Space Exploration

Implementation of several algorithms for space and unknown terrain exploration.

Table of Contents

• Path finding algorithms
  • D* Lite
  • A*
• Frontier detection algorithms
• Path Smoothing

D* Lite

Path finding algorithms specifically designed for unknown environmments. Its efficiency lays in the possibility to find a new path without entirely recompute the whole path from goal o source.

Algorithm described in Koenig, S., & Likhachev, M. (2005). Fast replanning for navigation in unknown terrain. IEEE Transactions on Robotics, 21(3), 354–363.

A*

Efficient path finding algorithm generally described as a natural evolution of Djikstra algorithm after the introduction of the direction's concept.

Algorithm described in Hart, P. E.; Nilsson, N.J.; Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics. 4 (2): 100–7.

Frontier Detection

Efficient frontier detection algorithm inspired by the Expanding Wavefront Frontier Detection algorithm presented in Quin, P., Alempijevic, A., Paul, G., & Liu, D. (2014, January). Expanding wavefront frontier detection: An approach for efficiently detecting frontier cells. In Australasian Conference on Robotics and Automation, ACRA., but made faster through the implementation of an RTree able to detect the only frontiers expanded by the robot at each iteration.

Path Smoothing

Two path smoothing algorithms.