Hybrid planning for challenging construction problems: an answer set programming approach. (English) Zbl 07702944
Summary: We study construction problems where multiple robots rearrange stacks of prefabricated blocks to build stable structures. These problems are challenging due to ramifications of actions, true concurrency, and requirements of supportedness of blocks by a surface or a robot and stability of the overall structure at all times. We propose a general elaboration tolerant method to solve a wide range of construction problems, based on the knowledge representation and reasoning paradigm of Answer Set Programming. This method not only (i) determines a stable final configuration of the structure, but also (ii) computes the order of manipulation tasks for multiple autonomous robots to build the structure from an initial configuration, (iii) while simultaneously ensuring the requirements of supportedness and stability at all times. We prove the soundness and completeness of our method with respect to these properties. We introduce a set of challenging construction benchmark instances, including construction of (uneven) bridges and overhangs, and discuss the usefulness of our framework over these instances. Furthermore, we perform experiments to investigate the computational performance of our hybrid method, and demonstrate the applicability of our method using a bimanual Baxter robot.
MSC:
| 68Txx | Artificial intelligence |
References:
| [1] | Akbari, A.; Muhayyuddin; Rosell, J., Knowledge-oriented task and motion planning for multiple mobile robots, J. Exp. Theor. Artif. Intell., 31, 1, 137-162 (2019) |
| [2] | Barry, J.; Hsiao, K.; Kaelbling, L. P.; Lozano-Pérez, T., Manipulation with multiple action types, (Proc. of ISER (2013)), 531-545 |
| [3] | Beetz, M.; Jain, D.; Mosenlechner, L.; Tenorth, M.; Kunze, L.; Blodow, N.; Pangercic, D., Cognition-enabled autonomous robot control for the realization of home chore task intelligence, Proc. IEEE, 100, 8, 2454-2471 (2012) |
| [4] | Bernardini, S.; Fox, M.; Long, D.; Piacentini, C., Boosting search guidance in problems with semantic attachments, (Proc. of ICAPS (2017)) |
| [5] | Beyeler, L.; Bazin, J.-C.; Whiting, E., A graph-based approach for discovery of stable deconstruction sequences, (Proc. of AAG (2015)), 145-157 |
| [6] | Blum, M.; Griffith, A.; Neumann, B., A stability test for configurations of blocks (1970), MIT Artificial Intelligence Laboratory, Technical report |
| [7] | Bock, T., Construction automation and robotics, (Robotics and Automation in Construction (2008), InTech) |
| [8] | Boneschanscher, N.; van der Drift, H.; Buckley, S. J.; Taylor, R. H., Subassembly stability, (Proc. of AAAI, vol. 88 (1988)), 780-785 |
| [9] | Brewka, G.; Eiter, T.; Truszczynski, M., Answer set programming: an introduction to the special issue, AI Mag., 37, 3, 5-6 (2016) |
| [10] | Buccafurri, F.; Leone, N.; Rullo, P., Enhancing disjunctive datalog by constraints, IEEE Trans. Knowl. Data Eng., 12, 5, 845-860 (2000) |
| [11] | Caldiran, O.; Haspalamutgil, K.; Ok, A.; Palaz, C.; Erdem, E.; Patoglu, V., Bridging the gap between high-level reasoning and low-level control, (Proc. of LPNMR (2009)), 342-354 |
| [12] | Calimeri, F.; Faber, W.; Gebser, M.; Ianni, G.; Kaminski, R.; Krennwallner, T.; Leone, N.; Ricca, F.; Schaub, T., ASP-Core-2 input language format (2013) |
| [13] | Calimeri, F.; Fink, M.; Germano, S.; Humenberger, A.; Ianni, G.; Redl, C.; Stepanova, D.; Tucci, A.; Wimmer, A., Angry-HEX: an artificial player for angry birds based on declarative knowledge bases, IEEE Trans. Comput. Intell. AI Games, 8, 2, 128-139 (2016) |
| [14] | Chitta, S.; Sucan, I. A.; Cousins, S., Moveit! [ROS topics], IEEE Robot. Autom. Mag., 19, 1, 18-19 (2012) |
| [15] | Coruhlu, G.; Erdem, E.; Patoglu, V., Explainable robotic plan execution monitoring under partial observability, IEEE Trans. Robot., 1-21 (2021) |
| [16] | Cosgun, A.; Hermans, T.; Emeli, V.; Stilman, M., Push planning for object placement on cluttered table surfaces, (Proc. of IEEE/RSJ IROS (2011)), 4627-4632 |
| [17] | Dantam, N. T.; Kingston, Z. K.; Chaudhuri, S.; Kavraki, L. E., Incremental task and motion planning: a constraint-based approach, (Proc. of RSS (2016)) |
| [18] | Dantam, N. T.; Kingston, Z. K.; Chaudhuri, S.; Kavraki, L. E., An incremental constraint-based framework for task and motion planning. I, J. Robot. Res., 37, 10 (2018) |
| [19] | Demaine, E. D.; Demaine, M. L.; Hoffmann, M.; O’Rourke, J., Pushing blocks is hard, Comput. Geom., 26, 1, 21-36 (2003) · Zbl 1041.65021 |
| [20] | Dogar, M. R.; Srinivasa, S. S., A planning framework for non-prehensile manipulation under clutter and uncertainty, Auton. Robots, 33, 3, 217-236 (2012) |
| [21] | Dornhege, C.; Eyerich, P.; Keller, T.; Trüg, S.; Brenner, M.; Nebel, B., Semantic attachments for domain-independent planning systems, (Proc. of ICAPS (2009)) |
| [22] | Edelkamp, S.; Hoffmann, J., PDDL2.2: the language for the classical part of the 4th international planning competition (2004), University of Freiburg, Technical Report 195 |
| [23] | Eiter, T.; Fink, M.; Ianni, G.; Krennwallner, T.; Redl, C.; Schüller, P., A model building framework for answer set programming with external computations, Theory Pract. Log. Program., 16, 4, 418-464 (2016) · Zbl 1379.68058 |
| [24] | Eiter, T.; Fink, M.; Krennwallner, T.; Redl, C.; Schüller, P., Efficient HEX-program evaluation based on unfounded sets, J. Artif. Intell. Res., 49, 269-321 (2014) · Zbl 1361.68031 |
| [25] | Eiter, T.; Ianni, G.; Schindlauer, R.; Tompits, H., dlvhex: a system for integrating multiple semantics in an answer-set programming framework, (Workshop on Logic Programming and Constraint Systems (2006)), 206-210 |
| [26] | Erdem, E.; Gelfond, M.; Leone, N., Applications of answer set programming, AI Mag., 37, 3, 53-68 (2016) |
| [27] | Erdem, E.; Haspalamutgil, K.; Palaz, C.; Patoglu, V.; Uras, T., Combining high-level causal reasoning with low-level geometric reasoning and motion planning for robotic manipulation, (Proc. of IEEE ICRA (2011)), 4575-4581 |
| [28] | Erdem, E.; Lifschitz, V., Transformations of logic programs related to causality and planning, (Proc. of LPNMR (1999)), 107-116 · Zbl 0952.68021 |
| [29] | Erdem, E.; Lifschitz, V., Tight logic programs, Theory Pract. Log. Program., 3, 4-5, 499-518 (2003) · Zbl 1079.68014 |
| [30] | Erdem, E.; Patoglu, V., Applications of ASP in robotics, Künstl. Intell., 32, 2-3, 143-149 (2018) |
| [31] | Erdem, E.; Patoglu, V.; Schüller, P., A systematic analysis of levels of integration between high-level task planning and low-level feasibility checks, AI Commun., 29, 2, 319-349 (2016) |
| [32] | Erdogan, C.; Stilman, M., Planning in constraint space: automated design of functional structures, (Proc. of IEEE ICRA (2013)) |
| [33] | Erdogan, S. T.; Lifschitz, V., Definitions in answer set programming, (Proc. of LPNMR (2004)), 114-126 · Zbl 1121.68330 |
| [34] | Faber, W.; Pfeifer, G.; Leone, N., Semantics and complexity of recursive aggregates in answer set programming, Artif. Intell., 175, 1, 278-298 (2011) · Zbl 1216.68263 |
| [35] | Fagin, R., Monadic generalized spectra, Math. Log. Q., 21, 1, 89-96 (1975) · Zbl 0317.02054 |
| [36] | Fahlman, S. E., A planning system for robot construction tasks, Artif. Intell., 5, 1, 1-49 (1974) |
| [37] | Ferreira, L.; Toledo, C., Generating levels for physics-based puzzle games with estimation of distribution algorithms, (Proc. of ACM ACE (2014)), 25 |
| [38] | Furrer, F.; Wermelinger, M.; Yoshida, H.; Gramazio, F.; Kohler, M.; Siegwart, R.; Hutter, M., Autonomous robotic stone stacking with online next best object target pose planning, (Proc. of IEEE ICRA (2017)), 2350-2356 |
| [39] | Gaschler, A.; Petrick, R. P.A.; Giuliani, M.; Rickert, M.; Knoll, A., KVP: a knowledge of volumes approach to robot task planning, (Proc. of IEEE/RSJ IROS (2013)), 202-208 |
| [40] | Gaschler, A.; Petrick, R. P.A.; Khatib, O.; Knoll, A., KABouM: knowledge-level action and bounding geometry motion planner, J. Artif. Intell. Res., 61, 323-362 (2018) · Zbl 1426.68263 |
| [41] | Gelfond, M.; Lifschitz, V., Classical negation in logic programs and disjunctive databases, New Gener. Comput., 9, 365-385 (1991) · Zbl 0735.68012 |
| [42] | Gelfond, M.; Lifschitz, V., Action languages, Electron. Trans. Artif. Intell., 2, 193-210 (1998) |
| [43] | Gerevini, A.; Haslum, P.; Long, D.; Saetti, A.; Dimopoulos, Y., Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners, Artif. Intell., 173, 5, 619-668 (2009) · Zbl 1191.68634 |
| [44] | Giunchiglia, E.; Lee, J.; Lifschitz, V.; McCain, N.; Turner, H., Nonmonotonic causal theories, Artif. Intell., 153, 1-2, 49-104 (2004) · Zbl 1085.68161 |
| [45] | Gravot, F.; Cambon, S.; Alami, R., aSyMov: a planner that deals with intricate symbolic and geometric problems, (Proc. of ISRR (2003)), 100-110 |
| [46] | Gupta, N.; Nau, D. S., On the complexity of blocks-world planning, Artif. Intell., 56, 2-3, 223-254 (1992) · Zbl 0785.68046 |
| [47] | Hall, J. F., Fun with stacking blocks, Am. J. Phys., 73, 12, 1107-1116 (2005) |
| [48] | Han, S. D.; Stiffler, N. M.; Bekris, K. E.; Yu, J., Autonomous design of functional structures, Adv. Robot., 29, 9, 625-638 (2015) |
| [49] | Han, S. D.; Stiffler, N. M.; Bekris, K. E.; Yu, J., Efficient, high-quality stack rearrangement, IEEE Robot. Autom. Lett., 3, 3, 1608-1615 (2018) |
| [50] | Haslum, P.; Ivankovic, F.; Ramírez, M.; Gordon, D.; Thiébaux, S.; Shivashankar, V.; Nau, D. S., Extending classical planning with state constraints: heuristics and search for optimal planning, J. Artif. Intell. Res., 62, 373-431 (2018) · Zbl 1448.68388 |
| [51] | Hauser, K.; Latombe, J.-C., Integrating task and PRM motion planning: dealing with many infeasible motion planning queries, (Workshop on Bridging the Gap Between Task and Motion Planning at ICAPS (2009)) |
| [52] | Havur, G.; Ozbilgin, G.; Erdem, E.; Patoglu, V., Geometric rearrangement of multiple movable objects on cluttered surfaces: a hybrid reasoning approach, (Proc. of IEEE ICRA (2014)), 445-452 |
| [53] | Hertle, A.; Dornhege, C.; Keller, T.; Nebel, B., Planning with semantic attachments: an object-oriented view, (Proc. of ECAI (2012)), 402-407 |
| [54] | Jia, Z.; Gallagher, A. C.; Saxena, A.; Chen, T., 3d reasoning from blocks to stability, IEEE Trans. Pattern Anal. Mach. Intell., 37, 5, 905-918 (2015) |
| [55] | Kaelbling, L. P.; Lozano-Pérez, T., Integrated task and motion planning in belief space. I, J. Robot. Res., 32, 9-10, 1194-1227 (2013) |
| [56] | Koenig, N. P.; Howard, A., Design and use paradigms for Gazebo, an open-source multi-robot simulator, (Proc. of IEEE/RSJ IROS (2004)), 2149-2154 |
| [57] | Krontiris, A.; Bekris, K. E., Dealing with difficult instances of object rearrangement, (Proc. of RSS (2015)) |
| [58] | Krontiris, A.; Bekris, K. E., Efficiently solving general rearrangement tasks: a fast extension primitive for an incremental sampling-based planner, (Proc. of IEEE ICRA (2016)), 3924-3931 |
| [59] | Krontiris, A.; Shome, R.; Dobson, A.; Kimmel, A.; Bekris, K., Rearranging similar objects with a manipulator using pebble graphs, (Proc. of IEEE-RAS Humanoids (2014)), 1081-1087 |
| [60] | Lagriffoul, F.; Dimitrov, D.; Bidot, J.; Saffiotti, A.; Karlsson, L., Efficiently combining task and motion planning using geometric constraints. I, J. Robot. Res., 33, 14, 1726-1747 (2014) |
| [61] | LaValle, S. M., Planning Algorithms (2006), Cambridge University Press · Zbl 1100.68108 |
| [62] | Lee, S.; Shin, Y. G., Assembly planning based on geometric reasoning, Comput. Graph., 14, 2, 237-250 (1990) |
| [63] | Livesley, R. K., Limit analysis of structures formed from rigid blocks, Int. J. Numer. Methods Eng., 12, 12, 1853-1871 (1978) · Zbl 0394.73022 |
| [64] | Livesley, R. K., A computational model for the limit analysis of three-dimensional masonry structures, Meccanica, 27, 3, 161-172 (1992) · Zbl 0775.73096 |
| [65] | Magnaguagno, M. C.; Meneguzzi, F., Semantic attachments for HTN planning, (Proc. of AAAI (2020)), 9933-9940 |
| [66] | Mattikalli, R.; Baraff, D.; Khosla, P., Finding all stable orientations of assemblies with friction, IEEE Trans. Robot. Autom., 12, 2, 290-301 (1996) |
| [67] | McCarthy, J., Elaboration tolerance, (Working Papers of the Fourth International Symposium on Logical Formalizations of Commonsense Reasoning (1998)) |
| [68] | McDermott, D.; Sussman, G., The Conniver Reference Manual, MIT AI Memo, vol. 259 (1972) |
| [69] | Mojtahedzadeh, R.; Bouguerra, A.; Schaffernicht, E.; Lilienthal, A. J., Support relation analysis and decision making for safe robotic manipulation tasks, Robot. Auton. Syst., 71, 99-117 (2015) |
| [70] | Napp, N.; Nagpal, R., Distributed amorphous ramp construction in unstructured environments, Robotica, 32, 2, 279-290 (2014) |
| [71] | Nouman, A.; Patoglu, V.; Erdem, E., Hybrid conditional planning for robotic applications, Int. J. Robot. Res., 40, 2-3, 594-623 (2021) |
| [72] | Okada, K.; Haneda, A.; Nakai, H.; Inaba, M.; Inoue, H., Environment manipulation planner for humanoid robots using task graph that generates action sequence, (Proc. of IEEE/RSJ IROS, vol. 2 (2004)), 1174-1179 |
| [73] | Palmer, R. S., Computational complexity of motion and stability of polygons (1989), Cornell University, Technical report |
| [74] | Pang, J.-S.; Trinkle, J., Stability characterizations of rigid body contact problems with Coulomb friction, J. Appl. Math. Mech., 80, 10, 643-663 (2000) · Zbl 0989.70002 |
| [75] | Paterson, M.; Peres, Y.; Thorup, M.; Winkler, P.; Zwick, U., Maximum overhang, Am. Math. Mon., 116, 9, 763-787 (2009) · Zbl 1229.00005 |
| [76] | Paterson, M.; Zwick, U., Overhang, (ACM-SIAM Symposium on Discrete Algorithm (2006)), 231-240 · Zbl 1192.40002 |
| [77] | Paterson, M.; Zwick, U., Overhang, Am. Math. Mon., 116, 1, 19-44 (2009) · Zbl 1168.40001 |
| [78] | Plaku, E., Planning in discrete and continuous spaces: from LTL tasks to robot motions, (Joint Proc. of TAROS and FIRA RoboWorld (2012)), 331-342 |
| [79] | Rizwan, M.; Patoglu, V.; Erdem, E., Human robot collaborative assembly planning: an answer set programming approach, Theory Pract. Log. Program., 20, 6, 1006-1020 (2020) · Zbl 1457.68270 |
| [80] | Röhrdanz, F.; Mosemann, H.; Wahl, F., Generating and evaluating stable assembly sequences, Adv. Robot., 11, 2, 97-126 (1996) |
| [81] | 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. Robots, 43, 213-238 (2019) |
| [82] | Schimmels, J. M.; Peshkin, M. A., Force-assembly with friction, IEEE Trans. Robot. Autom., 10, 4, 465-479 (1994) |
| [83] | Schmult, B., Autonomous robotic disassembly in the blocks world, Int. J. Robot. Res., 11, 5, 437-459 (1992) |
| [84] | Spanos, P. D.; Roussis, P. C.; Politis, N. P., Dynamic analysis of stacked rigid blocks, Soil Dyn. Earthq. Eng., 21, 7, 559-578 (2001) |
| [85] | Srivastava, S.; Fang, E.; Riano, L.; Chitnis, R.; Russell, S. J.; Abbeel, P., Combined task and motion planning through an extensible planner-independent interface layer, (Proc. of IEEE ICRA (2014)), 639-646 |
| [86] | Stephenson, M.; Renz, J., Procedural generation of complex stable structures for angry birds levels, (Proc. IEEE CIG (2016)), 1-8 |
| [87] | Stilman, M.; Kuffner, J., Planning among movable obstacles with artificial constraints, Int. J. Robot. Res., 27, 11-12, 1295-1307 (2008) · Zbl 1188.93084 |
| [88] | Stilman, M.; Kuffner, J. J., Navigation among movable obstacles: real-time reasoning in complex environments, Int. J. Humanoid Robot., 2, 04, 479-503 (2005) |
| [89] | Stilman, M.; Schamburek, J.-U.; Kuffner, J.; Asfour, T., Manipulation planning among movable obstacles, (Proc. of IEEE ICRA (2007)), 3327-3332 |
| [90] | Sucan, I. A.; Moll, M.; Kavraki, L. E., The open motion planning library, IEEE Robot. Autom. Mag., 19, 4, 72-82 (2012) |
| [91] | Sussman, G. J.; McDermott, D. V., From planner to conniver: a genetic approach, (Proc. of ACM Fall Joint Computer Conference, Part II (1972)), 1171-1179 |
| [92] | Thangavelu, V.; Liu, Y.; Saboia, M.; Napp, N., Dry stacking for automated construction with irregular objects, (Artif. Intell. (2018)) |
| [93] | Thiébaux, S.; Hoffmann, J.; Nebel, B., In defense of PDDL axioms, Artif. Intell., 168, 1-2, 38-69 (2005) · Zbl 1132.68714 |
| [94] | Thomas, A.; Amatya, S.; Mastrogiovanni, F.; Baglietto, M., Task-assisted motion planning in partially observable domains (2019), CoRR |
| [95] | Toussaint, M., Logic-geometric programming: an optimization-based approach to combined task and motion planning, (Proc. of IJCAI (2015)), 1930-1936 |
| [96] | Toussaint, M.; Lopes, M., Multi-bound tree search for logic-geometric programming in cooperative manipulation domains, (Proc. of IEEE ICRA (2017)), 4044-4051 |
| [97] | Wałega, P. A.; Zawidzki, M.; Lechowski, T., Qualitative physics in angry birds, IEEE Trans. Comput. Intell. AI Games, 8, 2, 152-165 (2016) |
| [98] | Wan, W.; Harada, K.; Nagata, K., Assembly sequence planning for motion planning, Assem. Autom., 38, 2, 195-206 (2018) |
| [99] | Wang, J.; Rogers, P.; Parker, L.; Brooks, D.; Stilman, M., Robot jenga: autonomous and strategic block extraction, (Proc. of IEEE/RSJ IROS (2009)), 5248-5253 |
| [100] | Weyhrauch, R. W., Prolegomena to a theory of formal reasoning (1978), Stanford University, Technical report |
| [101] | Weyhrauch, R. W., Prolegomena to a theory of mechanized formal reasoning, Artif. Intell., 13, 1-2, 133-170 (1980) · Zbl 0435.68070 |
| [102] | Whiting, E. J.W., Design of structurally-sound masonry buildings using 3D static analysis (2012), Massachusetts Institute of Technology, PhD thesis |
| [103] | Wilfong, G., Motion planning in the presence of movable obstacles, (Proc. of SCG (1988)), 279-288 |
| [104] | Wilson, R. H.; Latombe, J.-C., Geometric reasoning about mechanical assembly, Artif. Intell., 71, 2, 371-396 (1994) |
| [105] | Winograd, T., Understanding natural language, Cogn. Psychol., 3, 1, 1-191 (1972) |
| [106] | Zwick, U., Jenga, (Proc. of ACM SIAM SODA (2002)), 243-246 · Zbl 1092.91504 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
