Files and links (1)
SubmittedarXiv.org - Non-exclusive license to distribute, Open
Journal article
Robust Multiple-Path Orienteering Problem: Securing Against Adversarial Attacks
IEEE TRANSACTIONS ON ROBOTICS, v 39(3), p2060
Jun 2023
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
The multiple-path orienteering problem asks for paths for a team of robots that maximize the total reward collected while satisfying budget constraints on the path length. This problem models many multirobot routing tasks, such as exploring unknown environments and information gathering for environmental monitoring. In this article, we focus on how to make the robot team robust to failures when operating in adversarial environments. We introduce the robust multiple-path orienteering problem (RMOP), where we seek worst case guarantees against an adversary that is capable of attacking at most alpha robots. We consider two versions of this problem: RMOP offline and RMOP online. In the offline version, there is no communication or replanning when robots execute their plans, and our main contribution is a general approximation scheme with a bounded approximation guarantee that depends on alpha and the approximation factor for single-robot orienteering. In particular, we show that the algorithm yields a: 1) constant-factor approximation when the cost function is modular; 2) log factor approximation when the cost function is submodular; and 3) constant-factor approximation when the cost function is submodular, but the robots are allowed to exceed their path budgets by a bounded amount. In the online version, the RMOP is modeled as a two-player sequential game and solved adaptively in a receding horizon fashion based on Monte Carlo tree search. In addition to theoretical analysis, we perform simulation studies for ocean monitoring and tunnel information-gathering applications to demonstrate the efficacy of our approach.
Metrics
Details
- Title
- Robust Multiple-Path Orienteering Problem: Securing Against Adversarial Attacks
- Publication Details
- IEEE TRANSACTIONS ON ROBOTICS, v 39(3), p2060
- Publisher
- IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC; PISCATAWAY
- Grant note
- This work was supported in part by the National Science Foundation under Grant 1943368 and in part by the Office of Naval Research under Grant N000141812829. This paper was recommended for publication by Associate Editor E. Montijano and Editor F. Chaumette upon evaluation of the reviewers' comments.
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Drexel University
- Web of Science ID
- WOS:000926562400001
- Scopus ID
- 2-s2.0-85147291958
- Other Identifier
- 991021861186804721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Robotics