Computing High-Quality Clutter Removal Solutions for Multiple Robots

We investigate the task and motion planning problem of clearing clutter from a workspace with limited ingress/egress access for multiple robots. We call the problem multi-robot clutter removal (MRCR). Targeting practical applications where motion planning is non-trivial but is not a bottle-neck, we focus on finding high-quality solutions for feasible MRCR instances, which depends on the ability to efficiently compute high-quality object removal sequences. Despite the challenging multi-robot setting, our proposed search algorithms based on A *, dynamic programming, and best-first heuristics all produce solutions for tens of objects that significantly outperform single robot solutions. Realistic simulations with multiple Kuka youBots further confirms the effectiveness of our algorithmic solutions. In contrast, we also show that deciding the optimal object removal sequence for MRCR is computationally intractable.

Authors

• Wei N. Tang
• Shuai D. Han
• Jingjin Yu

Keywords

• Heuristic algorithms
• Search problems
• Planning
• Dynamic programming
• Clutter
• Task analysis
• Intelligent robots
• Multiple Robots
• Clutter Removal
• Search Algorithm
• Path Planning
• Optimal Sequence
• Realistic Simulation
• Solution Algorithm
• Single Robot
• Reachable
• Multiple Objects
• Optimal Ratio
• Number Of Objects
• Target Object
• Theoretical Limit
• Multiple Algorithms
• Child Nodes
• Near-optimal Solution
• Task Planning
• Scene Understanding
• Monte Carlo Tree Search
• Makespan
• Static Obstacles
• Object Pose
• Heuristic Search Algorithm
• Upper Confidence Bound
• Recursive Function
• Combinatorial Explosion
• Approximate Dynamic Programming