非同期マルチエージェントアーキテクチャ(A-teams)を用いた異種無人車両システムの配送計画問題の解法
Solving Vehicle Routing Problem for unmanned heterogeneous vehicle systems using Asynchronous Multi-Agent Architecture (A-teams)
UAVがUGV上で充電しながら広範囲を調査する問題に対し、二段階最適化を提案。外側でUGV経路をパラメータ化し、内側で容量・時間窓・訪問放棄を考慮した配送計画問題を解く。UGVパラメータ調整に遺伝的アルゴリズムと非同期マルチエージェント(A-teams)を比較し、A-teamsが2-3倍高速化を実現。
著者: Subramanian Ramasamy, Md Safwan Mondal, Pranav A. Bhounsule
分類: cs.RO, cs.DC, cs.MA
原文アブストラクト
Fast moving but power hungry unmanned aerial vehicles (UAVs) can recharge on slow-moving unmanned ground vehicles (UGVs) to survey large areas in an effective and efficient manner. In order to solve this computationally challenging problem in a reasonable time, we created a two-level optimization heuristics. At the outer level, the UGV route is parameterized by few free parameters and at the inner level, the UAV route is solved by formulating and solving a vehicle routing problem with capacity constraints, time windows, and dropped visits. The UGV free parameters need to be optimized judiciously in order to create high quality solutions. We explore two methods for tuning the free UGV parameters: (1) a genetic algorithm, and (2) Asynchronous Multi-agent architecture (Ateams). The A-teams uses multiple agents to create, improve, and destroy solutions. The parallel asynchronous architecture enables A-teams to quickly optimize the parameters. Our results on test cases show that the A-teams produces similar solutions as genetic algorithm but with a speed up of 2-3 times.
