Slimmere Robots, Betere Samenwerking: Een Doorbraak in Multi-Robot Systemen
In de wereld van de robotica neemt de complexiteit toe naarmate systemen slimmer worden en meer samen gaan werken. Mijn scriptie richt zich op de coördinatie van meerdere autonome robots in gedeelde omgevingen, een actueel probleem waar de industrie steeds vaker mee te maken krijgt. Denk aan robots die samen auto's bouwen of in de medische wereld zelfs operaties uitvoeren. Maar hoe zorg je ervoor dat deze robots soepel samenwerken zonder elkaar in de weg te zitten? De oplossing ligt in de ontwikkeling van geavanceerde bewegingsplanningsmethoden, en dat is precies waar mijn onderzoek over gaat.
De uitdaging: Veel robots, weinig ruimte
Het gebruik van meerdere robots in één systeem - ofwel Multi-Robot Systemen (MRS) - belooft enorme voordelen. Denk aan hogere efficiëntie, robuustheid en zelfs compleet nieuwe mogelijkheden binnen productieprocessen of medische toepassingen. Maar zoals met elke technologische vooruitgang brengt dit ook uitdagingen met zich mee. Eén van de grootste vraagstukken binnen MRS is bewegingsplanning: hoe zorg je dat robots zich efficiënt en veilig bewegen zonder elkaar te hinderen?
Traditionele oplossingen vallen vaak in twee categorieën: gekoppelde en ontkoppelde methoden. Bij gekoppelde methoden worden de bewegingen van alle robots gezamenlijk gepland, wat leidt tot een nauwkeurige coördinatie. Echter, naarmate het aantal robots of de complexiteit van de robots toeneemt, groeit ook de benodigde rekenkracht exponentieel. Dit maakt deze aanpak onpraktisch voor grote systemen. Aan de andere kant zijn ontkoppelde methoden schaalbaarder, omdat ze robots afzonderlijk plannen, maar het nadeel is dat ze vaak minder optimale oplossingen opleveren en geen garanties geven dat er een oplossing wordt gevonden indien die zou bestaan.
Een hybride oplossing
In mijn onderzoek stel ik een hybride bewegingsplanningsmethode voor, die de voordelen van beide bestaande benaderingen combineert. De kern van deze methode is het gebruik van Conflict-Based Search (CBS) in combinatie met Probabilistic Roadmaps (PRM). CBS wordt gebruikt om conflicten tussen robots op te lossen, terwijl PRM helpt bij het vinden van mogelijke paden voor elke robot. Deze hybride aanpak biedt een balans tussen de nauwkeurigheid van gekoppelde methoden en de schaalbaarheid van ontkoppelde methoden.
Testen en simulaties
Om de effectiviteit van deze hybride methode te testen, werden simulaties uitgevoerd met Franka Emika Panda-manipulatoren in verschillende omgevingen. De resultaten waren veelbelovend: de CBS-PRM hybride methode bleek beter te schalen met toenemende complexiteit vergeleken met gekoppelde methoden. Bovendien liet de methode hogere slagingspercentages zien dan ontkoppelde methoden, en genereerde ze routes met een lagere kost (kortere of meer efficiënte paden). Dit betekent dat robots hun taken sneller en efficiënter kunnen uitvoeren, zonder dat dit ten koste gaat van nauwkeurigheid of veiligheid.
Een nieuwe toolkit voor robotica
Tijdens mijn onderzoek heb ik ook een uitgebreide bibliotheek ontwikkeld voor multi-robot bewegingsplanning. Deze toolkit bevat implementaties van de verschillende algoritmen die ik heb onderzocht, en maakt benchmarking van de prestaties in verschillende scenario's mogelijk. Dit is een belangrijke stap, omdat het niet alleen mijn onderzoek ondersteunt, maar ook een waardevol hulpmiddel kan zijn voor andere onderzoekers en ingenieurs die werken aan vergelijkbare vraagstukken.
Hoewel de hybride aanpak die ik heb ontwikkeld veelbelovende resultaten laat zien, zijn er nog tal van mogelijkheden voor verdere verbetering. Denk aan het optimaliseren van de rekenefficiëntie of het toepassen van de methode in meer complexe, real-world omgevingen.
Toekomstperspectief
Het werk dat ik heb verricht biedt een solide basis voor verdere ontwikkeling in het domein van MRS. Naarmate robotica zich verder ontwikkelt, zullen systemen steeds complexer worden en zal de vraag naar robuuste, efficiënte oplossingen voor bewegingsplanning alleen maar toenemen. Of het nu gaat om robots in een fabriek of in een operatiekamer, de coördinatie tussen meerdere robots is cruciaal voor het succes van deze systemen.
Mijn onderzoek draagt bij aan deze ontwikkeling door een nieuwe, hybride benadering te bieden die zowel schaalbaar als effectief is. Deze methode kan een belangrijke stap zijn richting een toekomst waarin robots niet alleen naast elkaar werken, maar ook echt met elkaar samenwerken – veilig, efficiënt en zonder fouten.
Conclusie
De vooruitgang in multi-robot systemen is essentieel voor de toekomst van robotica. Mijn scriptie introduceert een nieuwe hybride aanpak voor bewegingsplanning die zowel de nauwkeurigheid als de schaalbaarheid van bestaande methoden verbetert. Met verdere ontwikkeling en verfijning kan deze aanpak bijdragen aan de implementatie van efficiënte, foutloze robotteams in talloze toepassingen. Dit onderzoek opent deuren naar nieuwe mogelijkheden en vormt een belangrijke stap in de evolutie van geavanceerde robotsystemen.
Bibliografie
Amato, N. M., Bayazit, O. B., Dale, L. K., Jones, C., & Vallejo, D. (1998). Obprm: An obstacle-based prm for 3d workspaces. Proc. Int. Workshop on Algorithmic Foundations of Robotics (WAFR), 155–168.
Barraquand, J., & Latombe, J.-C. (1990). A monte-carlo algorithm for path planning with many degrees of freedom. Proceedings., IEEE International Conference on Robotics and Automation, 1712–1717.
Bohlin, R., & Kavraki, L. E. (2000). Path planning using lazy prm. Proceedings 2000 ICRA. Millennium conference. IEEE international conference on robotics and automation. Symposia proceedings (Cat. No. 00CH37065), 1, 521–528.
Boor, V., Overmars, M. H., & Van Der Stappen, A. F. (1999). The gaussian sampling strategy for probabilistic roadmap planners. Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No. 99CH36288C), 2, 1018–1023.
Buss, S. R. (2004). Introduction to inverse kinematics with jacobian transpose. Pseudoinverse and Damped Least Squares methods, 19.
Canny, J. F. (1988). The complexity of robot motion planning. The MIT Press.
Čáp, M., Novák, P., Kleiner, A., & Selecký, M. (2015). Prioritized planning algorithms for trajectory coordination of multiple mobile robots. IEEE Transactions on Automation Science and Engineering, 12(3), 835–849.
Cheng, R., Shankar, K., & Burdick, J. W. (2020). Learning an optimal sampling distribution for efficient motion planning. 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 7485–7492.
Choset, H. (2000). Chapter 3: Configuration space (tech. rep.) (Accessed: 2024-08-05). Carnegie Mellon University. https://www.cs.cmu.edu/~motionplanning/lecture/Chap3-ConfigSpace_howie.pdf.
Choudhury, S., Gammell, J. D., Barfoot, T. D., Srinivasa, S. S., & Scherer, S. (2016). Regionally accelerated batch informed trees (rabit*): A framework to integrate local information into optimal path planning. 2016 IEEE International Conference on Robotics and Automation (ICRA), 4207–4214.
Cohen, B., Chitta, S., & Likhachev, M. (2014). Single-and dual-arm motion planning with heuristic search. The International Journal of Robotics Research, 33(2), 305–320.
Coulombe, A., & Lin, H.-C. (2020). High precision real time collision detection. arXiv preprint arXiv:2007.12045.
Dobson, A., & Bekris, K. E. (2014). Sparse roadmap spanners for asymptotically near-optimal motion planning. The International Journal of Robotics Research, 33(1), 18–47.
Erdmann, M., & Lozano-Perez, T. (1987). On multiple moving objects. Algorithmica, 2, 477–521.
Faust, A., Oslund, K., Ramirez, O., Francis, A., Tapia, L., Fiser, M., & Davidson, J. (2018). Prm-rl: Long-range robotic navigation tasks by combining reinforcement learning and sampling-based planning. 2018 IEEE International Conference on Robotics and Automation (ICRA), 5113–5120.
Franka Emika GmbH. (2024). Franka control interface documentation. https://frankaemika.github.io/docs/control_parameters.html (Accessed August 7, 2024).
Gammell, J. D., Srinivasa, S. S., & Barfoot, T. D. (2015). Batch informed trees (bit*): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs. 2015 IEEE International Conference on Robotics and Automation (ICRA), 3067–3074.
Ha, H., Xu, J., & Song, S. (2020). Learning a decentralized multi-arm motion planner. Retrieved December 15, 2023, from https://multiarm.cs.columbia.edu.
He, Y., & Liu, S. (2021). Analytical inverse kinematics for franka emika panda–a geometrical solver for 7-dof manipulators with unconventional design. 2021 9th International Conference on Control, Mechatronics and Automation (ICCMA), 194–199.
He, Y., Li, X., Xu, Z., Zhou, X., & Li, S. (2021). Collaboration of multiple scara robots with guaranteed safety using recurrent neural networks. Neurocomputing, 456, 1–10.
Hsu, D., Jiang, T., Reif, J., & Sun, Z. (2003). The bridge test for sampling narrow passages with probabilistic roadmap planners. 2003 IEEE International Conference on Robotics and Automation (Cat. No. 03CH37422), 3, 4420–4426.
Hsu, D., Latombe, J.-C., & Motwani, R. (1997). Path planning in expansive configuration spaces. Proceedings of International Conference on Robotics and Automation, 3, 2719–2726.
Ichter, B., Harrison, J., & Pavone, M. (2018). Learning sampling distributions for robot motion planning. 2018 IEEE International Conference on Robotics and Automation (ICRA), 7087–7094.
Janson, L., Ichter, B., & Pavone, M. (2018). Deterministic sampling-based motion planning: Optimality, complexity, and performance. The International Journal of Robotics Research, 37(1), 46–61.
Janson, L., Schmerling, E., Clark, A., & Pavone, M. (2015). Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions. The International Journal of Robotics Research, 34(7), 883–921.
Karaman, S., & Frazzoli, E. (2011). Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research, 30(7), 846–894.
Kavraki, L., Svestka, P., Latombe, J.-C., & Overmars, M. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4), 566–580. https://doi.org/10.1109/70.508439
Kavraki, L. E., Svestka, P., Latombe, J.-C., & Overmars, M. H. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4), 566–580.
Khamis, A., Hussein, A., & Elmogy, A. (2015). Multi-robot task allocation: A review of the state-of-the-art. In A. Koubaa & J. Martinez-de Dios (Eds.), Cooperative robots and sensor networks 2015 (pp. 31–51). Springer International Publishing. https://doi.org/10.1007/978-3-319-18299-5_2
Klosowski, J. T., Held, M., Mitchell, J. S., Sowizral, H., & Zikan, K. (1998). Efficient collision detection using bounding volume hierarchies of k-dops. IEEE Transactions on Visualization and Computer Graphics, 4(1), 21–36.
Kuffner, J. J., & LaValle, S. M. (2000). Rrt-connect: An efficient approach to single-query path planning. Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No. 00CH37065), 2, 995–1001.
LaValle, S., & Kuffner, J. (2001). Randomized kinodynamic planning. The International Journal of Robotics Research, 20(5), 378–400. https://doi.org/10.1177/02783640122067453
LaValle, S. (1998). Rapidly-exploring random trees: A new tool for path planning. Research Report 9811.
LaValle, S. M. (2006). Planning algorithms. Cambridge University Press.
Liu, G., De Winter, J., Steckelmacher, D., Hota, R. K., Nowe, A., & Vanderborght, B. (2023). Synergistic task and motion planning with reinforcement learning-based non-prehensile actions. IEEE Robotics and Automation Letters, 8(7), 4370–4377.
Marcucci, T., Petersen, M., von Wrangel, D., & Tedrake, R. (2023). Motion planning around obstacles with convex optimization. Science Robotics, 8(84), eadf7843.
Mazer, E., Ahuactzin, J. M., & Bessiere, P. (1998). The ariadne’s clew algorithm. Journal of Artificial Intelligence Research, 9, 295–316.
Orthey, A., Chamzas, C., & Kavraki, L. E. (2023). Sampling-based motion planning: A comparative review. Annual Review of Control, Robotics, and Autonomous Systems, 7.
Prianto, E., Kim, M., Park, J.-H., Bae, J.-H., & Kim, J.-S. (2020). Path planning for multi-arm manipulators using deep reinforcement learning: Soft actor–critic with hindsight experience replay. Sensors, 20(20), 5911.
Qureshi, A. H., Miao, Y., Simeonov, A., & Yip, M. C. (2020). Motion planning networks: Bridging the gap between learning-based and classical motion planners. IEEE Transactions on Robotics, 37(1), 48–66.
Ratliff, N., Zucker, M., Bagnell, J. A., & Srinivasa, S. (2009). CHOMP: Gradient optimization techniques for efficient motion planning. 2009 IEEE International Conference on Robotics and Automation, 489–494. https://doi.org/10.1109/ROBOT.2009.5152817
Reif, J. H. (1979). Complexity of the mover’s problem and generalizations. 20th Annual Symposium on Foundations of Computer Science (SFCS 1979), 421–427. https://doi.org/10.1109/SFCS.1979.10
Reig, S., Carter, E. J., Fong, T., Forlizzi, J., & Steinfeld, A. (2021). Flailing, hailing, prevailing: Perceptions of multi-robot failure recovery strategies. 2021 16th ACM/IEEE International Conference on Human-Robot Interaction (HRI), 158–167.
Rickert, M., Sieverling, A., & Brock, O. (2014). Balancing exploration and exploitation in sampling-based motion planning. IEEE Transactions on Robotics, 30, 1305–1317. https://doi.org/10.1109/TRO.2014.2340191
Schulman, J., Duan, Y., Ho, J., Lee, A., Awwal, I., Bradlow, H., Pan, J., Patil, S., Goldberg, K., & Abbeel, P. (2014a). Motion planning with sequential convex optimization and convex collision checking. The International Journal of Robotics Research, 33(9), 1251–1270.
Schulman, J., Duan, Y., Ho, J., Lee, A., Awwal, I., Bradlow, H., Pan, J., Patil, S., Goldberg, K., & Abbeel, P. (2014b). Motion planning with sequential convex optimization and convex collision checking. The International Journal of Robotics Research, 33, 1251–1270. https://doi.org/10.1177/0278364914528132
Sharon, G., Stern, R., Felner, A., & Sturtevant, N. R. (2015). Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219, 40–66.
Sharon, G., Stern, R., Goldenberg, M., & Felner, A. (2013). The increasing cost tree search for optimal multi-agent pathfinding. Artificial Intelligence, 195, 470–495.
Solis, I., Motes, J., Sandström, R., & Amato, N. M. (2021). Representation-optimal multi-robot motion planning using conflict-based search. IEEE Robotics and Automation Letters, 6(3), 4608–4615.
Standley, T. (2010). Finding optimal solutions to cooperative pathfinding problems. Proceedings of the AAAI Conference on Artificial Intelligence, 24(1), 173–178.
Standley, T., & Korf, R. (2011). Complete algorithms for cooperative pathfinding problems. IJCAI, 668–673.
Stern, R. (2019). Multi-agent path finding–an overview. Artificial Intelligence: 5th RAAI Summer School, Dolgoprudny, Russia, July 4–7, 2019, Tutorial Lectures, 96–115.
Strub, M. P., & Gammell, J. D. (2020). Adaptively informed trees (AIT*): Fast asymptotically optimal path planning through adaptive heuristics. 2020 IEEE International Conference on Robotics and Automation (ICRA), 3191–3198.
Şucan, I. A., Moll, M., & Kavraki, L. E. (2012). The Open Motion Planning Library. IEEE Robotics & Automation Magazine, 19(4), 72–82. https://doi.org/10.1109/MRA.2012.2205651
Tamizi, M. G., Yaghoubi, M., & Najjaran, H. (2023). A review of recent trend in motion planning of industrial robots. International Journal of Intelligent Robotics and Applications, 1–22.
Van Den Berg, J. P., & Overmars, M. H. (2005). Prioritized motion planning for multiple robots. 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, 430–435.
Verginis, C. K., Dimarogonas, D. V., & Kavraki, L. E. (2022). KDF: Kinodynamic motion planning via geometric sampling-based algorithms and funnel control. IEEE Transactions on Robotics, 39(2), 978–997.
Wagner, G., & Choset, H. (2011). M*: A complete multirobot path planning algorithm with performance bounds. 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, 3260–3267.
Wagner, G., & Choset, H. (2015). Subdimensional expansion for multirobot path planning. Artificial Intelligence, 219, 1–24.
Wang, J., Chi, W., Li, C., Wang, C., & Meng, M. Q.-H. (2020). Neural RRT*: Learning-based optimal path planning. IEEE Transactions on Automation Science and Engineering, 17(4), 1748–1758.
Warren, C. W. (1989). Global path planning using artificial potential fields. 1989 IEEE International Conference on Robotics and Automation, 316–317.
Wilmarth, S. A., Amato, N. M., & Stiller, P. F. (1999). MAPRM: A probabilistic roadmap planner with sampling on the medial axis of the free space. Proceedings 1999 IEEE International Conference on Robotics and Automation (Cat. No. 99CH36288C), 2, 1024–1031.
Ying, K.-C., Pourhejazy, P., Cheng, C.-Y., & Cai, Z.-Y. (2021). Deep learning-based optimization for motion planning of dual-arm assembly robots. Computers & Industrial Engineering, 160, 107603.
Zhang, S., Li, J., Huang, T., Koenig, S., & Dilkina, B. (2022). Learning a priority ordering for prioritized planning in multi-agent path finding. Proceedings of the International Symposium on Combinatorial Search, 15(1), 208–216.
