Consider a coverage problem for a team of agents in the plane: target points appear sporadically over time in a bounded environment and must be visited by one of the agents. It is desired to minimize the expected elapsed time between the appearance of a target point, and the instant it is visited. For holonomic agents, this reduces to a continuous facility location problem, well studied in the geometric optimization literature. We consider a team of nonholonomic vehicles constrained to move with constant forward speed along paths of bounded curvature. We show that the optimal policy depends on the density of vehicles in the environment. In low density scenarios, the optimal policy resembles that of holonomic agents: the environment is partitioned into subregions of dominance, and each vehicle is responsible for targets appearing in its own subregion (territorial behavior). As the density increases, the optimal policy exhibits a transition to a gregarious behavior in which the team loiters in a coordinated pattern, and each vehicle visits targets that appear immediately in front of it.
related publications
- J.J. Enright, K. Savla, and E. Frazzoli, Efficient Cooperative Search
and Surveillance, chapter in Handbook of Unmanned Aerial Vehicles, edited by Kimon P. Valavanis and George J. Vachtsevanos, published by Springer, invited and in preparation, 2012.
- John J. Enright, Ketan Savla, Emilio Frazzoli, and Francesco Bullo, Dynamic Routing for UAV Teams, in AIAA Journal of Guidance, Control, and Dynamics, Vol. 32, No. 4, July-Aug 2009. [PDF]
- J.J. Enright, K. Savla, and E. Frazzoli, Coverage Control for Teams of Nonholonomic Agents, in 47th IEEE Conf. on Decision and Control, 2008. [PDF]
- John J. Enright, Efficient Routing of Multi-Vehicle Systems: limited sensing and nonholonomic motion constraints, PhD Thesis, University of California, Los Angeles, Mechanical and Aerospace Engineering Department, June 2008. [PDF]
- J.J. Enright and E. Frazzoli, The Stochastic Traveling Salesman Problem for the Reeds-Shepp Car and the Differential Drive Robot, In IEEE Conf. on Decision and Control, 2006. [PDF]
- J.J. Enright, E. Frazzoli, K. Savla, and F. Bullo, On Multiple UAV Routing with Stochastic Targets: Performance Bounds and Algorithms, In Proc. of the AIAA Conf. on Guidance, Navigation, and Control, San Francisco, CA, August 2005. [PDF]
- J.J. Enright and E. Frazzoli, UAV Routing in a Stochastic, Time-Varying Environment, In Proc. of the IFAC World Congress, Prague, Czech Republic, July 2005. [PDF]