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

This topic is 4683 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.

##### Share on other sites
Both A* and Dijkstra will visit 2^64 nodes if you let them search a path from (INT_MIN,INT_MIN) to (INT_MAX,INT_MAX) on an empty grid. 2^64 is huge...

My proposed algorithms both need only 1 step. And compute the exact answer, at least for an empty grid i am sure of it.

##### Share on other sites
On an empty grid A* will shoot straight to the goal.

##### Share on other sites
Quote:
 Original post by DrEvilOn an empty grid A* will shoot straight to the goal.

Depends on how you implement it. If you are using a depth-first traversal with taxicab it's true, but it then needs to store all intermediate steps in it's queue. Which is around 32 GBytes of data for (min,min) to (max,max).
If you use breadth-first traversal you fill a bounding box of start and end and need only 16 GByte of data.

DFS is around 2^33 steps which still takes ages, if one step was 1 CPU-cycle it is several seconds. In reality it's at least 100 times slower.

##### Share on other sites
As we are looking for the shortest path with the least number of turns shooting straight to the target doesn't help as you would need all shortest paths to decide which one has the least number of turns.
If you encode the turnnumber in you metric, like (distance<<32+turns) you will find the right path directly, but still need 32 GByte of data...

##### Share on other sites
Quote:
Original post by Trap
Quote:
 Original post by DrEvilOn an empty grid A* will shoot straight to the goal.

Depends on how you implement it. If you are using a depth-first traversal with taxicab it's true, but it then needs to store all intermediate steps in it's queue. Which is around 32 GBytes of data for (min,min) to (max,max).
If you use breadth-first traversol you fill a bounding box of start and end and need only 16 GByte of data.

DFS is around 2^33 steps which still takes ages, if one step was 1 CPU-cycle it is several seconds. In reality it's at least 100 times slower.

If you used BFS or DFS then it wouldn't be A*. A* is a blend of best first and Dijkstra. A*, IMPLEMENTED PROPERLY, will go straight for the goal in an empty grid. Don't know why you are even bringing up int min - int max searches, it has nothing to do with anything. Your solution couldn't handle that kind of memory either. Even the OP's example numbers were not even close to to numbers that large, well under even a signed short. It's still a large grid yes, and it will still not be a cheap search. I'd venture to guess that he probably doesnt need that kind of density in the graph anyways, and should probably use fewer nodes by increasing the size of the nodes, but even with that size of a graph, with simple rectangular obstacles A* would be pretty good still.

##### Share on other sites
Quote:
 Original post by TrapAs we are looking for the shortest path with the least number of turns shooting straight to the target doesn't help as you would need all shortest paths to decide which one has the least number of turns.If you encode the turnnumber in you metric, like (distance<<32+turns) you will find the right path directly, but still need 32 GByte of data...

Not really, you can build that straight into the search by penalizing the paths that change directions.

##### Share on other sites
My solution sketch is independent of path length and exponential on obstacle number.
A* is linear with path length and independent of obstacle number.

If there are lots of obstacles A* is better, if there is lots of empty space and few obstacles my solution is better.

I brought up an int min to int max search because of the weak specification of the problem. It is the hardest problem with a short input that fullfills the specs of the problem.

What is the meaning of "best first" in this problem? Distance to node + estimated distance to goal is equal for all nodes in the bounding box of start and goal. Take the one with the lowest distance to goal estimate?

##### Share on other sites
Hmm Look at nehe lesson 21 that has a player, a grid and an enemy wich moves and each level has an extra enemy. Maybe that could be of use as maybe the base or a reference.

##### Share on other sites
Quote:
 Original post by TrapWhat is the meaning of "best first" in this problem? Distance to node + estimated distance to goal is equal for all nodes in the bounding box of start and goal. Take the one with the lowest distance to goal estimate?

Not sure what you are saying here. Best first is a specific pathfinding algorithm that uses the distance to goal heuristic only. Distance to current node is given cost, which A* uses in addition to the estimated distance to goal heuristic. Dijkstra uses only the given cost. You seem to be mixing up algorithms in some of your responses. Not only does your proposed algorithm sound unnecessarily complex, but it wouldn't produce an optimal path, which is one of the requirements the OP posted, unless maybe in an empty grid, which is unlikely to ever be the case of a search.

If he used A* and penalized paths that change directions to favor straight paths he could do it all in one search. Dijkstra and A*(without an underestimated heuristic) are the only options guaranteed to find an optimal path, so if that is indeed a requirement then those would likely be the choices he has. A* expands less of the grid than Dijkstra which makes it faster. Dijkstra only considers the given cost, A* considers given cost + heuristic cost. The heuristic cost is what allows it to bee-line for the goal if it can. It also allows you to tweak its speed an accuracy by tweaking the heurisic weight. By tweaking 1 number you can make it behave more like best first or Dijkstra.

##### Share on other sites
I can't prove nor disprove that my algorithm sketch finds the optimal solution, can you?

Ok, while trying to give an example i found my error in thinking about best first. Thanks for making me think harder about it :)

##### Share on other sites
Quote:
 Original post by DrEvilBest first is a specific pathfinding algorithm that uses the distance to goal heuristic only.
Notice that there can be confusion in terms. AIMA describes A* as a "best-first search", and what you mean by "best first" is called a "greedy best-first search" in that book.

##### Share on other sites

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

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628682
• Total Posts
2984198

• 13
• 12
• 9
• 10
• 10