Efficient algorithms and a two-stage framework for autonomous exploration of complex 3D environments using a climbing robot

Publication Type:
Thesis
Issue Date:
2016
Full metadata record
Files in This Item:
Filename Description Size
01front.pdf194.97 kB
Adobe PDF
02whole.pdf7.5 MB
Adobe PDF
Enabling robots to autonomously explore complex 3D environments is crucial in facilitating the automation of many real-world tasks. There exist many algorithms for exploring unknown environments with autonomous robots. Most of these are restricted to the 2D case, or to cases where the robot can be abstracted as a holonomic point robot. Algorithms that deal with the 3D case restrict the robot’s possible positions to the 2D plane, or assume that the robot can freely move through any empty space, like an idealised quadrocopter. This thesis presents a two-stage exploration framework that allows robots to consider any adherable surface in a 3D environment as a potential position from which to conduct exploration. The framework is therefore suitable to any robotic platform that must at all times maintain contact with a surface, but where this surface need not be the floor plane. A Nearest Neighbours Exploration Approach (NNEA) is developed to accomplish exploration of the environment immediately surrounding the robot when the robot is fixed to a position on a surface. In this approach, the Next Best Viewpoint is selected first by evaluating and choosing between candidate viewpoints that are within a bounded range of the robot’s current position. NNEA is demonstrated in experiments in a real bridge environment for the case of a high degrees of freedom (DOF) robot arm with a fixed base. NNEA is shown to result in faster exploration times in the case of a high-DOF robot arm in a fixed base position. Four frontier detection algorithms are proposed and investigated for determining the set of frontiers—the boundary between known and unknown space—after each map update. The resulting frontiers are used to limit which candidate positions need to be considered for exploration. The novel frontier detection algorithms are compared to other state of the art algorithms and are found to be suited for efficient frontier detection in different situations. A novel graph-based method for selecting the Next Best Base location (NBB) is presented in which the map is used to create an updated graph of possible positions for the robot base, sampled from all surfaces. Positions that are sufficiently close to the frontiers are selected as candidate positions for the robot to move to next. The information that could be gained from each reachable candidate position is estimated. A cost function determines which candidate is the best to move to next, and the robot moves to that position to take another sequence of scans. This method is demonstrated in simulations and experiments to be efficient in minimising the computation required to select and move to the NBB. The exploration framework and the developed algorithms and approach are demonstrated in simulation in an environment made up of unconnected surfaces, large enough that the robot is required to repeatedly move through the environment in order to fully explore it. The framework is shown to result in efficient exploration of the observable environment.
Please use this identifier to cite or link to this item: