Search-based Planning for Active Sensing in Goal-Directed Coverage Tasks

Tushar Kusnur, Dhruv Mauria Saxena, Maxim Likhachev

TL;DR

This paper introduces two novel search-based planning algorithms, SPLASH and SPLIT, for robots (specifically UAVs) that need to cover areas of interest while actively controlling their sensors. These methods aim to maximize information gain by intelligently planning both the robot's path and its sensor's orientation, outperforming traditional approaches that struggle with the high dimensionality of this combined planning problem.

What Problem Does This Paper Address?

Robots, particularly Unmanned Aerial Vehicles (UAVs), are increasingly used for tasks requiring them to observe or "cover" specific areas of an environment. Think of applications like environmental monitoring, traffic surveillance, or post-disaster assessment. These robots often have sensors with a limited field of view, and they can actively control the orientation of these sensors (e.g., a camera's yaw). The challenge is to plan a robot's trajectory and its sensor's orientation simultaneously to maximize the amount of useful information gathered, while also ensuring the robot avoids collisions and reaches a designated goal.

This problem is computationally difficult because it involves planning in a high-dimensional "joint state space" that includes the robot's position, orientation, velocity, and the sensor's orientation, along with a history of past sensor observations. Traditional search-based planners, while guaranteeing optimality in simpler scenarios, become intractable in this complex, high-dimensional space. Furthermore, simply planning the robot's path first and then trying to optimize the sensor is suboptimal, as the best sensor strategy often depends on the robot's future movements.

Methods

The paper proposes two distinct search-based algorithms to tackle this challenge:

  • SPLASH (Sensor Planning with Sensor History): This approach decouples the problem into two stages. First, it computes a robot trajectory using a Multi-Heuristic A (MHA) search, optimizing for motion primitive costs. Second, it plans the sensor trajectory for this fixed robot path using a standard A search. The key innovation here is the incorporation of a partial sensor history* into the sensor planning stage. This history helps the planner avoid re-observing areas already covered, thus maximizing new information gain without the computational burden of considering the full sensor history.
  • SPLIT (Sensor Planning with Local Iterative Tunneling): This method builds upon SPLASH. It starts with the suboptimal joint trajectory generated by SPLASH (or a similar initialization). Then, it employs a refinement process based on the Iterative Tunneling Search with A (ITSA) algorithm. SPLIT iteratively expands "tunnels" around the initial trajectory in the joint state space, performing local searches to find better solutions that optimize coverage cost. This two-step initialize-and-refine strategy aims to find a better solution than the initial one without the prohibitive cost of searching the entire joint state space from scratch.

Datasets

Not discussed in the paper. The authors mention using "200 randomly generated start-goal pairs over several maps" which were derived from a previously established persistent coverage framework [8]. These maps were generated by letting a map decay over time, creating complex coverage zones.

Key Insights and Ideas

  • Sensor History is Crucial, but Partial History Suffices: The paper demonstrates that while considering the full sensor history is computationally prohibitive, maintaining a limited history (e.g., size 3 or 5) significantly improves coverage by preventing redundant observations. Beyond a certain history size, the gains diminish.
  • Decoupling and Refinement is Effective: SPLASH's decoupling of robot and sensor planning, combined with SPLIT's iterative local refinement, offers a practical trade-off between computational cost and solution quality compared to full joint-space search.
  • Local Refinement Exploits "Close" Solutions: The insight that approximate search algorithms often overlook solutions "close" to the computed one is leveraged by SPLIT. By iteratively expanding search tunnels, it can find improved solutions without re-exploring the entire state space.
  • Trade-off Between Coverage and Path Cost: The experiments show that while SPLASH prioritizes minimizing sensor footprint overlaps (leading to better coverage), SPLIT can further refine this to also reduce path costs.

Key Results

  • SPLASH: Increasing sensor history size (from 0 to 3 or 5) led to an increase in the number of covered cells, indicating better information gain. The average priority of covered cells remained relatively stable, suggesting that while more area was covered, the "urgency" of the newly covered cells didn't drastically change.
  • SPLIT: Each iteration of SPLIT showed improvements in coverage cost (lower sum of cell priorities) and decreasing path costs. For real-time planning scenarios (e.g., a 5-second timeout), 2-3 iterations of SPLIT were found to be feasible and beneficial.
  • Comparison to Full Joint-Space Search: A baseline approach of running MHA* directly on the joint state space was significantly slower (average planning time of 8.44 ± 6.40s with a 20s timeout) compared to SPLASH or even a few iterations of SPLIT.

Limitations and Future Work

  • SPLIT's Iterative Search Inefficiency: A limitation of SPLIT (and ITSA*) is that search efforts are not reused between iterations, making each subsequent iteration take longer. The authors suggest reusing search efforts for speed-ups.
  • Sensor History in SPLIT: SPLIT currently doesn't incorporate sensor history in its refinement phase. The authors propose adapting SPLIT to adaptively increase sensor history size with increasing iterations.
  • Heuristic for Sensor Coverage: The paper mentions that formulating a consistent heuristic for sensor coverage is a direction for future work, which could further improve the performance of both SPLASH and SPLIT.
  • Real-time Performance: While SPLIT shows promise for real-time applications with a limited number of iterations, its performance is sensitive to the immediate area around the initial plan.

Summary updated

Abstract

Path planning for robotic coverage is the task of determining a collision-free robot trajectory that observes all points of interest in an environment. Robots employed for such tasks are often capable of exercising active control over onboard observational sensors during navigation. In this paper, we tackle the problem of planning robot and sensor trajectories that maximize information gain in such tasks where the robot needs to cover points of interest with its sensor footprint. Search-based planners in general guarantee completeness and provable bounds on suboptimality with respect to an underlying graph discretization. However, searching for kinodynamically feasible paths in the joint space of robot and sensor state variables with standard search is computationally expensive. We propose two alternative search-based approaches to this problem. The first solves for robot and sensor trajectories independently in decoupled state spaces while maintaining a history of sensor headings during the search. The second is a two-step approach that first quickly computes a solution in decoupled state spaces and then refines it by searching its local neighborhood in the joint space for a better solution. We evaluate our approaches in simulation with a kinodynamically constrained unmanned aerial vehicle performing coverage over a 2D environment and show their benefits.
BibTeX
@inproceedings{kusnur2021search,
  author = {Tushar Kusnur and Dhruv Mauria Saxena and Maxim Likhachev},
  title = {{Search-based Planning for Active Sensing in Goal-Directed Coverage Tasks}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2021},
  doi = {10.1109/icra48506.2021.9561310},
}
Figure