2278. A Lagrangian Decomposition Approach with Heuristic Search for Multi-Agent Path Planning in Moving Target Environments
Invited abstract in session TD-2: Integer Programming II, stream Discrete and Combinatorial Optimization.
Thursday, 14:30-16:00Room: H4
Authors (first author is the speaker)
| 1. | Wataru Murata
|
| Data Science Technology Department, Kawasaki Heavy Industries, Ltd. |
Abstract
Multi-agent path planning (MAPP) is integral to the fleet management of autonomous vehicles and robots across domains such as surveillance, search, and delivery. A key challenge in various applications lies in addressing the complex issue of moving targets, along with undefined terminal positions for agents, limited time availability, and continuous-valued delivery amounts. This study proposes a Lagrangian decomposition approach to solve a mixed integer second order cone programming (MISOCP) problem that incorporates these complexities. The problem is decomposed into subproblems for each agent by applying the Lagrangian relaxation technique. The proposed approach then iteratively performs subproblem optimization, feasible solution construction, and Lagrange multiplier update until a termination condition is met. A heuristic search is employed during the feasible solution construction to accelerate the convergence of the upper bound, leveraging the results from the subproblem optimization. Additionally, the Lagrange multipliers are initialized using a heuristic solution to obtain a tighter lower bound. Numerical experiments demonstrate that the proposed approach outperforms a direct method, highlighting its potential for solving complex MAPP problems.
Keywords
- Decomposition Methods
- Mixed-Integer Programming
- Routing
Status: accepted
Back to the list of papers