In this paper we investigate the problem of searching for a hidden target in a bounded region of the plane using an autonomous robot which is only able to use local sensory information. The problem is naturally formulated in the continuous domain but the solution proposed is based on an aggregation/refinement approach in which the continuous search space is partitioned into a finite collection of regions on which we define a discrete search problem. A solution to the original problem is obtained through a refinement procedure that lifts the discrete path into a continuous one. We show that the discrete optimization is computationally difficult (NP-hard) but there are computationally efficient approximation algorithms for solving it. The resulting solution to the continuous problem is in general not optimal but one can construct bounds to gauge the cost penalty incurred due to (i) the discretization of the problem and (ii) the attempt to approximately solve the NP-hard problem in polynomial time. Numerical simulations show that the algorithms proposed behave significantly better than naive approaches such as a random walk or a greedy algorithm. (c) 2006 Elsevier Ltd. All rights reserved.

This paper proposes several definitions of "norm-observability" for nonlinear systems and explores relationships among them. These observability properties involve the existence of a bound on the norm of the state in terms of the norms of the output and the input on some time interval. A Lyapunov-like sufficient condition for norm-observability is also obtained. As an application, we prove several variants of LaSalle's stability theorem for switched nonlinear systems. These results are demonstrated to be useful for control design in the presence of switching as well as for developing stability results of Popov type for switched feedback systems.