Mixed Integer Programming for Time-Optimal Multi-Robot Coverage Path Planning with Efficient Heuristics
We investigate time-optimal Multi-Robot Coverage Path Planning (MCPP) for both unweighted and weighted terrains, which aims to minimize the coverage time, defined as the maximum travel time of all robots. Specifically, we focus on a reduction from MCPP to Min-Max Rooted Tree Cover (MMRTC). For the first time, we propose a Mixed Integer Programming (MIP) model to optimally solve MMRTC, resulting in an MCPP solution with a coverage time that is provably at most four times the optimal. Moreover, we propose two suboptimal yet effective heuristics that reduce the number of variables in the MIP model, thus improving its efficiency for large-scale MCPP instances. We show that both heuristics result in reduced-size MIP models that remain complete (i.e., guaranteed to find a solution if one exists) for all MMRTC instances. Additionally, we explore the use of model optimization warm-startup to further improve the efficiency of both the original MIP model and the reduced-size MIP models. We validate the effectiveness of our MIP-based MCPP planner through experiments that compare it with two state-of-the-art MCPP planners on various instances, demonstrating a reduction in the coverage time by an average of 27.65% and 23.24% over them, respectively.
Code (2)
Tasks
Model OptimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Trajectory planning with a dynamic obstacle clustering strategy using Mixed-Integer Linear Programming
In this paper we propose a technique that assigns obstacles to clusters used for collision avoidance via Mixed-Integer Programming. This strategy enables a reduction in the number of binary variables used for collision a…
ClusteringCollision AvoidanceModel Predictive ControlTrajectory PlanningCombining Graph Attention Networks and Distributed Optimization for Multi-Robot Mixed-Integer Convex Programming
In this paper, we develop a fast mixed-integer convex programming (MICP) framework for multi-robot navigation by combining graph attention networks and distributed optimization. We formulate a mixed-integer optimization …
Distributed OptimizationGraph AttentionMotion PlanningRobot NavigationFuzzy Mixed Integer Linear Programming for Air Vehicles Operations Optimization
Multiple Air Vehicles (AVs) to prosecute geographically dispersed targets is an important optimization problem. Associated multiple tasks viz., target classification, attack and verification are successively performed on…
SchedulingLearning the cost-to-go for mixed-integer nonlinear model predictive control
Application of nonlinear model predictive control (NMPC) to problems with hybrid dynamical systems, disjoint constraints, or discrete controls often results in mixed-integer formulations with both continuous and discrete…
Model Predictive ControlPredictionOutlier-immune Data-driven Linear Power Flow Model Construction via Mixed-Integer Programming
The common approaches to construct a data-driven linear power flow (DD-LPF) model cannot completely eliminate the adverse impacts of outliers in a training dataset. In this letter, a novel outlier-immune DD-LPF model con…