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 constrained 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 observability 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 account 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 environments demonstrate that our approach leads to a significantly shorter search time compared to a greedy approach with background information. Using our proposed technique the robot can find the user with a search time reduction of compared to the informed greedy method.