Go Down

### Topic: NEED PATH FINDING CODE FOR ARDUINO (Read 710 times)previous topic - next topic

#### rudey2145

##### Jan 20, 2019, 12:41 am
I am building an eco-friendly recycling bin that navigates itself around my school and efficiently recycles paper-waste. I need a prewritten program that is possible to execute in the Arduino IDE, which can determine the shortest path from one point to another with weighted, undirected segments. I know about Dijkstra's Algorithm and A*, but I'm greatly struggling to make a program myself. Does anyone know of a preexisting one or have the capability to create one themselves for me? Thank you very much.

#### 6v6gt

#1
##### Jan 20, 2019, 12:34 pm
Maybe start here: https://en.wikipedia.org/wiki/Travelling_salesman_problem

As I understand the application you have described though, I'd have thought that a set of pre-programmed routes would have been adequate.

#### patduino

#2
##### Jan 20, 2019, 01:31 pm
It seems to me that the more challenging part of the problem will be the actual traveling part.  Given a graph with a set of nodes and weighted edges, how do you plan to "drive" the cart after you figure out the path?
There are 10 types of people in the world, those who understand binary, and those that don't.

#### jimLee

#3
##### Jan 20, 2019, 07:56 pm
Mount a trash can on a Roomba.

-jim lee
PNW Ardiuno & Maker club
1012 9Th Street, Anacortes, WA 98221 (Around the back of building)

#### rudey2145

#4
##### Jan 21, 2019, 04:36 pm
I have thought about there being a future issue about what @patduino commented, however, I have no clue how to solve this myself, either. Any ideas?

#### rudey2145

#5
##### Jan 22, 2019, 10:38 pm
Also, @6v6gt, the Traveling Salesman problem asks, "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?", however, I would not like to know that fastest route to visit EVERY node, but just that fastest route from one to another.

#### rudey2145

#6
##### Jan 22, 2019, 10:53 pm
Anyone else can help?

#### PieterP

#7
##### Jan 23, 2019, 10:38 am
There are many implementations of the algorithms you mentioned that you can find online. The only problem is going to be dynamic memory usage.

If you use a Teensy or another ARM microcontroller with >64KiB of RAM, that's probably not an issue. If you're using an Arduino UNO with 2KiB of RAM, you're going to run into problems.

My advice, get some good pseudocode for A*, watch this video: https://www.youtube.com/watch?v=ySN5Wnu88nE, get a good understanding of how it works.
Then try to implement it in a high-level language like Python.
Once that works, move to desktop C++, so you can easily debug it.
As a final step, port your desktop C++ code to Arduino C++ code (i.e. no dynamic memory usage, just static buffers).

To avoid dynamic memory, use static arrays of nodes, with some flags (instead of adding and removing nodes from the "open" list, just have each node keep a flag "isOpen", for example).

Pieter

#### jimLee

#8
##### Jan 23, 2019, 07:45 pm
Anything that grows in size as things get complex.. You can use a SD drive to offload it and only bring in what's pertinent at that time. But it'll take some clever programming just to get that working.

And use a teensy.

-jim lee
PNW Ardiuno & Maker club
1012 9Th Street, Anacortes, WA 98221 (Around the back of building)

#### patduino

#9
##### Jan 23, 2019, 10:52 pm
To minimize the processing burden onboard the vehicle, you may want to consider pre-calculating the routes offline (desktop computer) and downloading them with the sketch.  The only real reason you'd need to do this onboard was if the routes or destinations changed. And if that was the case, you'd need to update the code / data file anyway.

I suggest first that you develop a simple set of routes by hand, load them into a data structure in the sketch or on an SD card and focus on making a mobile obstacle avoiding robot that can follow the routes and not run into anyone or into a wall.
There are 10 types of people in the world, those who understand binary, and those that don't.

#### sefjqf

#10
##### May 04, 2019, 02:54 pm
rudey2145, curious if you solved this problem for yourself.  I'm working on project with similar goals and came across this. But I'm also interest in automation to encourage recycling - so I'd love to hear if your project was a success.  If not done yet, I'll share what I develop to see if it can help you.

I'm doing what patduino suggests (calculating all paths off-line and then just doing look-ups).

Best of luck!

Go Up