# Robots on a 2D grid with obstacles to a target... is Dijkstra the best solution?

This topic is 4967 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

##### Share on other sites
Dijkstra results in a sphere of visited nodes around the starting point, it's radius is equal to the length of the shortest path. A* results in a bounding box of start and endpoint.
Both are very expensive on a dense grid.

3 Questions: Do you need the optimal solution? Is there a limit on the number of obstacles? The obstacles are rectangle shaped, but are they axis aligned?

If your map size is only limited to be a 32bit number you can rule out any algorithm that is slower than O(log mapsize).

##### Share on other sites
Quote:
 Original post by TrapDijkstra results in a sphere of visited nodes around the starting point, it's radius is equal to the length of the shortest path. A* results in a bounding box of start and endpoint.Both are very expensive on a dense grid.3 Questions: Do you need the optimal solution? Is there a limit on the number of obstacles? The obstacles are rectangle shaped, but are they axis aligned?If your map size is only limited to be a 32bit number you can rule out any algorithm that is slower than O(log mapsize).

1) I need to find the best algorithm I can implement, but it has not to be the best one around. Even the simplest solution would do it as long as its cost is at an acceptable level.
2) No limits on the number of either obstacles or robots on the map. For each robot I have to find the shortest path that obeys to the minimum direction changes rule and use this to decide which robots can reach the target.
3) Rectangle obstacles can be either vertical or horizontal. No constraint in size there other than the map itself.

##### Share on other sites
This sounds less like a robotics question and more like a programming puzzle.

I say this because if you have n robots, and you MUST find the best path for each and every robot, taking in to account the decisions of the other robots, then you're going to be eating up processing like it's going out of style.

If you don't absolutely need the shortest path, or need to get this program running in something approximating real-time might I suggest the following:

1. Move the robot towards the desired location.
2. If it hits an obsticle have it:
2a. Pick strategy a or strategy b.
2b. Pick strategy a or stragegy b (yes, two random events in a row).
2c. Go to step 1.

Strategy a:
1. Turn a random direction.
2. Move for a random increment

Strategy b:
2. Randomly choose either the x or y axis.
3. Have the robot move towards the destination only along that axis.

Once the robot has found a path to the exit you can 'trim' the path afterwards (remove loops, cut corners, etc...) to get a more effecient exit plan.

This 'should' get your robots to the exit sooner or later. :)

Will

##### Share on other sites
Quote:
 Original post by RPGeezusThis sounds less like a robotics question and more like a programming puzzle.I say this because if you have n robots, and you MUST find the best path for each and every robot, taking in to account the decisions of the other robots, then you're going to be eating up processing like it's going out of style. If you don't absolutely need the shortest path, or need to get this program running in something approximating real-time might I suggest the following:1. Move the robot towards the desired location.2. If it hits an obsticle have it:2a. Pick strategy a or strategy b.2b. Pick strategy a or stragegy b (yes, two random events in a row).2c. Go to step 1.Strategy a:1. Turn a random direction.2. Move for a random incrementStrategy b:2. Randomly choose either the x or y axis.3. Have the robot move towards the destination only along that axis.Once the robot has found a path to the exit you can 'trim' the path afterwards (remove loops, cut corners, etc...) to get a more effecient exit plan.This 'should' get your robots to the exit sooner or later. :)Will

Unfortunately I have to absolutely find the shortest path among the free ones with less robot direction changes and know how many changes are needed. Also, it must be the best implementation I can come up with but I still know only a bit about all this stuff, it's just 72 hours that I started studying Dijkstra, networks and edge/path relaxation. I don't have enough knowledge for using A* and an heuristic approach so I can't use the best algorithms out there but I was thinking about an adapted/constrained Dijkstra approach.
Also, the world is a totally dynamic 32bit int signed square 2D grid map as the only limitation, nothing in the program must have a fixed size, none of the structures, everything has to be dynamic.

For this reason I couldn't use other simpler approaches.

##### Share on other sites
Do you have complete world knowledge? Meaning you known the size of the grid, the location of the target, and what if anything is in a space.

If so then I would solve it like this:

An action is a move or turn a turn.
Each action has a cost of 1.

So starting from the robot's current location use depth first search, to find a path to the goal, with an intial maxium depth of half the number of spaces on the grid. With some testing you should be able to determine a much lower maxium depth. Also when calculating a path check visited spaces and discard any path that attempts to enter a previously visited space. Finally when calculating a path discard it if the current cost is greater then cost of shortest found path. In this way you will cut down on the proccessing time by ignoring paths that the agent already knows to be longer.

The path finding algorthim is run when the robot is first placed and when the next space in the path is an obstacle. You could improve accuracy at the cost of performance by recalucating the path each time an object is placed in the current path but that will mean a greater drag on performance, and may not be worth it when it comes times to run the app.

##### Share on other sites
TechnoGoth, you do realize you just described Dijkstra's, right?

##### Share on other sites
Dijkstra is the best solution. It computes the BEST route, int he SHORTEST time.

##### Share on other sites
Dijkstra is surely not the fastest algorithm in this case.

You could do a backtracking algorithm like this:
The best way is the direct way.
If the direct way is blocked try going both ways around it and choose the better one, recursive for partial ways.

Which is independent on boardsize and exponential with respect to the number of obstacles.

Or another possibility: Create a new graph with 1 node at each edges of each obstacle, add start and end node. for all directly reachable combinations of nodes compute the distance. Run Dijkstra on this graph.

##### Share on other sites
A* will produce the same path as Dijkstra with less nodes searched and faster with a non overestimated heuristic. If you have a specific goal in mind, A* will find it fastest. If there are multiple goals then Dijkstra is what you want.

1. 1
2. 2
Rutin
22
3. 3
4. 4
5. 5
frob
12

• 17
• 9
• 31
• 16
• 9
• ### Forum Statistics

• Total Topics
632616
• Total Posts
3007447

×