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

aredo · 2005-02-16T05:35:27

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.