Note (General)Navigating a team of agents without colliding plays a crucial role in automation such as fleet operations in warehouses. This dissertation devotes to developing quick, scalable, near-optimal, robust, domain-independent, and end-to-end multi-agent navigation technologies from computational aspects. Multi-agent navigation is a complicated art based on compositing many components from AI and robotics. Therefore, the dissertation decomposes the navigation into three perspectives, i.e., planning, execution, and representation, and respectively overcomes current limitations.The first part studies planning, i.e., how to determine a sequence of actions for agents. The problem is formulated as multi-agent pathfinding (MAPF) that seeks a list of collision-free paths on graphs. The primary challenge is to maintain solvability and quality while suppressing computational effort. On one hand, state-of-the-art optimal MAPF algorithms have difficulty in solving instances with a few hundred agents, within a realistic time. On the other hand, sub-optimal algorithms can cope with massive instances in a short time, meanwhile, such algorithms often lack completeness. To break this tradeoff, the dissertation first presents algorithms with short horizon planning called PIBT and TSWAP, respectively developed for solving MAPF iteratively, and, simultaneous target assignment and collision-free pathfinding. Then, the LaCAM algorithm is presented, which uses short-horizon planning like PIBT as a sub-procedure. LaCAM is complete for MAPF, moreover, it eventually converges to optima. As another direction, the framework of iterative refinement is also presented, which gradually improves the MAPF solutions. Empirically, the dissertation demonstrates that these methods have excellent performance in success rate, computation time, and solution quality, significantly outperforming existing MAPF technologies.The second part studies execution, which asks how to achieve robust plan execution under uncertainties. The primary challenge is, at runtime, how to ensure safety and liveness when something bad happens, unexpected from the planning phase. To this end, the dissertation studies a novel integration style of planning and execution: deliberative offline planning assuming that agents reactively execute the plans. Two examples are presented, called the OTIMAPP and MAPPCF problems, respectively for timing uncertainties and crash faults. For both problems, theoretical foundations and practical approaches are provided. As proofs-of-concept, demonstrations of decentralized execution with robots are included, while ensuring liveness, without any central intervention. Such things can be achieved neither by conventional centralized execution nor by decentralized execution that lacks centralized planners.The third part studies representation, which asks how to model the world for agents. The primary challenge is how to construct small but effective search spaces for subsequent planning. It is necessary to construct a sparse representation (i.e., roadmaps), otherwise, it becomes dramatically difficult to find a combination of plausible paths due to the huge search space. Nevertheless, roadmaps should be sufficiently dense to ensure high planning solvability and better solutions. To break this tradeoff, the dissertation provides two directions. The first is learning to construct sparse roadmaps from planning demonstrations, i.e., data-driven roadmap construction. The second is combining roadmap construction and multi-agent search, making it possible to develop a small but effective search space such that the search is willing to use. Both concepts are extensively tested in various scenarios, revealing their power, i.e., solving more planning instances much faster compared to existing methods.Putting everything together, the dissertation presents a consistent story to realize multi-agent navigation technologies applicable to various domains.
identifier:oai:t2r2.star.titech.ac.jp:50644631
Data Provider (Database)国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）