Abstract
Solving task planning problems involving multiple objects and multiple robotic arms poses scalability challenges. Such problems involve not only coordinating multiple high-DoF arms, but also searching through possible sequences of actions including object placements, and handoffs. The current work identifies a useful connection between multi-arm rearrangement and recent results in multi-body path planning on graphs with vertex capacity constraints. Solving a synchronized multi-arm rearrangement at a high-level involves reasoning over a modal graph, where nodes correspond to stable object placements and object transfer states by the arms. Edges of this graph correspond to pick, placement and handoff operations. The objects can be viewed as pebbles moving over this graph, which has capacity constraints. For instance, each arm can carry a single object but placement locations can accumulate many objects. Efficient integer linear programming-based solvers have been proposed for the corresponding pebble problem. The current work proposes a heuristic to guide the task planning process for synchronized multi-arm rearrangement. Results indicate good scalability to multiple arms and objects, and an algorithm that can find high-quality solutions fast and exhibiting desirable anytime behavior.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Akbari, A., Lagriffoul, F., Rosell, J.: Combined heuristic task and motion planning for bi-manual robots. Auton. Robots, pp. 1–16 (2018)
van den Berg, J., Snoeyink, J., Lin, M., Manocha, D.: Centralized path planning for multiple robots: optimal decoupling into sequential plans. In: RSS (2009)
Cohen, B., Phillips, M., Likhachev, M.: Planning single-arm manipulations with n-arm robots. In: SoCS (2015)
Dantam, N.T., Kingston, Z.K., Chaudhuri, S., Kavraki, L.E.: Incremental task and motion planning: a constraint-based approach. In: RSS (2016)
Dobson, A., Bekris, K.E.: Planning representations and algorithms for prehensile multi-arm manipulation. In: IROS, pp. 6381–6386. IEEE (2015)
Dobson, A., Solovey, K., Shome, R., Halperin, D., Bekris, K.E.: Scalable asymptotically-optimal multi-robot motion planning. In: MRS (2017)
Garrett, C.R., Lozano-Perez, T., Kaelbling, L.P.: Ffrob: leveraging symbolic planning for efficient task and motion planning. IJRR 37(1), 104–136 (2018)
Ghrist, R., O’Kane, J.M., LaValle, S.M.: . Computing pareto optimal coordinations on roadmaps. IJRR 24(11) (2005)
Halperin, D., Latombe, J.C., Wilson, R.H.: A general framework for assembly planning: the motion space approach. Algorithmica 26(3–4) (2000)
Han, S.D., Stiffler, N.M., Bekris, K.E., Yu, J.: Efficient, high-quality stack rearrangement. IEEE RAL 3(3), 1608–1615 (2018)
Han, S.D., Stiffler, N.M., Krontiris, A., Bekris, K., Yu, J.: Complexity results and fast methods for optimal tabletop rearrangement with overhand grasps. arXiv:1711.07369 (2017)
Harada, K., Tsuji, T., Laumond, J.P.: A manipulation motion planner for dual-arm industrial manipulators. In: ICRA (2014)
Hauser, K., Ng-Thow-Hing, V.: Randomized multi-modal motion planning for a humanoid robot manipulation task. IJRR 30(6) (2011)
Havur, G., Ozbilgin, G., Erdem, E., Patoglu, V.: Geometric rearrangement of multiple movable objects on cluttered surfaces: a hybrid reasoning approach. In: ICRA (2014)
Janson, L., Schmerling, E., Clark, A., Pavone, M.: Fast marching tree: a fast marching sampling-based method for optimal motion planning in many dimensions. IJRR (2015)
Kaelbling, L.P., Lozano-Pérez, T.: Hierarchical task and motion planning in the now. In: ICRA (2011)
Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal motion planning. IJRR 30(7) (2011)
Kavraki, L.E., Svestka, P., Latombe, J.C., Overmars, M.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. 12(4) (1996)
Krontiris, A., Bekris, K.E.: Dealing with difficult instances of object rearrangement. In: RSS (2015)
Krontiris, A., Bekris, K.E.: Efficiently solving general rearrangement tasks: a fast extension primitive for an incremental sampling-based planner. In: ICRA (2016)
LaValle, S.M., Kuffner, J.J.: Randomized kinodynamic planning. IJRR 20 (2001)
Ota, J.: Rearrangement of multiple movable objects-integration of global and local planning methodology. In: ICRA, 2 (2004)
Saribatur, Z.G., Patoglu, V., Erdem, E.: Finding optimal feasible global plans for multiple teams of heterogeneous robots using hybrid reasoning: an application to cognitive factories. Auton. Robot 43(1), 213–238 (2019)
Schmitt, P.S., Neubauer, W., Feiten, W., Wurm, K.M., Wichert, G.V., Burgard, W.: Optimal, sampling-based manipulation planning. In: ICRA. IEEE (2017)
Shome, R., Bekris, K.E.: Anytime multi-arm task and motion planning for pick-and-place of individual objects via handoffs. In: MRS, pp. 37–43. IEEE (2019)
Shome, R., Bekris, K.E.: Synchronized multi-arm rearrangement guided by mode graphs with capacity constraints. arXiv preprint arXiv:2005.09127 (2020)
Shome, R., Solovey, K., Dobson, A., Halperin, D., Bekris, K.E.: drrt*: Scalable and informed asymptotically-optimal multi-robot motion planning. Auton. Robots, pp. 1–25 (2019)
Shome, R., Solovey, K., Yu, J., Halperin, D., Bekris, K.E.: Fast, high-quality dual-arm rearrangement in synchronous, monotone tabletop setups. In: WAFR (2018)
Siméon, T., Laumond, J.P., Cortés, J., Sahbani, A.: Manipulation Planning with Probabilistic Roadmaps. IJRR 23(8) (2004)
Solovey, K., Salzman, O., Halperin, D.: Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning. IJRR 35(5) (2016)
Stilman, M., Schamburek, J.U., Kuffner, J., Asfour, T.: Manipulation planning among movable obstacles. In: ICRA (2007)
Surynek, P., Felner, A., Stern, R., Boyarski, E.: Efficient sat approach to multi-agent path finding under the sum of costs objective. In: Proceedings of the Twenty-second European Conference on Artificial Intelligence, pp. 810–818. IOS (2016)
Surynek, P., Kumar, T.S., Koenig, S.: Multi-agent path finding with capacity constraints. In: International Conference of the Italian Association for Artificial Intelligence (2019)
Toussaint, M.: Logic-geometric programming: an optimization-based approach to combined task and motion planning. In: International Joint Conference on Artificial Intelligence (2015)
Vega-Brown, W., Roy, N.: Asymptotically optimal planning under piecewise-analytic constraints. In: WAFR (2016)
Wagner, G., Choset, H.: Subdimensional expansion for multirobot path planning. Artif. Intell. J. 219 (2015)
Yu, J., LaValle, S.M.: Optimal multirobot path planning on graphs: Complete algorithms and effective heuristics. IEEE Trans. Robot. 32(5), 1163–1177 (2016)
Acknowledgments
The authors would like to acknowledge the support of NSF awards IIS:1617744 and CCF:1934924. Any findings reported here do not reflect the opinions of the sponsor.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Shome, R., Bekris, K.E. (2021). Synchronized Multi-arm Rearrangement Guided by Mode Graphs with Capacity Constraints. In: LaValle, S.M., Lin, M., Ojala, T., Shell, D., Yu, J. (eds) Algorithmic Foundations of Robotics XIV. WAFR 2020. Springer Proceedings in Advanced Robotics, vol 17. Springer, Cham. https://doi.org/10.1007/978-3-030-66723-8_15
Download citation
DOI: https://doi.org/10.1007/978-3-030-66723-8_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-66722-1
Online ISBN: 978-3-030-66723-8
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)