Design of Task Assignments based on Ordering and Time Window Constraints for RoboCupRescue Agents

The RoboCupRescue Simulation (RRS) is a project that uses multi-agent systems to address real-world problems. RRS needs to perform an optimal task assignment for various disaster relief teams (agents) to minimize the damage caused by disasters. In previous studies, the RRS task assignment problem was modeled as a distributed constraint optimization problem (DCOP) and its effectiveness was confirmed. The DCOP can handle cooperative actions by one type of agent, but it cannot handle cooperative actions by multiple types of agents. To achieve this cooperative behavior, task assignment must take into account the order constraints of multiple types of tasks. It is also difficult for the DCOP to consider the dynamic environment. RRS should consider the dynamic environment because disaster conditions change over time. To consider the dynamic environment, task assignment must take into account the time window constraints of the task. Therefore, the objective of this study is to realize a disaster relief agent that performs task assignment considering the task order and time window constraints for RRS. First, the task assignment problem of RRS was modeled as a layered DCOP (L-DCOP) and L-DCOP was applied to RRS. Next, the rescue abilities and behavior of the L-DCOP agent applying the L-DCOP were compared with those of the DCOP agent applying the DCOP. The results confirmed the effectiveness of the L-DCOP agent and its ability to perform given the constraints of the task.