本資料は、掲載誌(URI)等のリンク先にある学位授与機関のWebサイトやCiNii Dissertationsから、本文を自由に閲覧できる場合があります。
博士論文
国立国会図書館館内限定公開
収録元データベースで確認する
国立国会図書館デジタルコレクション
デジタルデータあり
Planning, Execution, Representation, and their Integration for Multiple Moving Agents
- 国立国会図書館永続的識別子
- info:ndljp/pid/12985467
国立国会図書館での利用に関する注記
資料に関する注記
一般注記:
- Navigating a team of agents without colliding plays a crucial role in automation such as fleet operations in warehouses. This dissertation devotes to ...
書店で探す
障害者向け資料で読む
書店で探す
障害者向け資料で読む
書誌情報
この資料の詳細や典拠(同じ主題の資料を指すキーワード、著者名)等を確認できます。
デジタル
- 資料種別
- 博士論文
- 著者・編者
- 奥村, 圭祐Okumura, Keisuke
- 出版年月日等
- 2023-03
- 出版年(W3CDTF)
- 2023-03
- 授与機関名
- 東京工業大学
- 授与年月日
- 2023-03-26
- 授与年月日(W3CDTF)
- 2023-03-26
- 報告番号
- 甲第12460号
- 学位
- 博士(工学)
- 本文の言語コード
- eng
- 件名標目
- 対象利用者
- 一般
- 一般注記
- 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
- 国立国会図書館永続的識別子
- info:ndljp/pid/12985467
- コレクション(共通)
- コレクション(障害者向け資料:レベル1)
- コレクション(個別)
- 国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文
- 収集根拠
- 博士論文(自動収集)
- 受理日(W3CDTF)
- 2023-09-01T22:11:31+09:00
- 記録形式(IMT)
- application/pdf
- オンライン閲覧公開範囲
- 国立国会図書館内限定公開
- デジタル化資料送信
- 図書館・個人送信対象外
- 遠隔複写可否(NDL)
- 可
- 掲載誌(URI)
- 連携機関・データベース
- 国立国会図書館 : 国立国会図書館デジタルコレクション