A Planning Framework for Persistent, Multi-UAV Coverage with Global Deconfliction

Tushar Kusnur, Shohin Mukherjee, Dhruv Mauria Saxena, Tomoya Fukami, Takayuki Koyama, Oren Salzman, Maxim Likhachev

TL;DR

This paper presents a novel framework for enabling multiple Unmanned Aerial Vehicles (UAVs) to collaboratively and persistently cover an area, ensuring continuous coverage even as coverage "decays" over time. The key innovation is a globally deconflicting, kinodynamic path planning approach that efficiently coordinates UAVs to avoid collisions while maintaining coverage goals.

What Problem Does This Paper Address?

Traditional robot coverage focuses on a single robot visiting all points of interest. However, many real-world applications, like environmental monitoring, disaster assessment, or traffic congestion monitoring, require persistent coverage – continuously maintaining a desired level of coverage over time. This is challenging because coverage naturally degrades (e.g., dust accumulates on a cleaned floor). For multi-robot systems, this problem is compounded by the need for collision avoidance among multiple agents. Existing frameworks often tackle subproblems individually, but a comprehensive solution for persistent, multi-robot coverage with global deconfliction was lacking. This paper aims to fill that gap by providing a unified framework.

Methods

The proposed framework integrates several key components:

  • System Manager (SM): Acts as the communication hub between the centralized planner and individual UAVs, relaying mission maps and updated plans.
  • Prioritized Planner (PP): Orchestrates the planning cycle, managing updates to the mission map and coordinating the planning for each UAV.
  • Goal Assigner (GA): Determines the next target location for a UAV. It uses a graph-based approach (similar to Dijkstra's) where potential goals are connected to a "pseudo-goal." The cost considers both the urgency of covering a cell (based on its lifetime and current age) and the distance to it.
  • Goal Planner (GP): Computes a kinodynamically feasible path for a UAV to its assigned goal. This involves search-based planning on a state-lattice, considering the UAV's pose, velocity, and time, while actively pruning trajectories that would lead to collisions with other UAVs' committed plans.

A crucial concept is committed plans: parts of a UAV's planned trajectory that it is guaranteed to execute. The framework ensures global deconfliction by planning paths that do not intersect with the committed plans of other UAVs, either in space or time. This is achieved by construction, rather than reactive collision resolution.

Datasets

Not discussed in the paper. The experiments utilize simulated environments and real-world flight tests on custom maps.

Key Insights and Ideas

  • Persistent Coverage is More Than Just Coverage: The need to revisit areas as coverage decays adds a temporal dimension to traditional coverage problems, requiring a dynamic planning approach.
  • Global Deconfliction by Construction is Key: Instead of reactive collision avoidance, planning paths that are guaranteed to be collision-free with committed plans of other robots is more robust and avoids deadlocks.
  • Trade-offs in Committed Plan Length (tmax): A longer tmax makes UAVs less reactive to changes but increases redundant coverage. A shorter tmax improves reactivity but can lead to more frequent replanning and "plan thrashing."
  • Prioritization and Distance are Intertwined: The Goal Assigner effectively balances the urgency of covering a cell with the effort required to reach it, using a graph-based heuristic.
  • Simulation to Real-World Transfer: The framework demonstrates comparable performance in both simulated and real-world environments, highlighting its robustness to real-world stochasticity.

Key Results

  • The framework successfully maintains persistent coverage, with coverage levels decaying slowly even when resources (UAVs) are insufficient.
  • Global deconfliction incurs a negligibly higher planning cost compared to weaker, local collision-checking schemes.
  • In simulations, the framework kept the average criticality of cells below one (meaning no cells expired) for most scenarios, with some decay occurring only when the number of UAVs was significantly less than required for the map size.
  • Real-world experiments showed similar performance to simulations, with minimal stationary time for UAVs.
  • The framework supports dynamic addition/removal of UAVs without significantly impacting performance.

Limitations and Future Work

  • Myopic Planning: The current goal assignment is greedy and decoupled from goal planning, meaning it's not globally optimal. Future work could explore learning better strategies for repeatedly covering zones.
  • Anytime Planning: Given that planning time can be a bottleneck, incorporating anytime planning techniques is suggested to handle situations where deliberation time is limited.
  • Stochasticity in Real-World: While the framework performs well, it relies on the assumption of perfect state estimation and control in simulation. Real-world experiments show robustness, but further work could explicitly address larger deviations from planned paths.
  • Learning Macro-Actions: The authors suggest learning macro-actions from data to improve the planner's ability to repeatedly cover zones.

Summary updated

Abstract

Planning for multi-robot coverage seeks to determine collision-free paths for a fleet of robots, enabling them to collectively observe points of interest in an environment. Persistent coverage is a variant of traditional coverage where coverage-levels in the environment decay over time. Thus, robots have to continuously revisit parts of the environment to maintain a desired coverage-level. Facilitating this in the real world demands we tackle numerous subproblems. While there exist standard solutions to these subproblems, there is no complete framework that addresses all of their individual challenges as a whole in a practical setting. We adapt and combine these solutions to present a planning framework for persistent coverage with multiple unmanned aerial vehicles (UAVs). Specifically, we run a continuous loop of goal assignment and globally deconflicting, kinodynamic path planning for multiple UAVs. We evaluate our framework in simulation as well as the real world. In particular, we demonstrate that (i) our framework exhibits graceful coverage given sufficient resources, we maintain persistent coverage; if resources are insufficient (e.g., having too few UAVs for a given size of the enviornment), coverage-levels decay slowly and (ii) planning with global deconfliction in our framework incurs a negligibly higher price compared to other weaker, more local collision-checking schemes. (Video: https://youtu.be/aqDs6Wymp5Q)
BibTeX
@inproceedings{kusnur2019planning,
  author = {Tushar Kusnur and Shohin Mukherjee and Dhruv Mauria Saxena and Tomoya Fukami and Takayuki Koyama and Oren Salzman and Maxim Likhachev},
  title = {{A Planning Framework for Persistent, Multi-UAV Coverage with Global Deconfliction}},
  booktitle = {Fsr},
  year = {2019},
  doi = {10.1007/978-981-15-9460-1\_32},
}
Figure