Shortest path algorithm implementation using arrays

Using Arduino Programming Questions
#1

I am working on a project for UAV coordinated searching. I have a sample terrain data (which is supposed to be searched) of an area and it has been divided into a 20*20 grid, i.e. 400 cells. Now given a starting cell and ending cell, I need to find the shortest path from Starting to ending cell.

I had a look at the available shortest path algorithms such as A*, Yen's algo, Dijkstra algo but the difficulty I have in these is that they are implemented for graphs. Converting the input into a graph isn't possible due to memory constraints on the arduino board along with absence of STL. I had a look at StandardCplusplus library but it doesn't meet my requirements due to memory constraints (I have around 10 modules in my project).

Is there a possible way to get this implementation of the shortest path using only the default libraries in arduino, i.e. by using arrays? It would be really great if someone could guide me in the process while I try to implement it. Perhaps a use of anytime algorithms, especially because this is time critical.

The terrain input is as follows:

"Each cell has edges to all of its surrounding neighbours, with the elevation difference between the cell and a neighbour as the weight of the respective edge. Unreachable neighbours have edges with weights of 9999. Sample data for the first three cells are shown as follows:

0 21 9999 0 20 9999 0 1 7 1 20 9999 1 22 16 1 21 9999 1 0 7 1 2 9999 2 21 9999 2 23 9999 2 22 10 2 1 9999 2 3 7

In this set of data, this means that from cell (0, 0), cells (1, 0) and (1, 1) are unreachable, but it is possible to reach cell (0, 1) with a cost of 7. Similarly, from cell (0, 1), cells (1, 0), (1, 1) and (0, 2) are unreachable, but it is possible to reach cells (1, 2) with a cost of 16 and (0, 0) with a cost of 7.

Thanks a lot in advance

#2

the difficulty I have in these is that they are implemented for graphs

The implementation of an algorithm is not the same as its abstract representation. Dijkstra’s algorithm, for example, could be implemented using an array or some form of list.

Converting the input into a graph isn’t possible due to memory constraints on the arduino board along with absence of STL

And again, you are confusing the abstract representation (graph) with its implementation (array/list/whatever). I also don’t see what the “absence of STL” has to do with it.

Your problem is going to be designing a data representation which will fit in an Arduino. BTW you haven’t said which one you are using.

You have 400 nodes, each with six eight edges. Even if you could cram the info required for each edge into one byte you’ve already used 2400 3200 bytes which exceeds the available ram in a 328-based Arduino such as a Nano. If you can compile the graph info ahead of time, the 2400 3200 bytes can go in flash ram and then you might be able to do it but that would mean having to compile the code for each new problem. The 8kb of sram in a Mega 2560 might be enough to handle it.

Pete
[edit]Corrected a glaring numerical error! :blush:

#3

Now given a starting cell and ending cell, I need to find the shortest path from Starting to ending cell.

I am sure you have seen this:- http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm It will draw a line between two cells. It can be done using just an array there is no need for a display.

#4

@Grumpy_Mike The line algorithm solves a different kind of problem. The OP is referring to the kind of problem represented here: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Pete

#5

The actual number of edges for a cell should be 8. Now you don't need to create an array for 20 * 20 * 8 elements because there are repetitions. Half that number, i.e. 1600 elements, would suffice. If the maximum cost (excluding 9999) is less than 255 you would need 1600 bytes, which is a lot. Assuming you can manage this amount of memory you can probably map an array representation to a graph of sorts.

Note that the array maintains the edges, not the cells. I would create four distinct arrays for edges: North, North-East, East, South-East. For any cell having coordinates x, y, the four vertical edges would be: North [ x ], East [ y ], North [ x-1 ], East [ y-1 ]. The four diagonal edges would be represented similarly, after deciding how to flatten the two coordinates into a single number (e.g., x*20+y).

If you have a working algorithm based on graphs you can probably calculate each element: node x,y will be connected to node x+1,y with weight North[ x ]. The point is that you don't need to store the graph in memory, you just calculate the values for each node on the fly when you encounter one.

#6

Why does each cell have 8 edges when it is a square, unless you can cross from one square to the next diagonal one via a corner, which I don't think is implied in the original question.

#7

UKHeliBob: Why does each cell have 8 edges when it is a square, unless you can cross from one square to the next diagonal one via a corner, which I don't think is implied in the original question.

I think diagonal movement is indeed implied in the oq, though I might have got the coordinate system wrong.

In this set of data, this means that from cell (0, 0), cells (1, 0) and (1, 1) are unreachable, but it is possible to reach cell (0, 1) with a cost of 7. Similarly, from cell (0, 1), cells (1, 0), (1, 1) and (0, 2) are unreachable, but it is possible to reach cells (1, 2) with a cost of 16 and (0, 0) with a cost of 7.

#8

Checking back I think that you are right. If (1,1) is unreachable from (0,0) then diagonal movement is implied, but it may never be allowed. The coordinate system does not make sense to me even with the examples given. Perhaps the OP can enlighten us.

#9

Where on earth did I get 6 from? :blush:

Pete

#10

el_supremo: Where on earth did I get 6 from? :blush:

North, South, East, West, Spare1, Spare2. :P

#11

Sorry for the lack of Info, I am using the Mega 2560.

