Go Down

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

rudey2145

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

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

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

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

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

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


PieterP

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

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

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

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