Mixed integer programming for multi-vehicle path planning

By Tom Schouwenaars, B. De Moor, Eric M. Feron, Jonathan P. How. European Control Conference, 2001

610 citations recorded by the source corpus.

Subfields: Automotive Engineering, Computer Vision and Pattern Recognition, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/a15f2a2f6f6bbc3fffef001dbbf19cfed740013c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Automotive Engineering

In Computer Vision and Pattern Recognition

In Industrial and Manufacturing Engineering

Citations in the corpus

Cellular-Enabled UAV Communication: A Connectivity-Constrained Trajectory Optimization Perspective (2018, background): “It is worth noting that as a related line of research, UAV path planning for dedicated missions without communication performance consideration has been studied in [62]–[65], where the UAV paths were designed such that the UAVs can reach their pre-determined destinations while avoiding collisions wi”
Energy-Efficient UAV Communication With Trajectory Optimization (2016, methodology): “ not speciﬁcally for communication purposes. For instance, mixed-integer linear program (MILP) has been widely applied for trajectory planning for UAV systems to ensure terrain or collision avoidance [22], [23]. In [15], the authors study the energy-aware coverage path planning for aerial imaging pu”
CHOMP: Gradient optimization techniques for efficient motion planning (2009, background): “Many optimal controllers which do handle obstacles are framed in terms of mixed integer programming, which is known to be an NP-hard problem [24], [9], [17], [27].”
A Survey of Motion Planning Algorithms from the Perspective of Autonomous UAV Guidance (2010, methodology): “[97] uses a cost function based on a visibility graph and [7] estimates the cost function by searching a graph representation of the environment with Dijkstra’s algorithm.”
Graph Neural Networks for Decentralized Multi-Robot Path Planning (2019, background): “ centralized approaches, which consider the joint configuration space of all involved robots, have the advantage of producing optimal and complete plans, yet tend to be computationally very expensive [28]. Indeed, solving for optimality is NP-hard [42], and although significant progress has been mad”
Mixed-integer quadratic program trajectory generation for heterogeneous quadrotor teams (2012, methodology): “The condition that the prism does not collide with an obstacle o at time t k can be enforced with binary variables, b ofk , as where M is a large positive number [14].”
Receding horizon control of autonomous aerial vehicles (2002, methodology): “These variables can be used to add logical constraints into the optimization problem [3, 4], such as obstacle and collision avoidance [5, 6, 7].”
Towards a swarm of agile micro quadrotors (2012, methodology): “This method draws from the extensive literature on mixed-integer linear programs and their application to trajectory planning from Schouwenaars et al. (2001, 2006).”
Robust constrained model predictive control (2005, methodology): “Mixed-Integer Linear Programming (MILP) path-planning [56, 38] is combined with DMPC to provide a decentralized algorithm for cooperative guidance of UAVs.”
Wireless communications with unmanned aerial vehicles: opportunities and challenges (2016, background): “Many of the resulting problems with such an approximation belong to the class of mixed integer linear programming (MILP) [11], which can be solved with well-developed software packages.”
Trajectory Design for Completion Time Minimization in UAV-Enabled Multicasting (2018, background): “However, prior works mainly focus on UAV navigation applications to ensure its safe fly between a pair of predetermined initial and final locations, under various practical constraints such as collision avoidance with other UAVs and/or terrain obstacles [23]–[26].”
Minimum-Time Travel for a Vehicle with Acceleration Limits: Theoretical Analysis and Receding-Horizon Implementation (2008, methodology): “One way to achieve this, is for the trajectory optimization to be implemented in a receding horizon scheme rather than executed in one shot, from the start point to the end point [13, 14, 15].”
A Probabilistic Particle-Control Approximation of Chance-Constrained Stochastic Predictive Control (2010, methodology): “work has shown that optimal path planning with obstacles for vehicles, such as aircraft or satellites, can be posed as predictive control design for linear systems in polygonal feasible regions [49], [44].”
Accessing From the Sky: A Tutorial on UAV Communications for 5G and Beyond (2019, background): “While path planning has been extensively studied for UAV systems, early works mainly focused on UAV navigation applications, rather than targeting for optimizing the communication performance [70,119]–[121].”
Chance-Constrained Optimal Path Planning With Obstacles (2011, methodology): “The UAV is modeled as a double integrator with an innerloop velocity controller and maximum velocity constraints , a proposed by [5].”
Stereo vision-based obstacle avoidance for micro air vehicles using disparity space (2014, background): “Another unique feature of this RRT planner is that it maintains a safety invariance while the vehicle is flying [20].”
Learning to search: structured prediction techniques for imitation learning (2009, background): “obstacles are framed in terms of mixed integer programming, which is known to be an NP-hard problem (Schouwenaars et al., 2001; Earl et al., 2005; Ma et al., 2006; Vitus et al., 2008).”
CHOMP: Covariant Hamiltonian optimization for motion planning (2013, background): “Many optimal controllers which do handle obstacles are framed in terms of mixed integer programming, which is known to be an NP-hard problem [61].”