Here I will try clearing the coordinate system used in the example:

Id 0 is (0,0) Id 21 is (1,1) Id 20 is (1,0) Id 22 is (1,2) Id 1 is (0,1) Id 2 is (0,2) Id 3 is (0,3) Id 23 is (1,3)

0 21 9999 means that the weight to get from cell with ID 0 to cell with ID 21 is 9999 (which according to the description means unreachable!)

#12

"Shortest path" algorithms are for graphs ( networks, not pictures ), because graphs represent networks of roads, railways, foot trails, or scheduled air services, where the available routes through the graph represent the alternative possible paths using the available pathways rather than just going straight from A to B.

If you want your UAV to go straight from A to B, then just go there ! You don't need a route. I think your problem is somewhat misconceived.

If you want to follow some kind of systematic searching strategy, well that is a different problem, and a problem for which "shortest path" algorithms may, or may not, be useful.

#13

Converting the input into a graph isn't possible due to memory constraints on the arduino board along with absence of STL.

You can use the STL:

http://andybrown.me.uk/wk/2011/01/15/the-standard-template-library-stl-for-avr-with-c-streams/

Are you doing a physical search? Rather than one in memory? I think you would use different techniques.

#14

You have 400 nodes, each with six edges.

So you have a map, and you put a grid over it, and you have 400 cells in a 20x20 array.

These cells have six edges ??? Are they squares or cubes ? Or hexagons ?

And if such a large proportion of the squares are unreachable from most of their adjacent squares at any cost, then what you have looks more like a maze than a network.

So I'd suggest that you look into maze-following algorithms, of which there are several.

#15

0 21 9999 means that the weight to get from cell with ID 0 to cell with ID 21 is 9999

And a further consequence of this explanation, is that you are potentially allowing travel from one cell to another which is only diagonally adjacent.

Which means each cell has not four neighbours, nor six neighbours, but eight neighbours.

The size of the datastructure needed to keep this data has been raised as an issue on the Arduino.

There are many ways in which the data could be stored more compactly. For a start, you could leave out all the items of data which represent unreachable neighbours. If the "cost" isn't listed in the list, then you can deduce it is unreachable without storing data to say so. Secondly, if RAM space really is tight, you can dispense with the information about some cells being slightly more difficult to reach than others. If the cells are squares, then the cost of reaching a cell adjacent up or down or sideways is x and the cost of reaching a diagonally adjacent square is 1.4x where the 1.4 is the square root of 2 and follows from elementary geometry.

You can then implement your shortest path from A to B algorithm with minimal data storage requirement.

#16

Is it the shortest route or the least "cost" route that is required ?

#17

UKHeliBob: Is it the shortest route or the least "cost" route that is required ?

Least cost route

#18

michinyon: And a further consequence of this explanation, is that you are potentially allowing travel from one cell to another which is only diagonally adjacent.

Which means each cell has not four neighbours, nor six neighbours, but eight neighbours.

The size of the datastructure needed to keep this data has been raised as an issue on the Arduino.

There are many ways in which the data could be stored more compactly.

How about I remove the weight and instead store degrees of reachability of each cell from the current cell? 0 = Easy, 1 = moderately easy, 2 = moderately hard, 3 = hard, and then encode this into 2 bits per cell?

#19

On a Mega 2560 you might get away with using one byte for each weight which would require 3200 bytes for the weights plus probably another one byte per node for status information requiring a total of 3600 bytes which fits in the Mega's 8kB ram. That assumes of course that the largest array you have to handle is 20x20. I would focus on coding a specific algorithm, such as Dijkstra's, and getting it working on a small example. You could use the example shown on the WIKI page http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm. That would give you a better idea of how much memory is likely to be required. Then expand it to a 20x20 array.

Pete

#20

I'm not good at algorithms. Bear with me if I'm asking stupid questions, but I feel like we should have a benchmark to explore the feasibility of this project. Did you actually create and test a working program for the problem at hand on a less constrained device, and can you give us some estimates of time, memory usage, code size? You said that you would have implemented the algorithm in C/C++ using the STL. Did you check the implementation in reply #12? Which part of the STL are you missing: iterators, lists, sets, ...?

My own approach would use probes, i.e. objects that keep track of their position and cost. When a probe reaches a cell, it checks whether there is another probe in it (incumbent). If so it compares the costs. If the probe's cost is >= the cost of the incumbent it kills itself (apoptosis). If it's lower, it sends an apoptosis message to the incumbent's and replaces it. Then it spawns 8 probes going to the adjoining cells, which will repeat the process. Each probe keeps track of its parent and checks if it's alive. If the parent is dead the probe kills itself. The first probe to reach the target advertises its cost, and all probes whose current cost is higher than that go into apoptosis. The process ends when all living probes have spawned their children. The winner returns its path and cost by following the parents' trail.

As I said above, in my approach the problem map can be represented by 20*20*4 = 1600 elements, representing edges. I don't know how to estimate the number of probes for each generation, but it need to be less than 256 for the thing to work, so that the probe's id can be stored in one byte. Each probe would have to keep track of its position, cost, own id, parent id. A map with 256 living probes would take around 1.5kb. Add the map itself, and the memory for data should be around 1600 (edges map) + 400 (probes map) + 1536 (probes data) = about 3.6kb.