Multi-Agent Action Graph Based Task Allocation and Path Planning Considering Changes in Environment

Task allocation and path planning considering changes in the mobility of robots in the environment allows the robots to efficiently execute tasks with smaller travel times. A lunar base construction is one of the situations in which robots can more efficiently accomplish its goal by taking such environment changes into account when performing tasks. For the construction, we assumed that when a robot executes a task of building a road, the environment changes such that aisles that were unusable before the task become usable post execution. If such changes in environment are considered in advance, the robot can efficiently plan to wait until the environment changes and can move before executing the task. However, previous studies have not considered such changes, resulting in inefficient planning. To solve this problem, we developed a multi-agent action graph that consists of multiple layers and expresses the environment changes associated with task execution in terms of changes in these layers. In this graph, task allocation and path planning are formulated as a combinatorial optimization problem and are optimized using mixed-integer programming. Multi-agent action graphs and the proposed formulation enable efficient planning considering changes in the robots' mobility in advance. Through simulations, we confirmed that the proposed method completed the construction of the lunar base approximately 16.4% earlier than the conventional method, while consuming approximately 16.0% less total energy of the robots.