Robot Search in Unknown Environments using POMDPs

Abstract

Search is an important competence for a robot. It is the core task of a search and rescue robot, and many other typical robots task require some form of search. In order to be truly autonomous, the robot must be able to perform its tasks in an unknown environment. Using SLAM, the robot has to make search decisions with increasing knowledge of the environment. Today, mostly Next Best View algorithms are used to achieve this feat. These are heuristic based algorithms, which balance between heuristic measures like information gain and traveling time. The action if often chosen greedily. In this thesis a novel approach is taken. POMDPs are used to model the problem of object search. Representing the changing environment explicitly in a POMDP is not feasible, since the number of possible layouts of the environment is just too great. Instead an instance of the POMDP model and the solution are recalculated every time step. Six different POMDP models were designed for known environments and three models for unknown environments. These were tested in a simulated environment and compared to a baseline Next Best View algorithm. Surprisingly, reasoning about unexplored environments was shown not to be necessary for a good result. It has been shown that although NBV works fast, the POMDP clearly gives a better solution, with an average search path that is almost twice as short.