| Popis: |
In this paper we formulate and solve the concurrent multi-agent search and rescue problem (C-SARP), where a multi-agent system is to concurrently search an area and assist the victims found during the search. It is widely believed that a UAV-system can help saving lives by locating and assisting victims over large inaccessible areas in the initial stages after a disaster, such as an earthquake, flood, or plane crash. In such a scenario, a natural objective is to minimize the loss of lives. Therefore, two types of uncertainties needs to be taken into account, the uncertainty in position of the victims, and the uncertainty in health over time. It is rational to start looking where victims are most likely to be found, such as the reported position of a victim in a life boat with access to a radio, but it is also rational to start looking where loss of lives is most likely to occur, such as the uncertain position of victims swimming in cold water. We show that the proposed C-SARP is NP-hard, and that the two elements of search and rescue should not be decoupled, making C-SARP substantially different from previously studied multi agent problems, including coverage, multi agent travelling salesmen problems and earlier studies of decoupled search and rescue. Finally, we provide an experimental comparison between the most promising algorithms used in the literature to address similar problems, and find that the solutions to the C-SARP reproduce the trajectories recommended in search and rescue manuals for simple problems, but outperform those trajectories in terms of expected survivability for more complex scenarios. |
