
Open access
Author
Date
2021-01-11Type
- Master Thesis
ETH Bibliography
yes
Altmetrics
Abstract
Safe planning problem arises in many applications including autonomous driving and exploration scenarios. In this thesis, we focus on a particular case studied for emergency rescue missions. The main challenge of such problems is the computational complexity of handling a dynamic uncertainty, e.g., a spreading hazard. A multi-agent extension can potentially improve the safety of the mission. However, it further increases the computational complexity with the need to consider exponentially many possible task-robot combinations. To overcome these computational issues, we propose a two-stage framework splitting the multi-robot safe planning problem into a low-level single-agent safe planning problem and a high-level multi-robot task allocation problem. For single-agent safe planning, we utilize an efficient Monte-Carlo sampling-based approximation to handle the dynamic uncertainty. For the task allocation problem, we use forward and reverse greedy heuristics to obtain approximate solutions. These algorithms are equipped with provable performance bounds on the safety of the resulting approximate solutions. Finally, we present several case studies on example environments to compare the performance of these different algorithms. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000471229Publication status
publishedPublisher
ETH ZurichSubject
Dynamic programming, dynamic uncertainty, task allocation, greedy algorithms.Organisational unit
09578 - Kamgarpour, Maryam (ehemalig) / Kamgarpour, Maryam (former)
More
Show all metadata
ETH Bibliography
yes
Altmetrics