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.

## Type of Work

Article (6) Book (0) Theses (0) Multimedia (0)

## Peer Review

Peer-reviewed only (6)

## Supplemental Material

Video (0) Audio (0) Images (0) Zip (0) Other files (0)

## Publication Year

## Campus

UC Berkeley (0) UC Davis (0) UC Irvine (1) UCLA (0) UC Merced (0) UC Riverside (1) UC San Diego (0) UCSF (0) UC Santa Barbara (1) UC Santa Cruz (0) UC Office of the President (0) Lawrence Berkeley National Laboratory (3) UC Agriculture & Natural Resources (0)

## Department

## Journal

## Discipline

Physical Sciences and Mathematics (1)

## Reuse License

BY - Attribution required (1)

## Scholarly Works (6 results)

We perform a self-consistent, time-dependent numerical simulations of dissipative turbulent plasmas at a higher Lundquist number, typically up to O(10(6)), using full three-dimensional compressible magnetohydrodynamics code with a numerical resolution of 128(3). Our simulations follow the time variation of global helicity, magnetic energy, and the dissipation rate and show that the global helicity remains approximately constant, while magnetic energy is decaying faster and the dissipation rate is decaying even faster than the magnetic energy. This establishes that the principle of minimum dissipation rate under the constraint of (approximate) conservation of global helicity is a viable approach for plasma relaxation. (c) 2008 American Institute of Physics.