I am having some trouble understanding how A* search could be applied to a robot traversing a maze in real time. I understand how A* works but only in "pre-computed" sense (i.e. if you were to work out the whole path before attempting to traverse the maze).
How would you use it to give an answer to "where to next" at every step of the maze? Or am I missing something? Thanks a lot!
Generally the robot will map out the maze as best it can, then run the pathfinding algorithm and follow the resulting best path. If changes to the maze are later detected, the robot will rerun A* from its current position.
There is an alteration to A*, called D*-lite, that is able to reuse past searches to speed up future searches when small changes to the maze are made. This is the algorithm the Mars Rovers use.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments