Optimal Integrated Task and Path Planning and Its Application to Multi-Robot Pickup and Delivery

• URL: http://arxiv.org/abs/2403.01277v1
• Date: Sat, 2 Mar 2024 17:48:40 GMT
• Title: Optimal Integrated Task and Path Planning and Its Application to Multi-Robot Pickup and Delivery
• Authors: Aman Aryan, Manan Modi, Indranil Saha, Rupak Majumdar and Swarup Mohalik
• Abstract summary: We propose a generic multi-robot planning mechanism that combines an optimal task planner and an optimal path planner. The Integrated planner, through the interaction of the task planner and the path planner, produces optimal collision-free trajectories for the robots.
• Score: 10.530860023128406
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a generic multi-robot planning mechanism that combines an optimal task planner and an optimal path planner to provide a scalable solution for complex multi-robot planning problems. The Integrated planner, through the interaction of the task planner and the path planner, produces optimal collision-free trajectories for the robots. We illustrate our general algorithm on an object pick-and-drop planning problem in a warehouse scenario where a group of robots is entrusted with moving objects from one location to another in the workspace. We solve the task planning problem by reducing it into an SMT-solving problem and employing the highly advanced SMT solver Z3 to solve it. To generate collision-free movement of the robots, we extend the state-of-the-art algorithm Conflict Based Search with Precedence Constraints with several domain-specific constraints. We evaluate our integrated task and path planner extensively on various instances of the object pick-and-drop planning problem and compare its performance with a state-of-the-art multi-robot classical planner. Experimental results demonstrate that our planning mechanism can deal with complex planning problems and outperforms a state-of-the-art classical planner both in terms of computation time and the quality of the generated plan.

Related papers

• A Meta-Engine Framework for Interleaved Task and Motion Planning using Topological Refinements [51.54559117314768]
  Task And Motion Planning (TAMP) is the problem of finding a solution to an automated planning problem. We propose a general and open-source framework for modeling and benchmarking TAMP problems. We introduce an innovative meta-technique to solve TAMP problems involving moving agents and multiple task-state-dependent obstacles.
  arXiv  Detail & Related papers  (2024-08-11T14:57:57Z)
• Unified Task and Motion Planning using Object-centric Abstractions of Motion Constraints [56.283944756315066]
  We propose an alternative TAMP approach that unifies task and motion planning into a single search. Our approach is based on an object-centric abstraction of motion constraints that permits leveraging the computational efficiency of off-the-shelf AI search to yield physically feasible plans.
  arXiv  Detail & Related papers  (2023-12-29T14:00:20Z)
• Planning as In-Painting: A Diffusion-Based Embodied Task Planning Framework for Environments under Uncertainty [56.30846158280031]
  Task planning for embodied AI has been one of the most challenging problems. We propose a task-agnostic method named 'planning as in-painting' The proposed framework achieves promising performances in various embodied AI tasks.
  arXiv  Detail & Related papers  (2023-12-02T10:07:17Z)
• Optimal task and motion planning and execution for human-robot multi-agent systems in dynamic environments [54.39292848359306]
  We propose a combined task and motion planning approach to optimize sequencing, assignment, and execution of tasks. The framework relies on decoupling tasks and actions, where an action is one possible geometric realization of a symbolic task. We demonstrate the approach effectiveness in a collaborative manufacturing scenario, in which a robotic arm and a human worker shall assemble a mosaic.
  arXiv  Detail & Related papers  (2023-03-27T01:50:45Z)
• Toward Efficient Task Planning for Dual-Arm Tabletop Object Rearrangement [12.928188950810043]
  In a non-monotone rearrangement task, complex object-object dependencies exist that require moving some objects multiple times to solve an instance. We develop effective task planning algorithms for scheduling the pick-n-place sequence that can be properly distributed between the two arms.
  arXiv  Detail & Related papers  (2022-07-17T05:11:14Z)
• Simultaneous Contact-Rich Grasping and Locomotion via Distributed Optimization Enabling Free-Climbing for Multi-Limbed Robots [60.06216976204385]
  We present an efficient motion planning framework for simultaneously solving locomotion, grasping, and contact problems. We demonstrate our proposed framework in the hardware experiments, showing that the multi-limbed robot is able to realize various motions including free-climbing at a slope angle 45deg with a much shorter planning time.
  arXiv  Detail & Related papers  (2022-07-04T13:52:10Z)
• Cooperative Task and Motion Planning for Multi-Arm Assembly Systems [32.56644393804845]
  Multi-robot assembly systems are becoming increasingly appealing in manufacturing. Planning for these systems in a manner that ensures each robot is simultaneously productive, and not idle, is challenging. We present a task and motion planning framework that jointly plans safe, low-makespan plans for a team of robots to assemble complex spatial structures.
  arXiv  Detail & Related papers  (2022-03-04T18:12:49Z)
• Learning to Search in Task and Motion Planning with Streams [20.003445874753233]
  Task and motion planning problems in robotics combine symbolic planning over discrete task variables with motion optimization over continuous state and action variables. We propose a geometrically informed symbolic planner that expands the set of objects and facts in a best-first manner. We apply our algorithm on a 7DOF robotic arm in block-stacking manipulation tasks.
  arXiv  Detail & Related papers  (2021-11-25T15:58:31Z)
• Anytime Stochastic Task and Motion Policies [12.72186877599064]
  We present a new approach for integrated task and motion planning in settings. Our algorithm is probabilistically complete and can compute feasible solution policies in an anytime fashion.
  arXiv  Detail & Related papers  (2021-08-28T00:23:39Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.