CDS2013

Dynamic Pathfinding in Unknown Terrain

A problem with exploration rovers based on other planets is the propagation time for signals to be sent and received from a control station based back on Earth. As a result it is very difficult to make rovers navigate to their target location in real time. To solve this problem it would be better if exploration rovers where able to traverse terrain autonomously without any human input.

A real time simulation system was developed that applied the D* search algorithm to a rover in a simulated planetary environment. The environments for the system were provided by the Planet and Natural scene Generation Utility (PANGU) created by The University of Dundeeā€™s space research group.

As the rover traverses the region it collects data about the environment using a simulated sensor system. It is able to use the collected elevation data to develop an internal hazard map which can then be used for navigation using its pathfinding system.
To prove how effective the D* search algorithm is the simulation runs comparison simulations with different configurations. These configurations are D* when the terrain is unknown, D* when the terrain is known and the A* search algorithm.

 
Stewart Taylor
Website
stewart@taylore.net