This paper introduces the correlated arc orienteering problem (CAOP), where the task is to find routes for a team of robots to maximize the collection of rewards associated with features in the environment. These features can be one-dimensional or points in the environment, and can have spatial correlation, i.e., visiting a feature in the environment may provide a portion of the reward associated with a correlated feature. A robot incurs costs as it traverses the environment, and the total cost for its route is limited by a resource constraint such as battery life or operation time. As environments are often large, we permit multiple depots where the robots must start and end their routes. The CAOP generalizes the correlated orienteering problem (COP), where the rewards are only associated with point features, and the arc orienteering problem (AOP), where the rewards are not spatially correlated. We formulate a mixed integer quadratic program (MIQP) that formalizes the problem and gives optimal solutions. However, the problem is NP-hard, and therefore we develop an efficient greedy constructive algorithm. We illustrate the problem with two different applications: informative path planning for methane gas leak detection and coverage of road networks.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    The Correlated Arc Orienteering Problem


    Weitere Titelangaben:

    Springer Proceedings in Advanced Robotics


    Beteiligte:
    LaValle, Steven M. (Herausgeber:in) / O’Kane, Jason M. (Herausgeber:in) / Otte, Michael (Herausgeber:in) / Sadigh, Dorsa (Herausgeber:in) / Tokekar, Pratap (Herausgeber:in) / Agarwal, Saurav (Autor:in) / Akella, Srinivas (Autor:in)

    Kongress:

    International Workshop on the Algorithmic Foundations of Robotics ; 2022 ; , MD, USA June 22, 2022 - June 24, 2022



    Erscheinungsdatum :

    2022-12-15


    Format / Umfang :

    17 pages





    Medientyp :

    Aufsatz/Kapitel (Buch)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Dubins orienteering problem with neighborhoods

    Penicka, Robert / Faigl, Jan / Vana, Petr et al. | IEEE | 2017


    The Team Orienteering Arc Routing Problem

    Archetti, Claudia | Online Contents | 2014


    The Team Orienteering Arc Routing Problem

    Archetti, C. / Speranza, M.G. / Corberan, A. et al. | British Library Online Contents | 2014


    The Multiconstraint Team Orienteering Problem with Multiple Time Windows

    Souffriau, W. / Vansteenwegen, P. / Berghe, G.V. et al. | British Library Online Contents | 2013


    The Multiconstraint Team Orienteering Problem with Multiple Time Windows

    Souffriau, W. / Vansteenwegen, P. / Berghe, G.V. et al. | British Library Conference Proceedings | 2013