Sign in to follow this  
aredo

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

Recommended Posts

Artificial Intelligence and Robotics are not my field so I'm asking for help here. The problem is about a world map which is a signed integer only 2D grid. Each robot can only move in 4 directions (N,S,E,W). And each robot can only move 1 position at a time. More than one robot can be placed on the same x,y coordinates. There are rectangle shaped obstacles on the world map/2D grid. Obstacles can be placed one above the other in whole or in part. A target can be placed anywhere on the map. I have to find the shortest path to reach the target and take into account which among the shortest possible paths needs less robot directions changes (90 degrees turning in practice), storing this value. If the shortest path with the least number of direction changes can't be followed by a robot to reach the target due to obstacles then I must discard the next shortest path even if that would allow reaching the target. Obstacles and robots can be added to the map at any time. I don't need to implement graphics for now. I read a bit about Dijkstra and A* algorithms. I was thinking about Dijkstra to calculate the shortest path but what if I have a robot at coordinates -15000,+400 and the target is at +40,+5 , just for example ? I am obliged to calculate all the possible paths and use an algorithm like Dijkstra and constrain it to work with the given world map and robot rules, or not ? I was thinking about a weighted graph for data structures with adjacency lists. Would this be right ? What I'd like to understand then is, could I make a weighted graph with vertices only for coordinates where there is an object ? But then what about the weight ? What should I use as the weight to have the Dijkstra algorithm work given what the world map and the rules set is about ? Or with a directed or undirected weighted graph should I be obliged to store every single cell of the grid map to find the connection to the next object although I know from the start that every single 1x1 cell is connected to the other ? I was thinking about using weight as the distance between one object and the next put on the graph which exist on the grid map and avoid considering every single cell to form a complete graph. But that would be wrong, wouldn't it ? I have to use C/C++ and there must be no restrictions on the grid size other than the fact that coordinates are signed integers.

Share this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Trap
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).


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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by RPGeezus
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



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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
TechnoGoth, you do realize you just described Dijkstra's, right?

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by DrEvil
On 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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Trap
Quote:
Original post by DrEvil
On 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 this post


Link to post
Share on other sites
Quote:
Original post by Trap
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...


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

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Trap
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?


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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by DrEvil
Best 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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this