An autonomous service robot often first has to search for auser to carry out a desired task. This is a challenging problem, especiallywhen this person moves around since the robot’s field of view is con-strained and the environment structure typically poses further visibilityconstraints that influence the perception of the user. In this paper, wepropose a novel method that computes the likelihood of the user’s ob-servability at each possible location in the environment based on MonteCarlo simulations. As the robot needs time to reach the possible searchlocations, we take this time as well as the visibility constraints into ac-count when computing effective search locations. In this way, the robotcan choose the next search location that has the maximum expectedobservability of the user. Our experiments in various simulated environ-ments demonstrate that our approach leads to a significantly shortersearch time compared to a greedy approach with background informa-tion. Using our proposed technique the robot can find the user with asearch time reduction of 20% compared to the informed greedy method.