グラフ埋め込みによる複雑環境でのマルチロボット経路計画
Multi-Robot Path Planning in Complex Environments via Graph Embedding
ペブルグラフとメッシュ最適化を用いて、複雑な形状の環境にマルチエージェント経路計画を適用する手法を提案し、高い空間被覆率とロボット密度を達成した。
著者: Xifeng Gao, Zherong Pan, Ruiqi Ni
分類: cs.RO
原文アブストラクト
We propose an approach to solve multi-agent path planning (MPP) problems for complex environments. Our method first designs a special pebble graph with a set of feasibility constraints, under which MPP problems have feasibility guarantee. We further propose an algorithm to greedily improve the optimality of planned MPP solutions via parallel pebble motions. As a second step, we develop a mesh optimization algorithm to embed our pebble graph into arbitrarily complex environments. We show that the feasibility constraints of a pebble graph can be converted into differentiable geometric constraints, such that our mesh optimizer can satisfy these constraints via constrained numerical optimization. We have evaluated the effectiveness and efficiency of our method using a set of environments with complex geometries, on which our method achieves an average of 99.0% free-space coverage and 30.3% robot density within hours of computation on a desktop machine.
