211service.com
Hoedenrobots en andere 'multi-agentsystemen'
Een programma schrijven om een enkele autonome robot te besturen die door een onzekere omgeving navigeert met een grillige communicatieverbinding is al moeilijk genoeg; schrijf er een voor meerdere robots die al dan niet samen moeten werken, afhankelijk van de taak, is nog moeilijker.
Als gevolg hiervan hebben ingenieurs die controleprogramma's ontwerpen voor multi-agentsystemen - of het nu teams van robots of netwerken van apparaten met verschillende functies zijn - zich over het algemeen beperkt tot speciale gevallen, waar betrouwbare informatie over de omgeving kan worden aangenomen of een relatief eenvoudige samenwerkingstaak duidelijk kan worden vooraf opgegeven.
In mei, tijdens de Internationale Conferentie over Autonomous Agents and Multiagent Systems, hebben onderzoekers van MIT's Laboratorium voor computerwetenschappen en kunstmatige intelligentie (CSAIL) zal een nieuw systeem presenteren dat bestaande controleprogramma's aan elkaar hecht, zodat multiagentsystemen op veel complexere manieren kunnen samenwerken. Het systeem houdt rekening met onzekerheid - bijvoorbeeld de kans dat een communicatieverbinding wegvalt, of dat een bepaald algoritme een robot per ongeluk in een doodlopende weg stuurt - en plant er automatisch omheen.
Voor kleine samenwerkingstaken kan het systeem garanderen dat de combinatie van programma's optimaal is - dat het de best mogelijke resultaten zal opleveren, gezien de onzekerheid van de omgeving en de beperkingen van de programma's zelf.
In samenwerking met Jon How, de Richard Cockburn Maclaurin Professor of Aeronautics and Astronautics, en zijn student Chris Maynor, testen de onderzoekers momenteel hun systeem in een simulatie van een warehousing-applicatie, waarbij teams van robots willekeurige objecten van onbepaalde locaties, waar nodig samenwerken om zware ladingen te vervoeren. Bij de simulaties zijn kleine groepen iRobot Creates betrokken, programmeerbare robots die hetzelfde chassis hebben als de Roomba-stofzuiger.
Gerede twijfel
In [multiagent]-systemen is het in de echte wereld over het algemeen erg moeilijk voor hen om effectief te communiceren, zegt Christopher Amato, een postdoc bij CSAIL en eerste auteur van het nieuwe artikel. Als je een camera hebt, is het onmogelijk voor de camera om constant al zijn informatie naar alle andere camera's te streamen. Evenzo bevinden robots zich op netwerken die onvolmaakt zijn, dus het kost wat tijd om berichten naar andere robots te krijgen, en misschien kunnen ze in bepaalde situaties rond obstakels niet communiceren.
Een agent heeft misschien niet eens perfecte informatie over zijn eigen locatie, zegt Amato, bijvoorbeeld in welk gangpad van het magazijn hij zich daadwerkelijk bevindt. Bovendien, als je een beslissing probeert te nemen, is er enige onzekerheid over hoe dat zich gaat ontvouwen, zegt hij. Misschien probeer je in een bepaalde richting te bewegen en is er sprake van wind- of wielslip, of is er onzekerheid over netwerken als gevolg van pakketverlies. Dus in deze real-world domeinen met al deze communicatieruis en onzekerheid over wat er gebeurt, is het moeilijk om beslissingen te nemen.
Het nieuwe MIT-systeem, dat Amato heeft ontwikkeld met co-auteurs Leslie Kaelbling, de Panasonic-hoogleraar Computer Science and Engineering, en George Konidaris, een collega-postdoc, heeft drie input nodig. Een daarvan is een reeks low-level controle-algoritmen - die de MIT-onderzoekers macro-acties noemen - die het gedrag van agenten collectief of individueel kunnen regelen. De tweede is een reeks statistieken over de uitvoering van die programma's in een bepaalde omgeving. En de derde is een schema voor het waarderen van verschillende uitkomsten: het uitvoeren van een taak levert een hoge positieve waardering op, maar het verbruiken van energie levert een negatieve waardering op.
School van harde klappen
Amato stelt zich voor dat de statistieken automatisch kunnen worden verzameld door een systeem met meerdere agenten een tijdje te laten draaien - in de echte wereld of in simulaties. In de warehousing-applicatie zouden de robots bijvoorbeeld verschillende macro-acties uitvoeren en zou het systeem gegevens over resultaten verzamelen. Robots die in het magazijn van punt A naar punt B proberen te gaan, kunnen een bepaald percentage van de tijd in een doodlopende straat terechtkomen, en hun communicatiebandbreedte kan een ander percentage van de tijd dalen; die percentages kunnen variëren voor robots die van punt B naar punt C gaan.
Het MIT-systeem neemt deze invoer en beslist vervolgens hoe macro-acties het beste kunnen worden gecombineerd om de waardefunctie van het systeem te maximaliseren. Het kan alle macro-acties gebruiken; het kan slechts een kleine subset gebruiken. En het zou ze kunnen gebruiken op manieren waar een menselijke ontwerper niet aan zou hebben gedacht.
Stel bijvoorbeeld dat elke robot een kleine reeks gekleurde lichten heeft die hij kan gebruiken om met zijn tegenhangers te communiceren als hun draadloze verbindingen niet beschikbaar zijn. Wat meestal gebeurt, is dat de programmeur besluit dat rood licht betekent naar deze kamer gaan en iemand helpen, groen licht betekent naar die kamer gaan en iemand helpen, zegt Amato. In ons geval kunnen we gewoon zeggen dat er drie lichten zijn, en het algoritme spuugt uit of ze al dan niet moeten worden gebruikt en wat elke kleur betekent.
Het werk van de MIT-onderzoekers omschrijft het probleem van multi-agent control als iets dat een gedeeltelijk waarneembaar Markov-beslissingsproces of POMDP wordt genoemd. POMDP's, en vooral Dec-POMDP's, de gedecentraliseerde versie, zijn in principe onhandelbaar voor echte multirobot-problemen omdat ze zo complex en rekenkundig duur zijn om op te lossen dat ze gewoon exploderen als je het aantal robots verhoogt, zegt Nora Ayanian, een assistent hoogleraar computerwetenschappen aan de Universiteit van Zuid-Californië, gespecialiseerd in multirobotsystemen. Ze zijn dus niet echt populair in de multirobotwereld.
Normaal gesproken, als je deze Dec-POMDP's gebruikt, werk je op een zeer laag niveau van granulariteit, legt ze uit. Het interessante van dit artikel is dat ze deze zeer complexe tools gebruiken en de resolutie enigszins verlagen.
Dit zal deze POMDP's zeker op de radar krijgen van mensen met multirobotsystemen, voegt Ayanian toe. Het is iets dat het echt veel beter in staat maakt om op complexe problemen te worden toegepast.