Searching Objects in Known Environments: Empowering Simple Heuristic Strategies

We consider the problem of exploring a known structured environment to find an object with a mobile robot. We proposed a novel heuristic-based strategy for reducing the traveled distance by first obtaining an exploration order of the rooms in the environment and then, searching for the object in each room by positioning the robot through a set of viewpoints. For the exploration order we proposed a heuristic based on the distance from the robot to the room, the probability of finding the object therein and the room area; integrated in a \(O(n^2)\) complexity greedy algorithm that selects the next room. The experimental results show an advantage of the proposed heuristic over other methods in terms of expected traveled distance, except for full search which has a complexity of O(n!). For the exploration within each room, we integrate the localization of horizontal flat surfaces with the generation of poses. With the set of poses, a similar heuristic establishes the exploration order that guides the robot path inside the room. The evaluation of the set of poses shows an average coverage of the flat surfaces of more than 90% when it is configured with an overlap of 40%. Experiments were performed with a real robot using three objects in a six-room environment. The success rate for the robot finding the object is 86.6%.