Incremental frontier generation for improvement of exploration efficiency

• Main Author: Senarathne, P. G. Chaminda Namal
• Other Authors: Wang Dan Wei
• Format: Theses and Dissertations
• Language: English
• Published: 2015
• Subjects: DRNTU::Engineering::Electrical and electronic engineering::Control and instrumentation::Robotics; DRNTU::Science::Mathematics::Discrete mathematics::Algorithms
• Online Access: https://hdl.handle.net/10356/65285
• Institution: Nanyang Technological University

Autonomously navigating a single or a multiple set of robots to map a previously unknown environment is known as autonomous exploration and is a fundamental operation in many robotic missions. Given the unknown nature of the environment, planning for the optimal exploratory path for a robot or a group of robots to completely cover the given environment is known to be NP-Hard. Therefore, all autonomous exploration strategies operate by successively selecting the next best sensing location as robot's intermediate target point in a greedy manner, until the environment is completely mapped. Frontier based exploration and its many variants, where the robot's next sensing location is selected from the boundary between the mapped-free and unknown space (i.e. frontier) from the occupancy grid representation of the environment, has emerged as the baseline exploration strategy due to its simplicity and scalability. This dissertation examines the efficient generation and management of frontier information to refresh frontier cell information at a high frequency, and how these frequently available frontier cells can be utilized to further improve the efficiency of exploration missions. Incremental algorithms to extract both safe and reachable area from the occupancy grid map by processing only the locally updated map data and in turn generate only the valid frontier cells in an efficient manner is introduced. The proposed algorithms are validated in real world experimental data and is shown to drastically reduce and bound the execution time throughout exploration missions with very high detection accuracy compared to state of the art incremental frontier extraction methods. The resulting high frequency frontier cell refreshing is utilized to propose an improvement to the traditional frontier based exploration strategy as the next contribution. A probabilistic decision step, based on the most recent frontier cell information is proposed to decide the desirability of the remaining motion of the robot to its current intermediate target and to re-plan when the current motion is undesirable. This reduces redundant exploratory motions of the robot and improves the total efficiency of exploration missions. Experiments carried out in both real and simulated, indoor and outdoor environments corroborate the efficiency of this method and also reveal that the re-planning capability is especially suitable for improving efficiency of indoor exploration missions. This re-planning ability is then utilized to propose a new goal oriented navigation algorithm in unknown environments based on frontier based exploration. This is achieved by directing the exploration towards the goal. A new utility function based on the combined distance estimate to the goal from the robot's position through known and unknown cells is introduced for directing the exploration steps. The distance from frontier cells to the goal which is still in unknown area is estimated using a visibility graph generated through the unknown area thus negating the need to access the entire search space. Experimental results show that the proposed navigation algorithm is an alternative to popular dynamic planning algorithms and that it provides the same travel distance efficiency and a superior re-planning cost efficiency. Finally, the efficiency of exploration missions in unbounded environments is discussed in terms of the compactness of generated maps. Balanced mapping in all possible directions to generate compact maps is captured as balancing the arrival time of the robot to available frontier cells in the robot's neighborhood. The proposed efficient frontier management algorithms are employed to efficiently update the waiting times of individual frontier cells for robot's arrival and a waiting time variance based utility function is derived to guide the robot in a compact exploratory motion. Simulated experiments conducted in multiple environments for both single and multiple robot systems validate the efficiency of the proposed compact exploration strategy in mapping unbounded environments.