Stepwise Large-Scale Multi-Agent Task Planning Using Neighborhood Search

This letter presents a novel stepwise multi-agent task planning method that incorporates neighborhood search to address large-scale problems, thereby reducing computation time. With an increasing number of agents, the search space for task planning expands exponentially. Hence, conventional methods aiming to find globallyoptimalsolutions,especiallyforsomelarge-scaleproblems, incur extremely high computational costs and may even fail. In this letter, the proposed method easily achieves the goals of multi-agent task planning by solving an initial problem using a minimal number of agents. Subsequently, tasks are reallocated among all agents based on this solution and the solutions are iteratively optimized using a neighborhood search. While aiming to find a near-optimal solution rather than an optimal one, the method substantially reduces the time complexity of searching to a polynomial level. Moreover,theeffectivenessoftheproposedmethodisdemonstrated by solving some benchmark problems and comparing the results obtained using the proposed method with those obtained using other state-of-the-art methods.