People Finding under Visibility Constraints using Graph-Based Motion Prediction

An autonomous service robot often first has to search for a

user to carry out a desired task. This is a challenging problem, especially

when this person moves around since the robot’s field of view is con-

strained and the environment structure typically poses further visibility

constraints that influence the perception of the user. In this paper, we

propose a novel method that computes the likelihood of the user’s ob-

servability at each possible location in the environment based on Monte

Carlo simulations. As the robot needs time to reach the possible search

locations, we take this time as well as the visibility constraints into ac-

count when computing effective search locations. In this way, the robot

can choose the next search location that has the maximum expected

observability of the user. Our experiments in various simulated environ-

ments demonstrate that our approach leads to a significantly shorter

search time compared to a greedy approach with background informa-

tion. Using our proposed technique the robot can find the user with a

search time reduction of 20% compared to the informed greedy method.