Rigid Body Path Planning Using Mixed-Integer Linear Programming

Navigating rigid body objects through crowded environments can be challenging, especially when narrow passages are presented. Existing sampling-based planners and optimization-based methods like mixed integer linear programming (MILP) formulations, suffer from limited scalability with respect to eit...

Full description

Saved in:
Bibliographic Details
Published in:IEEE robotics and automation letters 2024-11, Vol.9 (11), p.10026-10033
Main Authors: Yu, Mingxin, Fan, Chuchu
Format: Article
Language:English
Subjects:
Algorithms
Collision avoidance
formal methods in robotics and automation
Integer programming
Lattices
Linear programming
Mixed integer
Motion and path planning
Path planning
Pipelines
Planning
Polytopes
Rigid structures
Sampling
Scalability
Three-dimensional displays
Workspace
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Navigating rigid body objects through crowded environments can be challenging, especially when narrow passages are presented. Existing sampling-based planners and optimization-based methods like mixed integer linear programming (MILP) formulations, suffer from limited scalability with respect to either the size of the workspace or the number of obstacles. In order to address the scalability issue, we propose a three-stage algorithm that first generates a graph of convex polytopes in the workspace free of collision, then poses a large set of small MILPs to generate viable paths between polytopes, and finally queries a pair of start and end configurations for a feasible path online. The graph of convex polytopes serves as a decomposition of the free workspace and the number of decision variables in each MILP is limited by restricting the subproblem within two or three free polytopes rather than the entire free region. Our simulation results demonstrate shorter online computation time compared to baseline methods and scales better with the size of the environment and tunnel width than sampling-based planners in both 2D and 3D environments.
ISSN:2377-3766
2377-3766
DOI:10.1109/LRA.2024.3468165