| Abstract | This dissertation presents a controller design framework and algorithms for controlling formations of autonomous vehicles. It addresses all three fundamental issues of formation control, namely establishing formations, navigating in formation through an obstacle-ridden environment, and switching between different formations. These issues are treated both in a centralized and a decentralized way. To deal with the complexity of multi-vehicle control, we propose a formation abstraction by the means of a virtual rectangular grid. This grid-based approach enables the decoupling of group motion and formation configuration. The grid acts as a virtual leader, keeping the formation together and providing tracking references for the vehicles. Formations are represented in discrete space, as grid cell occupations. Transitions between different formations are modeled using a matrix-based framework that is well-established in the manufacturing systems domain, yet it has not been applied to multi-vehicle coordination problems before. We use it to design provably correct and safe transition sequences between arbitrary formations. Combined with algorithms for selecting appropriate evasion formations, the transition scheduling algorithm enables safe formation navigation in obstacle-ridden environments. The discrete event scheduling strategy operates with the assumption that vehicles can transition between two neighboring grid cells without entering any of the other cells. We provide a controller tuning procedure which insures that the vehicle-level motion controllers can satisfy such performance guarantees. We also develop a hybrid controller architecture which integrates group motion control, discrete-event formation transition scheduling and vehicle-level motion controllers into a coherent formation control framework. Simulated and experimental results confirm the capability of our architecture to deal with all aspects of formation control, from assembling formations to safe navigation through environments with obstacles. |
| Abstract (croatian) | U ovoj disertaciji opisani su postupci projektiranja sustava upravljanja i algoritmi za upravljanje formacijama autonomnih vozila. Obrađena su tri fundamentalna problema upravljanja formacijama: uspostavljanje formacije, navigacija kroz okolinu s preprekama uz održavanje formacije, te promjena formacije. Razmotreni su centralizirani i decentralizirani pristupi navedenim problemima. Kao odgovor na složenost upravljanja skupinom vozila, uvedena je apstrakcija formacije korištenjem virtualne pravokutne mreže. Ovakav pristup, temeljen na mrežastom modelu prostora, omogućuje rasprezanje problema upravljanja gibanjem skupine vozila i upravljanja konfiguracijom formacije. Mrežasti model preuzima ulogu virtualnog vođe, koji drži formaciju na okupu dajući reference za slijeđenje vozilima. Formacije su modelirane u diskretiziranom prostoru, kao zauzeća pojedinih ćelija na mreži. Promjene formacija su modelirane korištenjem matričnog modela koji je široko prihvaćen u području fleksibilnih proizvodnih sustava, ali do sada nije primjenjivan na probleme koordinacije skupine vozila. Matrični je model korišten za dizajn pouzdano ispravnih i sigurnih prijelaznih sekvenci između proizvoljno odabranih formacija. Uz korištenje odgovarajućih algoritama za odabir formacije pri izbjegavanju prepreka, algoritam raspoređivanja prijelaznih sekvenci osigurava sigurnu navigaciju grupe vozila u formaciji kroz prostor s preprekama. Strategija raspoređivanja prijelaza kao diskretnih događaja djeluje pod pretpostavkom da vozila mogu prijeći između dvije susjedne ćelije mreže, bez da pri tome zađu u bilo koju drugu ćeliju. U okviru disertacije razvijene su procedure podešavanja slijednih regulatora vozila u formaciji, koje osiguravaju da trajektorije svih vozila zadovoljavaju navedenu pretpostavku u svakom trenutku. Također, razvijena je hibridna upravljačka arhitektura koja ujedinjuje upravljanje gibanjem skupine, raspoređivanje prijelaznih sekvenci u diskretnom vremenu i upravljanje gibanjem pojedinog vozila u koherentan upravljački sustav. Mogućnosti opisane upravljačke arhitekture potvrđene su u simulacijama i eksperimentima koji uključuju sve vidove upravljanja formacijama, od uspostavljanja do sigurne navigacije kroz okoline s preprekama. Poglavlje 1 daje kratak povijesni pregled razvoja robotike i osvrt na trenutačna znanstvena i tehnološka dostignuća u ovoj relativno mladoj, ali vrlo propulzivnoj grani znanosti. Motivacija za proučavanje problema upravljanja formacijama dana je kroz analogiju s različitim biološkim i tehničkim sustavima koji gibanjem u formaciji povećavaju učinkovitost svog djelovanja. U Poglavlju 2 detaljno je opisan problem upravljanja formacijama. Dan je pregled aktualnih znanstvenih dostignuća na ovom području te je navedeno nekoliko potencijalnih područja primjene koja s razmatrana pri izradi disertacije. Neformalno su opisani konkretni problemi i pretpostavke pod kojima su razmatrani, te su uvedene posebne oznake koje se koriste u daljnjem tekstu. Metodologija projektiranja diskretnog algoritma za upravljanje formacijama, temeljenog na matričnom modelu, obrađena je u Poglavlju 3. Primjena ovog modela, prenesenog iz područja upravljanja fleksibilnim proizvodnim sustavima, na probleme upravljanja formacijama, predstavlja jednu od inovacija disertacije. Matrični model izveden je na temelju mrežastog modela kojim su predstavljene formacije, i omogućuje projektiranje algoritama promjene formacije koji su pouzdano ispravni i bez sudara među vozilima Poglavlje 4 posvećeno je postupcima koji grupi vozila omogućuju uspostavljanje formacije i odabir ispravne formacije za izbjegavanje prepreka. Uspostavljanje formacije iz proizvoljnih početnih uvjeta, koje se u literaturi naziva rendezvous problem, riješeno je postupnim skaliranjem pravokutne mreže. Razmotrene su dvije metode odabira formacije za izbjegavanje prepreka, jedna temeljena na heurističkim pravilima, i druga temeljena na mjeri sličnosti skupova. Nakon prethodnih poglavlja, u kojima se upravljanje formacijama obrađuje na apstraktnom nivou, u Poglavlju 5 razmatramo praktične zahtjeve koji moraju biti zadovoljeni, kako bi se ranije opisane metode mogle primijeniti na stvarnim vozilima. Opisan je hibridni upravljački sustav, koji integrira upravljanje gibanjem pojedinim vozilom na najnižoj razini s algoritmima upravljanja formacijom na apstraktnoj razini. Također, predstavljeni su postupci podešavanja slijednih regulatora koji osiguravaju dosljedno ispunjavanje pretpostavki koordinacijskih algoritama više razine. U Poglavlju 6 su rezultati prethodnih poglavlja prošireni na decentraliziraniji scenarij. U razmatranom slučaju, većina proračuna za uspostavljanje i promjenu formacija se izvodi na ugradbenim računalima vozila, a podaci nužni za koordinaciju se izmjenjuju preko bežične mreže. Poglavlje 7 je posvećeno simulacijama i eksperimentima kojima se ispituje valjanost i kvaliteta izvođenja opisanih algoritama. Predstavljeni su rezultati opširnih simulacija koje uključuju grupe do devet vozila. Eksperimenti su provedeni u zatvorenom i otvorenom prostoru, na grupi od tri autonomna vozila. Zaključna razmatranja i pregled znanstvenih doprinosa disertacije izloženi su u Poglavlju 8. |
