Het snel en betrouwbaar coördineren van multi-agent systemen
- StanServaes
Herinner je je die ene keer nog, toen je op het voetpad iemand tegenkwam en jullie elkaar langs dezelfde kant probeerden te passeren? Je zette dan een stap in de andere richting, maar je tegenligger had hetzelfde idee. Na een paar keer heen en weer wiebelen geraakte je erlangs, al vond je het toch wat ongemakkelijk. Stel je nu voor dat je met z’n drieën op elkaar afkwam, of met vijf, tien of zelfs meer! Dat valt niet zo gemakkelijk meer te coördineren.
Dit probleem is echter niet beperkt tot onze sociale omgeving, maar kent talloze analoge versies in de ingenieurswereld. Of het nu gaat om robots, drones, satellieten of transport in een fabriek: het simultaan plannen en coördineren van hun bewegingen is van cruciaal belang. Om het algemeen te houden, worden ze vaak ook ‘multi-agent systemen’ genoemd, waarbij de ‘agents’ bijvoorbeeld transportkarretjes voorstellen.
Onze scriptie spitst zich toe op die laatste toepassing. De industrie kan zich namelijk geen tijdsverlies of opstoppingen veroorloven op de productielijn of in de fabriek, omdat de beweging van de karretjes niet goed gecoördineerd is. Bijgevolg schreeuwt men om zogenaamde bewegingsplanners: algoritmes die dit pittige coördinatieprobleem voor meerdere karretjes op een efficiënte manier kunnen aanpakken.
Alles in één klap
Een populaire methode om zo’n bewegingsplanner te maken, is met Model Predictieve Controle – kortweg MPC. Dit is een wiskundige optimalisatietechniek die de beste trajecten kan vinden voor de karretjes en tegelijk rekening kan houden met bepaalde beperkingen, zoals snelheidslimieten. Je kan zelfs kiezen hoe je ‘de beste trajecten’ definieert. Zo kan je de duur van het traject minimaliseren, maar ook het energieverbruik, indien je ecologischer te werk wilt gaan.
Wanneer het algoritme de trajecten van alle karretjes tegelijk berekent, in één stap, spreekt men van centrale MPC. Het werkt namelijk alsof het algoritme van bovenaf naar de situatie kijkt. Hierdoor heeft het alle informatie om de trajecten van ieder karretje tegelijk te plannen. Dit zorgt dus voor een zeer goede coördinatie en fantastische resultaten.
Maar het verhaal eindigt hier nog niet. Er is namelijk één groot nadeel: deze centrale optimalisatieproblemen zijn enorm complex en vergen veel te veel rekentijd, zelfs voor krachtige industriële computers. Dit ondermijnt natuurlijk de nodige flexibiliteit van de bewegingsplanner, want de karretjes hebben geen tijd om minutenlang op het resultaat van deze berekeningen te wachten! En het wordt alleen maar erger naarmate er meer karretjes bijkomen. Hierdoor zijn onderzoekers op zoek gegaan naar snellere bewegingsplanners.
Toch iedereen voor zich
Om het optimalisatieprobleem lichter te maken, richtte de literatuur zich op de zogenaamde ‘gedecentraliseerde methoden’, waarbij het probleem wordt opgesplitst per karretje. Deze deelproblemen zijn bijgevolg veel lichter en kunnen parallel worden opgelost, wat leidt tot snellere berekeningen.
Uiteraard moeten de karretjes nog steeds met elkaar communiceren om rond elkaar te kunnen plannen. Het nieuwe algoritme moet dus iteratief zijn: de karretjes berekenen eerst elk hun eigen optimale traject, waarna ze hun intenties met elkaar communiceren. Vervolgens herwerken ze hun plan om met elkaar rekening te houden. Dit proces herhaalt zich totdat de karretjes tot een consensus komen, wat betekent dat ze elk een optimaal traject hebben gevonden dat niet met de rest botst.
Dus, probleem opgelost? Helaas. Het nieuwe algoritme is wel sneller, maar in de praktijk komen de karretjes niet altijd tot een consensus — althans niet in het soort coördinatieprobleem dat we in deze scriptie willen oplossen. Dat betekent dat de trajecten niet zo optimaal zijn als verwacht en, erger nog, dat het algoritme niet alle botsingen kan vermijden. Dit is natuurlijk absoluut onaanvaardbaar in de industrie, en evenzeer in andere toepassingen.
Het beste uit beide werelden
De veilige alternatieven voor gedecentraliseerde methoden proberen op allerlei manieren de karretjes toch tot consensus te dwingen. Helaas kan men dit enkel onder strikte voorwaarden garanderen, wat tot serieuze beperkingen leidt.
Deze scriptie zoekt een oplossing in een ander concept binnen de robotica: de zogenaamde ‘control barrier functions’. Dit is een wiskundig concept dat kan worden gebruikt om een soort barrière te vormen die bepaalde oplossingen uitsluit — bijvoorbeeld onveilige trajecten.
Het idee om deze te combineren met gedecentraliseerde methoden is zeer recent ook in de literatuur verschenen, al was dit nog steeds bedoeld om de karretjes tot consensus te dwingen. Deze scriptie tracht echter de beperkende voorwaarden die hierbij komen kijken te omzeilen, door de control barrier functions te gebruiken in een extra centrale ‘veiligheidsstap’ aan het einde van het gedecentraliseerde algoritme.
Deze extra stap corrigeert de originele trajecten door voor alle karretjes tegelijk het meest aansluitende traject te zoeken dat wél veilig is. Er hoeven dus geen trajecten vanaf nul te worden berekend, wat ervoor zorgt dat deze stap verwaarloosbaar snel kan worden uitgevoerd. Resultaat? Een hybride algoritme dat de voordelen van de centrale en gedecentraliseerde methoden combineert. Het is praktisch even snel als het gedecentraliseerde algoritme, maar wél veilig!
Van theorie naar praktijk
Theorie is één ding, maar kan het ook werken in de praktijk? Hiervoor werd het hybride algoritme eerst uitgebreid getest in simulaties om na te gaan wat de invloed is van de verschillende parameters, én of de trajecten wel echt veilig zijn. Daarna hebben we het geïmplementeerd op een industrieel systeem (de zogenaamde XPlanar van Beckhoff) dat karretjes magnetisch kan laten zweven en aansturen in alle richtingen. Ter demonstratie stellen we een YouTube-filmpje ter beschikking van onze experimenten in het labo: https://youtu.be/sBp-01f-Wow
Hieruit blijkt dat het hybride algoritme ook in de praktijk wel degelijk in staat is om snel genoeg de trajecten te berekenen, zodat de karretjes veilig en zonder vertraging kunnen worden aangestuurd.
Maar wat betekent dit nu voor jou? Wel, algoritmes die de efficiëntie in de industrie kunnen verhogen, bieden de mogelijkheid voor productiviteitsgroei en bijgevolg een stijging van onze welvaart. Dat klinkt misschien ver van huis, maar wie weet kan je er ook in het dagelijks leven iets van opsteken. Herinner je je die ongemakkelijke momentjes op straat nog? De volgende keer dat je iemand moet kruisen, kan je de bovenstaande strategie eens proberen!
Bibliografie
[1] C++ class template for std::barrier. https://en.cppreference.com/w/cpp/ thread/barrier.html. Accessed: 02/06/2025.
[2] Mumps home page. https://mumps-solver.org/index.php?page=home. Accessed: 02/06/2025.
[3] A. D. Ames, S. Coogan, M. Egerstedt, G. Notomista, K. Sreenath, and P. Tabuada. Control barrier functions: Theory and applications. In 2019 18th European control conference (ECC), pages 3420–3431. Ieee, 2019.
[4] J. A. Andersson, J. Gillis, G. Horn, J. B. Rawlings, and M. Diehl. Casadi: a software framework for nonlinear optimization and optimal control. Mathematical Programming Computation, 11:1–36, 2019.
[5] B. Automation. Beckhoff information system. Technical report. https:// infosys.beckhoff.com/index_en.htm , Accessed: 5/05/2025.
[6] Beckhoff. Xplanar | planar motor system. https://www.beckhoff.com/en-en/ products/motion/xplanar-planar-motor-system/, Accessed: 05/05/2025.
[7] U. Borrmann, L. Wang, A. D. Ames, and M. Egerstedt. Control barrier certificates for safe swarm behavior. IFAC-PapersOnLine, 48(27):68–73, 2015.
[8] S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends® in Machine learning, 3(1):1–122, 2011.
[9] M. Chahine, R. Firoozi, W. Xiao, M. Schwager, and D. Rus. Local noncooperative games with principled player selection for scalable motion planning. In 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 880–887. IEEE, 2023.
[10] J. Chen. A brief tutorial on consensus admm for distributed optimization with applications in robotics. arXiv preprint arXiv:2410.03753, 2024.
[11] J. Choi. Introduction to control lyapunov functions and control barrier functions, 2021. Guest lecture at University of California, San Diego, https://www. youtube.com/watch?v=_Tkn_Hzo4AA.
[12] W. Decr. Specialised lecture 2: Optimal control. Slides from optimization of mechatronic systems [H04U1C], KU Leuven.
[13] H. J. Ferreau, C. Kirches, A. Potschka, H. G. Bock, and M. Diehl. qpoases: A parametric active-set algorithm for quadratic programming. Mathematical Programming Computation, 6:327–363, 2014.
[14] J. Gillis, B. Vandewal, G. Pipeleers, and J. Swevers. Effortless modeling of optimal control problems with rockit. In 39th Benelux Meeting on Systems and Control, Date: 2020/03/10-2020/03/12, Location: Elspeet, The Netherlands, 2020.
[15] T. Goldstein, B. O’Donoghue, S. Setzer, and R. Baraniuk. Fast alternating direction optimization methods. SIAM Journal on Imaging Sciences, 7(3):1588– 1623, 2014.
[16] P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100–107, 1968.
[17] C. Jiang and Y. Guo. Incorporating control barrier functions in distributed model predictive control for multirobot coordinated control. IEEE Transactions on Control of Network Systems, 11(1):547–557, 2023.
[18] Y. Koren, J. Borenstein, et al. Potential field methods and their inherent limitations for mobile robot navigation. In Icra, volume 2, pages 1398–1404, 1991.
[19] S. LaValle. Rapidly-exploring random trees: A new tool for path planning. Research Report 9811, 1998.
[20] C. Liu, C.-Y. Lin, and M. Tomizuka. The convex feasible set algorithm for real time optimization in motion planning. SIAM Journal on Control and optimization, 56(4):2712–2733, 2018.
[21] C. E. Luis and A. P. Schoellig. Trajectory generation for multiagent point-topoint transitions via distributed model predictive control. IEEE Robotics and Automation Letters, 4(2):375–382, 2019.
[22] T. Mercy, R. Van Parys, and G. Pipeleers. Spline-based motion planning for autonomous guided vehicles in a dynamic environment. IEEE Transactions on Control Systems Technology, 26(6):2182–2189, 2017.
[23] P. Patrinos. Optimization. Lecture notes from Optimization [H03E3A], KU Leuven.
[24] Z. Qin, K. Zhang, Y. Chen, J. Chen, and C. Fan. Learning safe multiagent control with decentralized neural barrier certificates. arXiv preprint arXiv:2101.05436, 2021.
[25] J. B. Rawlings, D. Q. Mayne, M. Diehl, et al. Model predictive control: theory, computation, and design, volume 2. Nob Hill Publishing Madison, WI, 2017.
[26] F. Rey, Z. Pan, A. Hauswirth, and J. Lygeros. Fully decentralized admm for coordination and collision avoidance. In 2018 European Control Conference (ECC), pages 825–830. IEEE, 2018.
[27] A. Sathya, P. Sopasakis, R. Van Parys, A. Themelis, G. Pipeleers, and P. Patrinos. Embedded nonlinear model predictive control for obstacle avoidance using panoc. In 2018 European Control Conference (ECC), pages 1523–1528, 2018.
[28] O. Shorinwa, T. Halsted, J. Yu, and M. Schwager. Distributed optimization methods for multi-robot systems: Part 1a tutorial [tutorial]. IEEE Robotics & Automation Magazine, 31(3):121–138, 2024.
[29] O. Shorinwa, T. Halsted, J. Yu, and M. Schwager. Distributed optimization methods for multi-robot systems: Part 2a survey. IEEE Robotics & Automation Magazine, 31(3):154–169, 2024.
[30] Z. Tian, Z. Zhang, and R. Jin. Distributed admm for time-varying communication networks. In 2022 IEEE 96th Vehicular Technology Conference (VTC2022-Fall), pages 1–5. IEEE, 2022.
[31] R. Van Parys and G. Pipeleers. Online distributed motion planning for multivehicle systems. In 2016 European Control Conference (ECC), pages 1580–1585. IEEE, 2016.
[32] R. Van Parys and G. Pipeleers. Distributed mpc for multi-vehicle systems moving in formation. Robotics and Autonomous Systems, 97:144–152, 2017.
[33] L. Vanroye, A. Sathya, J. De Schutter, and W. Decré. Fatrop: A fast constrained optimal control problem solver for robot trajectory optimization and control. In 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 10036–10043. IEEE, 2023.
[34] A. Wächter and L. T. Biegler. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical programming, 106:25–57, 2006.
[35] L. Wang, A. D. Ames, and M. Egerstedt. Safety barrier certificates for collisionsfree multirobot systems. IEEE Transactions on Robotics, 33(3):661–674, 2017.
[36] W. Wang, W. Xiao, A. Gonzalez-Garcia, J. Swevers, C. Ratti, and D. Rus. Robust model predictive control with control barrier functions for autonomous surface vessels. In 2024 IEEE International Conference on Robotics and Automation (ICRA), pages 6089–6095. IEEE, 2024.
[37] W. Xiao and C. Belta. High-order control barrier functions. IEEE Transactions on Automatic Control, 67(7):3655–3662, 2021.
[38] Y. Yang, X. Guan, Q.-S. Jia, L. Yu, B. Xu, and C. J. Spanos. A survey of admm variants for distributed optimization: Problems, algorithms and features. arXiv preprint arXiv:2208.03700, 2022.
[39] X. Zhang, A. Liniger, and F. Borrelli. Optimization-based collision avoidance. IEEE Transactions on Control Systems Technology, 29(3):972–983, 2020.
[40] H. Zhou and C. Liu. Distributed motion coordination using convex feasible set based model predictive control. In 2021 IEEE International Conference on Robotics and Automation (ICRA), pages 8330–8336. IEEE, 2021.
[41] V. Zinage, A. Jha, R. Chandra, and E. Bakolas. Decentralized safe and scalable multi-agent control under limited actuation. arXiv preprint arXiv:2409.09573, 2024.
