Robots on a 2D grid with obstacles to a target... is Dijkstra the best solution?
Author
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.
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).
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).
Author
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.
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
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
Author
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.
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.
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.
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
