Abstract“Exploration and search” is a typical task for autonomous robots performing in rescue missions, specifically addressing the problem of exploring the environment and at the same time searching for interesting features within the environment. In this paper, we model this problem as a multi‐objective exploration and search problem and present a prototype system, featuring a strategic level, which can be used to adapt the task of exploration and search to specific rescue missions. Specifically, we make use of high‐level representation of the robot plans through a Petri Net formalism that allows representing in a coherent framework decisions, loops, interrupts due to unexpected events or action failures, concurrent actions, and action synchronization. While autonomous exploration has been investigated in the past, we specifically focus on the problem of searching interesting features in the environment during the map building process. We discuss performance evaluation of exploration and search strategies for rescue robots, by using an effective performance metric, and present evaluation of our system through a set of experiments. © 2007 Wiley Periodicals, Inc.