X Invited talk at International Workshop on Symbolic-Neural Learning (SNL) 2022 July 8, 2022 7/8/2022 SNL 2022 | (c) 2022 OMRON SINIC X. All Rights Reserved. 1
for a single agent from its start to goal • While avoiding collisions with obstacles Multi-agent path planning • Find paths for a team of agents with e.g., lowest possible sum of costs • While avoiding collisions with obstacles and other agents 7/8/2022 SNL 2022 | (c) 2022 OMRON SINIC X. All Rights Reserved. 2
it collides with obstacles. This action is apparently good as it brings us closer to the goal. But there's a dead end ahead. This action should be the best as it brings us to the goal while avoiding dead ends. How can we get AI to think this way? Start Goal 7/8/2022 SNL 2022 | (c) 2022 OMRON SINIC X. All Rights Reserved. 3
studied • Design how to plan in a top-down fashion Machine learning? • Has greatly advanced recently • Learn how to plan in a bottom-up fashion 7/8/2022 SNL 2022 | (c) 2022 OMRON SINIC X. All Rights Reserved. 4
machine learning • Key idea: Learning representations of problem instances that are effective for path planning algorithms 7/8/2022 SNL 2022 | (c) 2022 OMRON SINIC X. All Rights Reserved. 5 Neural network Transforms the representation of problem instance Problem instance Path planning algorithm Solves the transformed problem instance Path
Tatsunori Taniai1* *Equal contribution Mohammadamin1 Barekatain Mai Nishimura1 Asako Kanezaki2 1OMRON SINIC X 2Tokyo Institute of Technology 7/8/2022 SNL 2022 | (c) 2022 OMRON SINIC X. All Rights Reserved. 7
to goal • Completeness: Able to find a solution path if one exists • Optimality: Able to find a shortest path • With machine learning, can we improve the performance and generalizability of A* in a principled fashion? 7/8/2022 SNL 2022 | (c) 2022 OMRON SINIC X. All Rights Reserved. 8
7/8/2022 SNL 2022 | (c) 2022 OMRON SINIC X. All Rights Reserved. 11 G G Select Expand Node selection • Finding nodes from candidates for constructing a shortest path • Softmax + discretized activation Node expansion • Adding neighboring nodes to the list of next selection candidates • Fixed convolution + binary masking Select … G Candidates History
ground-truth path 7/8/2022 SNL 2022 | (c) 2022 OMRON SINIC X. All Rights Reserved. 12 G G Select Search history Ground-truth path Loss Loss: L1 between search history and ground-truth path • Backpropagated thorugh every search step to the encoder • Making guidance maps to indicate nodes to/not to explore
Planning in Continuous Spaces (AAMAS 2022) Keisuke Okumura1,2 Ryo Yonetani1 Mai Nishimura1 Asako Kanezaki2 1OMRON SINIC X 2Tokyo Institute of Technology 7/8/2022 SNL 2022 | (c) 2022 OMRON SINIC X. All Rights Reserved. 15
OMRON SINIC X. All Rights Reserved. 16 MAPP on the grid map (aka MAPF) • Limit agent locations and possible actions • Has long been studied for decades MAPP in continuous spaces (our focus) • Need to construct a graph (roadmap) that approximates the space • Has long been recognized as challenging and still relatively unexplored
2022 OMRON SINIC X. All Rights Reserved. 17 Sparser roadmaps • Can be constructed faster • May produce sub-optimal solutions or fail to solve the problem Denser roadmaps • Can produce higher-quality solutions • Require higher computational cost for construction and pathfinding
each agent while being aware of other agents • Timed: Roadmaps are extended over the time axis to generate “timed” paths 7/8/2022 SNL 2022 | (c) 2022 OMRON SINIC X. All Rights Reserved. 18 Roadmap for agent #0 Roadmap for agent #1 Roadmap for agent #2
of possible next actions of each agent from the observations of others • Conditional VAE to learn the distribution • Attention mechanism to deal with variable number of agents 7/8/2022 SNL 2022 | (c) 2022 OMRON SINIC X. All Rights Reserved. 19 … Attention MLP MLP MLP Features for the self Features from other agents
next actions using the learned CVAE and random sampler • Solving MAPP: Performing any multi-agent pathfinding algorithm on the constructed CTRMs 7/8/2022 SNL 2022 | (c) 2022 OMRON SINIC X. All Rights Reserved. 20 Constructing CTRMs New problem instance CTRMs Solution Solve MAPP
of problem instances that are effective for path planning algorithms • Code available on GitHub • Neural A* | https://github.com/omron-sinicx/neural-astar • CTRM | https://github.com/omron-sinicx/jaxmapp 7/8/2022 SNL 2022 | (c) 2022 OMRON SINIC X. All Rights Reserved. 22 A* Neural A*