| Presentation | 2021-08-27 Combining Multiagent Reinforcement Learning and Discrete Event Modeling for Pathfinding on a Non-Grid Graph Shiyao Ding, Hideki Aoyama, Donghui Lin, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this report, we study a new multiagent path finding (MAPF) problem where multiple agents move on a non-grid graph with the goal of minimizing the traveling time summation of all agents. Multiagent reinforcement learning (MARL), which is effective to solve the traditional MAPF problems on a grid graph, can be applied in this new problem. However, considering the following two issues brought by the non-grid feature: 1) the action space is large where the agent actions are the nodes it can arrive rather than only four directions (up, down, right, left); 2) the state space is large where the agent can stay at edges rather than only nodes, MARL cannot learn optimal paths for all agents effectively. As for solving this problem, we propose a novel MARL algorithm by importing a discrete event model to MARL. Specifically, one part of agents’ pathfinding are solved by the predefined rules. Then, based on those pathfinding results, the other part of agents are trained by MARL further, which can accelerate the learning process. Finally, the experiment results show the effectiveness of our proposed method than some existing algorithms. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Multi-agent PathfindingMulti-agent reinforcement learningDrone delivery |
| Paper # | SWIM2021-15,SC2021-13 |
| Date of Issue | 2021-08-20 (SWIM, SC) |
| Conference Information | |
| Committee | SWIM / SC |
|---|---|
| Conference Date | 2021/8/27(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Kenji Saotome(Hosei Univ.) / Shinji Kikuchi(NIMS) |
| Vice Chair | Akihiro Hayashi(Shizuoka Inst. of Science and Tech.) / Yoji Yamato(NTT) / Kosaku Kimura(Fujitsu Lab.) |
| Secretary | Akihiro Hayashi(Tokyo Univ. of Science) / Yoji Yamato(Osaka Sangyo Univ.) / Kosaku Kimura(Kobe Univ.) |
| Assistant | Tsukasa Kudo(Shizuoka Inst. of Science and Tech.) / Kokichi Tsuji(Aichi Pref. Univ.) / Shin Tezuka(Hitachi) / Takao Nakaguchi(KCGI) |
| Paper Information | |
| Registration To | Technical Committee on Software Interprise Modeling / Technical Committee on Service Computing |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Combining Multiagent Reinforcement Learning and Discrete Event Modeling for Pathfinding on a Non-Grid Graph |
| Sub Title (in English) | |
| Keyword(1) | Multi-agent PathfindingMulti-agent reinforcement learningDrone delivery |
| 1st Author's Name | Shiyao Ding |
| 1st Author's Affiliation | Kyoto University(Kyoto Univ.) |
| 2nd Author's Name | Hideki Aoyama |
| 2nd Author's Affiliation | Panasonic Corporation(Panasonic) |
| 3rd Author's Name | Donghui Lin |
| 3rd Author's Affiliation | Kyoto University(Kyoto Univ.) |
| Date | 2021-08-27 |
| Paper # | SWIM2021-15,SC2021-13 |
| Volume (vol) | vol.121 |
| Number (no) | SWIM-156,SC-157 |
| Page | pp.pp.13-17(SWIM), pp.13-17(SC), |
| #Pages | 5 |
| Date of Issue | 2021-08-20 (SWIM, SC) |