Decentralized Coordination in RoboCup Rescue.
Emergency responders are faced with a number of significant challenges when managing major disasters. First, the number of rescue tasks posed is usually larger than the number of responders (or agents) and the resources available to them. Second, each task is likely to require a different level of effort in order to be completed by its deadline. Third, new tasks may continually appear or disappear from the environment, thus requiring the responders to quickly recompute their allocation of resources. Fourth, forming teams or coalitions of multiple agents from different agencies is vital since no single agency will have all the resources needed to save victims, unblock roads and extinguish the fires which might erupt in the disaster space. Given this, coalitions have to be efficiently selected and scheduled to work across the disaster space so as to maximize the number of lives and the portion of the infrastructure saved. In particular, it is important that the selection of such coalitions should be performed in a decentralized fashion in order to avoid a single point of failure in the system. Moreover, it is critical that responders communicate only locally given they are likely to have limited battery power or minimal access to long-range communication devices. Against this background, we provide a novel decentralized solution to the coalition formation process that pervades disaster management. More specifically, we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a coalition formation with spatial and temporal constraints (CFST) problem where agents form coalitions to complete tasks, each with different demands. To design a decentralized algorithm for CFST, we formulate it as a distributed constraint optimization problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralized message-passing solution. We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment. In empirical evaluations, our algorithm is shown to generate better solutions than other decentralized algorithms used for this problem. [ABSTRACT FROM PUBLISHER]/nCopyright of Computer Journal is the property of Oxford University Press / USA and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
First, we compare the effectiveness of F-Max-Sum in maximizing the number of tasks completed compared with a number of other strategiesIn the next, we evaluate how efficient F-Max-Sum is compared with Max- Sum in dealing with changes in the set of tasks.
Algorithm development, empirical evaluation
Number of completed tasks
We introduce CFST as a general model for the task allocation problem faced by ambulances and fire brigades in RCR and in disaster management at large. Thus, our model captures most task allocation problems that involve some form of temporal (i.e. deadline and time to complete a task) and spatial constraints (i.e. positions of agents and tasks) such as those existing in logistics planning or crew scheduling [7]. Given this, we define both optimal and approximate solutions for the problem. (ii) We develop a new DCOP formulation for the approximate solution to the CFST problem and solve it using a novel decentralized algorithm based on the state-of-the-art Max-Sum algorithm [8]. (iii) We show that our algorithm can complete 10% more tasks than the current best decentralized algorithm for this problem (on average) and requires up to 91% fewer messages and 99% less computation than the standard Max-Sum algorithm in order to converge to a solution.
Artificial data. No real world scenario application.
In this paper, we have modelled the RCR domain in terms of a CFST constraints. We then provided a DCOP formulation of the problem and showed how to solve it using the Max- Sum algorithm. On the basis of this, we then developed the novel F-Max-Sum algorithm that improves upon Max-Sum to deal with disruptions in its underlying factor graph more effectively. In so doing, we have provided the first full solution to the problem of decentralized coalition formation that pervades disaster management. Our solution is also one that is able to efficiently adapt to a dynamic environment.
we provide a novel decentralized solution to the coalition formation process that pervades disaster management.we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a coalition formation with spatial and temporal constraints (CFST) problem where agents form coalitions to complete tasks, each with different demands.we formulate it as a distributed constraint optimization problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralized message-passing solution.We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment.In empirical evaluations, our algorithm is shown to generate better solutions than other decentralized algorithms used for this problem.
 |
Die Portfolio of Solutions Website wurde ursprünglich im Rahmen des DRIVER+ Projekts entwickelt. Heute wird das Service von der AIT Austrian Institute of Technology GmbH. zum Nutzen des europäischen Krisenmanagements betrieben. PoS ist vom Disaster Competence Network Austria (DCNA) sowie von den H2020-Projekten STAMINA und TeamAware befürwortet und unterstützt. |