Search and exploration capabilities are essential for robots to inspect hazardous areas, support scientific expeditions in extreme environments, and potentially save human lives in natural disasters. The variability of scale in these problems requires robots to reason about time alongside their dynamics and sensor capabilities to effectively assess and explore for information. Recent advances in ergodic search methods have shown promise in supporting trajectory planning for exploration in continuous, multiscale environments with dynamics consideration. However, these methods are still limited by their inability to effectively reason about and adapt the time to explore in response to their environment. This ability is crucial for adapting exploration to variable-resolution information-gathering tasks. To address this limitation, this paper poses the time-optimal ergodic search problem and investigates solutions for fast, multiscale, and adaptive robotic exploration trajectories. The problem is formulated as a minimum-time problem with an ergodic inequality constraint whose upper bound specifies the amount of coverage needed. We show the existence of optimal solutions using Pontryagin’s conditions of optimality, and we demonstrate effective, minimum-time coverage numerically through a direct transcription optimization approach. The efficacy of the approach in generating time-optimal search trajectories is demonstrated in simulation under several nonlinear dynamic constraints, and in a physical experiment using a drone in a cluttered environment. We find that constraints such as obstacle avoidance are readily integrated into our formulation, and we show through an ablation study the flexibility of search capabilities at various scales. Last, we contribute a receding-horizon formulation of time-optimal ergodic search for sensor-driven information-gathering and demonstrate improved adaptive sampling capabilities in localization tasks.
AbrahamIMurpheyTD (2018) Decentralized ergodic control: distribution-driven sensing and exploration for multiagent systems. IEEE Robotics and Automation Letters3(4): 2987–2994.
2.
AbrahamIMavrommatiAMurpheyT (2018) Data-driven measurement models for active localization in sparse environments. In Proceedings of robotics: science and systems, Pittsburgh, PA, July 10–July 14, 2023.
3.
AbrahamIPrabhakarAMurpheyTD (2021) An ergodic measure for active learning from equilibrium. IEEE Transactions on Automation Science and Engineering18(3): 917–931.
4.
AdamsALSchmidtTANewgardCD, et al. (2007) Search is a time-critical event: when search and rescue missions may become futile. Wilderness and Environmental Medicine18(2): 95–101.
5.
AgrawalASreenathK (2017) Discrete control barrier functions for safety-critical control of discrete systems with application to bipedal robot navigation. Robotics: Science and Systems. Cambridge, MA, USA: MIT Press, Vol. 13.
6.
AmesADCooganSEgerstedtM, et al. (2019) Control barrier functions: theory and applications. In 2019 18th European control conference (ECC), Naples, 25–28 June 2019, 3420–3431. IEEE.
7.
ApplegateDLBixbyREChvátalV, et al. (2011) The traveling salesman problem. In The Traveling Salesman Problem. Princeton, NJ: Princeton University Press.
8.
AraujoJSujitPSousaJB (2013) Multiple UAV area decomposition and coverage. In 2013 IEEE symposium on computational intelligence for security and defense applications (CISDA), Singapore, 16–19 April 2013, 30–37. IEEE.
9.
BaghliFZbakkaliLELakhalY (2017) Optimization of arm manipulator trajectory planning in the presence of obstacles by ant colony algorithm. Procedia Engineering181: 560–567.
10.
BähnemannRLawranceNChungJJ, et al. (2021) Revisiting boustrophedon coverage path planning as a generalized traveling salesman problem. In Field and service robotics: results of the 12th international conference, Berlin, 277–290. Springer.
11.
BoumanAOttJKimSK, et al. (2022) Adaptive coverage path planning for efficient exploration of unknown environments. In 2022 IEEE/RSJ international conference on intelligent robots and systems (IROS), Kyoto, 23–27 October 2022, 11916–11923. DOI: 10.1109/IROS47612.2022.9982287.
12.
BreitenmoserASchwagerMMetzgerJC, et al. (2010) Voronoi coverage of non-convex environments with a group of networked robots. In 2010 IEEE international conference on robotics and automation, Anchorage, AK, 03–07 May 2010, 4982–4989. IEEE.
13.
CabreiraTMBrisolaraLBFerreira JrPR (2019) Survey on coverage path planning with unmanned aerial vehicles. Drones3(1): 4.
14.
ChenWKhardonRLiuL (2022) AK: attentive kernel for information gathering. In Proceedings of robotics: science and systems. New York, NY, USA.
15.
ChinWPNtafosS (1986) Optimum watchman routes. In Proceedings of the second annual symposium on computational geometry, Richardson, TX, 24–33.
16.
ChosetH (2001) Coverage for robotics–a survey of recent results. Annals of Mathematics and Artificial Intelligence31: 113–126.
17.
CieslewskiTKaufmannEScaramuzzaD (2017) Rapid exploration with multi-rotors: a frontier selection method for high speed flight. In 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS), Vancouver, September 24–28, 2017, 2135–2142. DOI: 10.1109/IROS.2017.8206030.
18.
CoffinHAbrahamISartorettiG, et al. (2022) Multi-agent dynamic ergodic search with low-information sensors. In 2022 international conference on robotics and automation (ICRA), Philadelphia, PA, 23–27 May 2022, 11480–11486. IEEE.
19.
DaiRFotedarSRadmaneshM, et al. (2018) Quality-aware UAV coverage and path planning in geometrically complex environments. Ad Hoc Networks73: 95–105.
20.
Dal BiancoNBertolazziEBiralF, et al. (2019) Comparison of direct and indirect methods for minimum lap time optimal control problems. Vehicle System Dynamics57(5): 665–696.
21.
De La TorreGFlaßkampKPrabhakarA, et al. (2016) Ergodic exploration with stochastic sensor dynamics. In 2016 American control conference (ACC), Boston, MA, 06–08 July 2016, 2971–2976. IEEE.
22.
De PinhoM (1997) A maximum principle for optimal control problems with equality and inequality constraints. In Proceedings of the 36th IEEE conference on decision and control, volume 2, San Diego, CA, 12 December 1997, Vol. 2, 1403–1404. DOI: 10.1109/CDC.1997.657658.
23.
DongDEBergerHPAbrahamI (2023) Time optimal ergodic search. In Proceedings of robotics: science and systems. Daegu, Republic of Korea.
24.
DresselLKochenderferMJ (2018) On the optimality of ergodic trajectories for information gathering tasks. In 2018 annual American control conference (ACC), Milwaukee, WI, 27–29 June 2018, 1855–1861. IEEE. https://ieeexplore.ieee.org/document/8430857/.
25.
DuYChenY (2022) Time optimal trajectory planning algorithm for robotic manipulator based on locally chaotic particle swarm optimization. Chinese Journal of Electronics31(5): 906–914.
26.
DuchiJHazanESingerY (2011) Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research12(7): 2121–2159.
27.
EmeryAFNenarokomovAV (1998) Optimal experiment design. Measurement Science and Technology9(6): 864–876.
28.
FazliPDavoodiAPasquierP, et al. (2010) Complete and robust cooperative robot area coverage with limited range. In 2010 IEEE/RSJ international conference on intelligent robots and systems, Taipei, 18–22 October 2010, 5577–5582. IEEE.
FoxDHightowerJLiaoL, et al. (2003) Bayesian filtering for location estimation. IEEE pervasive computing2(3): 24–33.
31.
FriedenBR (2004) Science from Fisher Information: A Unification. Cambridge, MA: Cambridge University Press.
32.
GalceranECarrerasM (2013) A survey on coverage path planning for robotics. Robotics and Autonomous Systems61(12): 1258–1276.
33.
HowardAMatarićMJSukhatmeGS (2002) Mobile sensor network deployment using potential fields: a distributed, scalable solution to the area coverage problem. In Distributed Autonomous Robotic Systems 5. Berlin: Springer, 299–308.
34.
KimJJLeeJJ (2015) Trajectory optimization with particle swarm optimization for manipulator motion planning. IEEE Transactions on Industrial Informatics11(3): 620–631.
35.
KimDHShinS (2006) Local path planning using a new artificial potential function composition and its analytical design guidelines. Advanced Robotics20(1): 115–135.
36.
KleshAGirardAKabambaP (2008) Real-time path planning for time-optimal exploration. In AIAA guidance, navigation and control conference and exhibit, Honolulu, Hawaii, 18 August 2008–21 August 2008, 6982.
37.
KoppRE (1962) Pontryagin maximum principle. In Mathematics in Science and Engineering, Volume 5. Amsterdam: Elsevier, 255–279.
38.
KuhnHTuckerA (1951) Nonlinear Programming in Proceedings of 2nd Berkeley Symposium. Berkeley: University of California Press, 481–492. [Google Scholar].
39.
LaSalleJP (2016) The time optimal control problem, In. Contributions to the theory of nonlinear oscillations. New Jersey: Princeton University Press Princeton, 1–24.
40.
LerchCDongDAbrahamI (2023) Safety-critical ergodic exploration in cluttered environments via control barrier functions. In International conference on robotics and automation (ICRA), London, 29 May 2023–02 June 2023.
41.
LiPYangCWangR, et al. (2020) A high-efficiency, information-based exploration path planning method for active simultaneous localization and mapping. International Journal of Advanced Robotic Systems17(1): 172988142090320.
MathewGMezićI (2011) Metrics for ergodicity and design of ergodic dynamics for multi-agent systems. Physica D: Nonlinear Phenomena240(4-5): 432–442.
44.
MavrommatiATzorakoleftherakisEAbrahamI, et al. (2017) Real-time area coverage and target localization using receding-horizon ergodic exploration. IEEE Transactions on Robotics34(1): 62–80.
45.
MayerSLischkeLWoźniakPW (2019) Drones for search and rescue. In 1st International Workshop on Human-Drone Interaction. Pune: FlytBase.
46.
MillerLMMurpheyTD (2013) Trajectory optimization for continuous ergodic exploration. In 2013 American control conference, Washington, DC, 17–19 June 2013, 4196–4201. IEEE.
47.
MillerLMSilvermanYMacIverMA, et al. (2015) Ergodic exploration of distributed information. IEEE Transactions on Robotics32(1): 36–52.
48.
MukkamalaMCHeinM (2017) Variants of rmsprop and adagrad with logarithmic regret bounds. In International Conference on Machine Learning, Sydney, NSW, August 6–11, 2017, 2545–2553.
49.
NenchevVRaischJ (2013) Towards time-optimal exploration and control by an autonomous robot. In 21st Mediterranean conference on control and automation, Platanias, 25–28 June 2013, 1236–1241. IEEE.
50.
O’rourkeJ (1987) Art Gallery Theorems and Algorithms. Oxford: Oxford University Press, Vol. 57.
51.
PatelSHariharanSDhulipalaP, et al. (2021) Multi-agent ergodic coverage in urban environments. In 2021 IEEE international conference on robotics and automation (ICRA), Xi’an, 30 May 2021–05 June 2021, 8764–8771. IEEE.
52.
PaullLSaeediSSetoM, et al. (2012) Sensor-driven online coverage planning for autonomous underwater vehicles. IEEE18(6): 1827–1838.
53.
PosaMCantuCTedrakeR (2014) A direct method for trajectory optimization of rigid bodies through contact. The International Journal of Robotics Research33(1): 69–81.
54.
PotraFAWrightSJ (2000) Interior-point methods. Journal of Computational and Applied Mathematics124(1-2): 281–302.
55.
PrabhakarAAbrahamITaylorA, et al. (2020) Ergodic specifications for flexible swarm control: from user commands to persistent adaptation. In Proceedings of robotics: science and systems. Corvalis, Oregon, USA.
56.
PratissoliFCapelliBSabattiniL (2022) On coverage control for limited range multi-robot systems. In 2022 IEEE/RSJ international conference on intelligent robots and systems (IROS), Kyoto, 23–27 October 2022, 9957–9963. IEEE.
57.
PreissJAHönigWSukhatmeGS, et al. (2017) Crazyswarm: a large nano-quadcopter swarm. In: IEEE international conference on robotics and automation (ICRA), Singapore, 29 May 2017–03 June 2017, 3299–3304. DOI:10.1109/ICRA.2017.7989376. IEEE. https://github.com/USC-ACTLab/crazyswarm.
58.
ReynoldsNMecklPH (2001) Hybrid optimization scheme for time-optimal control. In Proceedings of the 2001 American control conference. (Cat. No. 01CH37148), volume 5, Arlington, VA, 25–27 June 2001, 3421–3426. IEEE.
59.
RomeroAPenickaRScaramuzzaD (2022) Time-optimal online replanning for agile quadrotor flight. IEEE Robotics and Automation Letters7(3): 7730–7737.
60.
SartorettiGRaoAChosetH (2021) Spectral-based distributed ergodic coverage for heterogeneous multi-agent search. International Symposium Distributed Autonomous Robotic Systems. Berlin, Germany: Springer, 227–241.
61.
SchmidLPanticMKhannaR, et al. (2020) An efficient sampling-based method for online informative path planning in unknown environments. IEEE Robotics and Automation Letters5(2): 1500–1507. DOI: 10.1109/LRA.2020.2969191.
62.
ScottSEReddTCKuznetsovL, et al. (2009) Capturing deviation from ergodicity at different scales. Physica D: Nonlinear Phenomena238(16): 1668–1679.
63.
ShettySSilvérioJCalinonS (2021) Ergodic exploration using tensor train: applications in insertion tasks. IEEE Transactions on Robotics38(2): 906–921.
64.
SiligardiLPaneratiJKaufmannM, et al. (2019) Robust area coverage with connectivity maintenance. In 2019 international conference on robotics and automation (ICRA), Montreal, QC, 20–24 May 2019, 2202–2208. IEEE.
65.
SilvermanYMillerLMMacIverMA, et al. (2013) Optimal planning for information acquisition. In 2013 IEEE/RSJ international conference on intelligent robots and systems, Tokyo, 03–07 November 2013, 5974–5980. IEEE.
66.
SungYChenZDasJ, et al. (2023) A survey of decision-theoretic approaches for robotic environmental monitoring. Foundations and Trends in Robotics11(4): 225–315.
67.
TabakDKuoBC (1971) Optimal Control by Mathematical Programming. London: SRL Publishing Company.
68.
TianLCollinsC (2004) An effective robot trajectory planning method using a genetic algorithm. Mechatronics14(5): 455–470.
69.
TranzattoMMikiTDharmadhikariM, et al. (2022) Cerberus in the darpa subterranean challenge. Science Robotics7(66): eabp9742.
70.
UlrichIMondadaFNicoudJD (1997) Autonomous vacuum cleaner. Robotics and Autonomous Systems19(3-4): 233–245.
71.
WangWTaoQCaoY, et al. (2020) Robot time-optimal trajectory planning based on improved cuckoo search algorithm. IEEE Access8: 86923–86933.
72.
ZelinskyAJarvisRAByrneJ, et al. (1993) Planning paths of complete coverage of an unstructured environment by a mobile robot. Proceedings of international conference on advanced robotics13: 533–538.
73.
ZengJZhangBSreenathK (2021) Safety-critical model predictive control with discrete-time control barrier function. In 2021 American control conference (ACC), New Orleans, LA, 25–28 May 2021, 3882–3889. IEEE.
74.
ZhouBZhangYChenX, et al. (2021) Fuel: fast UAV exploration using incremental frontier structure and hierarchical planning. IEEE Robotics and Automation Letters6(2): 779–786. DOI: 10.1109/LRA.2021.3051563.
