2019/09/23 by Park, Jungwon, Junha Kim, Inkyu Jang +4 · 6 citations
Computer Science · Engineering · #Robotic Path Planning Algorithms #Distributed Control Multi-Agent Systems #Maritime Navigation and Safety
paper · pdf · doi:10.48550/arxiv.1909.10219
This paper presents a new efficient algorithm which guarantees a solution for\na class of multi-agent trajectory planning problems in obstacle-dense\nenvironments. Our algorithm combines the advantages of both grid-based and\noptimization-based approaches, and generates safe, dynamically feasible\ntrajectories without suffering from an erroneous optimization setup such as\nimposing infeasible collision constraints. We adopt a sequential optimization\nmethod with \dummy agents to improve the scalability of the algorithm,\nand utilize the convex hull property of Bernstein and relative Bernstein\npolynomial to replace non-convex collision avoidance constraints to convex\nones. The proposed method can compute the trajectory for 64 agents on average\n6.36 seconds with Intel Core i7-7700 @ 3.60GHz CPU and 16G RAM, and it reduces\nmore than 50 % of the objective cost compared to our previous work. We\nvalidate the proposed algorithm through simulation and flight tests.\n