Intrinsic and environmental factors modulating autonomous robotic search under high uncertainty

Abstract

Autonomous robotic search problems deal with different levels of uncertainty. When uncertainty is low, deterministic strategies employing available knowledge result in most effective searches. However, there are domains where uncertainty is always high since information about robot location, environment boundaries or precise reference points is unattainable, e.g., in cave, deep ocean, planetary exploration, or upon sensor or communications impairment. Furthermore, latency regarding when search targets move, appear or disappear add to uncertainty sources. Here we study intrinsic and environmental factors that affect low-informed robotic search based on diffusive Brownian, naive ballistic, and superdiffusive strategies (Lévy walks), and in particular, the effectiveness of their random exploration. Representative strategies were evaluated considering both intrinsic (motion drift, energy or memory limitations) and extrinsic factors (obstacles and search boundaries). Our results point towards minimum-knowledge based modulation approaches that can adjust distinct spatial and temporal aspects of random exploration to lead to effective autonomous search under uncertainty.

Figure 1

Brownian and Lévy search simulation models. Traces on the left are examples of planar Brownian exploration: The blue trace is a pure Brownian search and the green trace incorporates a small local memory of previous positions to avoid recently explored areas (see details in further sections). “Brownian + memory” used the same initialisation seed as the pure Brownian search, and both ran for ${10}^3$ steps. The overlapped representation allows to identify that incorporating a small memory leads to a more efficient use of the available resources, expanding the exploration clusters of the pure Brownian strategy. Traces on the right show a similar experiment applied to Lévy exploration with $\alpha =2.5$. The red trace is a pure Lévy search, and the black trace incorporates the effect of locomotion drift (0.6${}^{\circ }$, implementation described below). The Lévy strategy with drift corresponds to situations where global position references are not available, since a robot cannot perform indefinite perfectly-straight trajectories without correcting from external information. Note the differences between the two Lévy searches: both start very close to each other (indicated by triangles) and gradually diverge when drift is present, with noticeable deviations during long walks (final positions indicated by squares). We study a set of intrinsic and extrinsic factors and show that their effect can be utilised to modulate low-informed autonomous random search.

Figure 2

Modulation of Lévy travel length probability by intrinsic and extrinsic factors. Each represented trace is the complementary cumulative distribution function (CCDF) of the travel lengths for each strategy/parameter combination. We show its modulation by the exponent parameter $\alpha$ (blue, orange and green traces) and under different factors: intrinsic (battery truncated –red– and drift bound –brown–) and extrinsic (environment bound, a basic model that truncates trajectories at ${10}^2$ a.u. to represent search area diameter limit –purple trace–). Each CCDF was computed numerically with the models described in “Robot simulation models” section. The dashed rectangle indicates the region employed for the drift and battery analyses discussed in Fig. 3.

Figure 3

Effect of motion drift and battery constraints over travel length probability. For all traces in this figure $\alpha =2.5$ and no environment bounds. A pure implementation of Lévy search would strictly follow a power-law (dark-green trace). In practice, there are several intrinsic and extrinsic parameters that affect the planned strategy when implemented in a robot. Motion drift is caused by uncertainty in the locomotive plant (i.e., wheel slipping, inertial sensor accuracy, etc.) and effectively limits long travels. Two representative drift values are depicted in red and blue. Energy limitations are considered in the “battery truncated” case (brighter red, green and blue traces) where individual travels are limited in length to use at most 10% of the available battery (“Robot simulation models” section).

Figure 4

Exploration diffusivity represented as the area explored by each strategy over time. Each trace aggregates 1000 simulations by representing the minimum area covered by at least 900 of the runs at each point in time. A square marker highlights the point where each strategy covered 85% of the total available area (see Table 1 for the area sizes).

Figure 5

Exploration redundancy represented by heat maps of revisit frequency for a set of search strategies and environments. Panels correspond to: (a) Plain map and ballistic random bounce, (b) Dense Forest map and Lévy mirror bounce, (c) craters map and ballistic mirror bounce, (d) Craters map and Lévy mirror bounce, (e) Triangle map and Lévy recast bounce, (f) Corridor map and Lévy wall follow. Representative trajectories are depicted in black for each map (${10}^4$ steps). The supplementary material includes a video animation (Supplementary Video 1) depicting the evolution of this metric for the Craters map with strategies: Ballistic random bounce, Lévy mirror bounce, Brownian with memory, and uninformed Brownian.

Figure 6

Revisit time analysis. For illustrative purposes we focus our analysis on the Craters map and four search strategies that have different exploration diffusivity levels (see Fig. 4). (a) A colour map representation of the time since last visit to each cell at step number 300K. An animated version of this representation (Supplementary Video 2) is also provided. Note the non-uniformity of the Brownian strategy in this representation. Markers 1, 2 and 3 indicate the location of three representative cells which are discussed below. The revisit sequence was also stored for every cell during a 100M step simulation for each strategy. (b) Cumulative distribution function (CDF) of the revisit intervals for every cell. There are three overlayed traces corresponding to the CDF for cells 1, 2 and 3. The ballistic strategy shows significantly increased redundancy near the search area limits (cell 3). (c) Revisit sequence for cell 2 on a plot where each data point is the revisit interval annotated at the corresponding simulation time step. The heterogeneous revisiting time of the Brownian strategy becomes apparent as it is the only strategy with revisit times $>{10}^5$ (indicated by a vertical line) which translate into empty horizontal stripes. This effect can be overcome with the implementation of a short-term memory to reduce local repetitions (“Brownian, memory”), which yields similar temporal profile to the Lévy-mirror bounce strategy for this map. The ballistic strategy yields medium revisit times concentrated between ${10}^3$ and ${10}^5$.