Time Range Constraints for Motion Planning for Manipulators

This paper addresses the problem of coordinated motion planning for multi-link robotic manipulator systems. One of the promising modern approaches to solving this problem is conflict-based planning, which avoids constructing a high-dimensional joint search space by sequentially solving a series of lower-dimensional problems. This is achieved by introducing spatio-temporal constraints whenever conflicts arise in individual manipulator plans, followed by replanning with these constraints in place. Unfortunately, existing methods that use constraints operate with individual time points, which reduces their practical efficiency. In this work, we present a novel conflict-based planning algorithm that utilizes interval-based temporal constraints rather than point-based ones – GECBS-T. Theoretically, the proposed algorithm guarantees bounded sub-optimality of the generated solutions; that is, for any user-defined bound w > 1, the cost of the GECBS-T solution will not exceed w times the cost of the optimal solution. In practice, the proposed algorithm significantly outperforms analogous algorithms in terms of planning speed, as confirmed by experiments conducted in the MuJoCo robotics simulator involving 2–4 KUKA robotic manipulators, each with 7 degrees of freedom.

motion planning, manipulators, M-RAMP, CBS, search-based, conflict-based, graph search, constraints, multi-agent, time range