Frontier-based exploration for unknown environments using incremental triangulation

In this article we present a new exploration strategy to reduce searching time while simultaneously increasing the robot's knowledge about its surroundings. A robot's ability to successfully complete a required task is bound by its knowledge about the operation environment. Thus, the robot must be able to collect information from its surrounding and map it accurately to create a correct representation of the environment and use it as a return path later. An increasing number of applications, such as surveillance and search and rescue, impose time constraints on the mapping and exploration process. The proposed Triangulation-Based exploration maps the environment incrementally using our Incremental Triangulation Algorithm to accelerate the searching process. To achieve those objectives this article introduces the Dynamic Triangulation Tree DTT which is a tree-like structure built incrementally during the Incremental Triangulation Algorithm. The DTT compactly represents the geometry of the environment which is utilized for minimizing the overall exploration time. Our solution drives the exploration process towards areas that will provide the robot with greater exposure to its surroundings by considering not only the distances to the frontiers but also the currently known surroundings of the environment. The effectiveness of the DTT and the efficiency of the proposed frontier selection process is validated in simulations using various scenarios to demonstrate the main advantages of the proposed DTT, namely ease of construction, compactness and completeness for "search and rescue" and "sample and return" missions.