The Team Surviving Orienteers problem: routing teams of robots in uncertain environments with survival constraints
The Team Surviving Orienteers problem: routing teams of robots in uncertain environments with survival constraints
复制标题
团队生存定向问题：在具有生存限制的不确定环境中路由机器人团队
DOI：
10.1007/s10514-017-9694-1
复制
发表时间：
2016
影响因子：
3.5
通讯作者：
M. Pavone
中科院分区：
文献类型：
--
作者：
S. Jorgensen;Robert H. Chen;Mark B. Milam;M. Pavone
We study the following multi-robot coordination problem: given a graph, where each edge is weighted by the probability of surviving while traversing it, find a set of paths for K robots that maximizes the expected number of nodes collectively visited, subject to constraints on the probabilities that each robot survives to its destination. We call this the Team Surviving Orienteers (TSO) problem, which is motivated by scenarios where a team of robots must traverse a dangerous environment, such as aid delivery after disasters. We present the TSO problem formally along with several variants, which represent “survivability-aware” counterparts for a wide range of multi-robot coordination problems such as vehicle routing, patrolling, and informative path planning. We propose an approximate greedy approach for selecting paths, and prove that the value of its output is within a factor 1-e-ps/λ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1-e^{-p_s/\lambda }$$\end{document} of the optimum where ps\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p_s$$\end{document} is the per-robot survival probability threshold, and 1/λ≤1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/\lambda \le 1$$\end{document} is the approximation factor of an oracle routine for the well-known orienteering problem. We also formalize an on-line update version of the TSO problem, and a generalization to heterogeneous teams where both robot types and paths are selected. We provide numerical simulations which verify our theoretical findings, apply our approach to real-world scenarios, and demonstrate its effectiveness in large-scale problems with the aid of a heuristic for the orienteering problem.
We study the following multi-robot coordination problem: given a graph, where each edge is weighted by the probability of surviving while traversing it, find a set of paths for K robots that maximizes the expected number of nodes collectively visited, subject to constraints on the probabilities that each robot survives to its destination. We call this the Team Surviving Orienteers (TSO) problem, which is motivated by scenarios where a team of robots must traverse a dangerous environment, such as aid delivery after disasters. We present the TSO problem formally along with several variants, which represent “survivability-aware” counterparts for a wide range of multi-robot coordination problems such as vehicle routing, patrolling, and informative path planning. We propose an approximate greedy approach for selecting paths, and prove that the value of its output is within a factor 1-e-ps/λ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1-e^{-p_s/\lambda }$$\end{document} of the optimum where ps\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p_s$$\end{document} is the per-robot survival probability threshold, and 1/λ≤1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/\lambda \le 1$$\end{document} is the approximation factor of an oracle routine for the well-known orienteering problem. We also formalize an on-line update version of the TSO problem, and a generalization to heterogeneous teams where both robot types and paths are selected. We provide numerical simulations which verify our theoretical findings, apply our approach to real-world scenarios, and demonstrate its effectiveness in large-scale problems with the aid of a heuristic for the orienteering problem.
DOI：
10.1007/978-3-642-37213-1
发表时间：
2013
期刊：
--
影响因子：
--
作者：
M. Tomassini;A. Antonioni;F. Daolio;Pierre Buesser
通讯作者：
M. Tomassini;A. Antonioni;F. Daolio;Pierre Buesser