Integer Programming for Multi-Robot Planning: A Column Generation Approach
We consider the problem of coordinating a fleet of robots in a warehouse so as to maximize the reward achieved within a time limit while respecting problem and robot specific constraints. We formulate the problem as a weighted set packing problem where elements are defined as being the space-time positions a robot can occupy and the items that can be picked up and delivered. We enforce that robots do not collide, that each item is delivered at most once, and that the number of robots active at any time does not exceed the total number available. Since the set of robot routes is not enumerable, we attack optimization using column generation where pricing is a resource-constrained shortest-path problem.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Simultaneous Contact-Rich Grasping and Locomotion via Distributed Optimization Enabling Free-Climbing for Multi-Limbed Robots
While motion planning of locomotion for legged robots has shown great success, motion planning for legged robots with dexterous multi-finger grasping is not mature yet. We present an efficient motion planning framework f…
Distributed OptimizationMotion 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 NavigationPIP-LLM: Integrating PDDL-Integer Programming with LLMs for Coordinating Multi-Robot Teams Using Natural Language
Enabling robot teams to execute natural language commands requires translating high-level instructions into feasible, efficient multi-robot plans. While Large Language Models (LLMs) combined with Planning Domain Descript…
Sparsification for Fast Optimal Multi-Robot Path Planning in Lazy Compilation Schemes
Path planning for multiple robots (MRPP) represents a task of finding non-colliding paths for robots through which they can navigate from their initial positions to specified goal positions. The problem is usually modele…
NavigateMixed 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, w…
Model Optimization