Robots worden steeds beter in staat om zich door de wereld te bewegen, maar het geven van een lijst met instructies over wat ze moeten doen is vaak te rigide voor de chaotische realiteit van een ziekenhuis, een magazijn of een verre planeet. Een simpele lijst kan zeggen "ga hierheen, ga dan daarheen", maar het worstelt met de "wat als"-vragen die het echte leven definiëren: Wat als de robot een gemorste vloeistof ziet en deze moet opruimen? Wat als twee taken binnen een specifieke tijdspanne moeten plaatsvinden, maar niet noodzakelijkerwijs in een vaste volgorde? Jarenlang hebben onderzoekers een methode genaamd timed partial orders gebruikt om dit op te lossen. Denk aan een stroomdiagram waarbij pijlen aangeven welke taken vóór andere moeten plaatsvinden, en klokken ervoor zorgen dat ze binnen bepaalde tijdslimieten worden uitgevoerd. Deze benadering is duidelijk voor mensen en gemakkelijk te verwerken voor computers, maar het heeft een blinde vlek. Het kan niet gemakkelijk complexe tijdsregels tussen ongerelateerde taken afhandelen, noch kan het gemakkelijk zeggen: "Voer deze volgende stap alleen uit als aan een specifieke voorwaarde in de omgeving wordt voldaan."

Een team onderzoekers aan de University of Colorado Boulder heeft een nieuwe manier ontwikkeld om deze kloof te overbruggen, door een systeem te creëren dat ze Conditional Timed Partial Orders noemen. Dit framework stelt ingenieurs in staat om robotmissies te schrijven die veel flexibeler en realistischer zijn. Het nieuwe systeem kan regels afdwingen zoals: "Deze twee taken moeten binnen twintig minuten na elkaar plaatsvinden, ongeacht welke eerst komt," of: "Als de robot in de buurt van een specifiek gebied komt, moet hij onmiddellijk een nieuwe reeks taken uitvoeren." De onderzoekers bewezen dat ze deze complexe, voorwaardelijke missies naar een wiskundig probleem kunnen vertalen dat een computer kan oplossen om het snelst mogelijke pad te vinden. Echter, ze ontdekten ook dat naarmate deze missies ingewikkelder worden, de rekentijd van de computer kan exploderen, waardoor het te traag wordt om nuttig te zijn. Om dit op te lossen, hebben ze een methheid uitgevonden om de enorme, ingewikkelde missie op te splitsen in kleinere, onafhankelijke stukken. Ze losten elk klein stukje afzonderlijk op en voegden de antwoorden vervolgens weer samen. Hun tests toonden aan dat deze benadering het planningsproces tot wel tienduizend keer sneller kan maken dan het proberen op te lossen van de gehele missie in één keer, zonder de kwaliteit van het plan op te offeren.

De kern van dit werk ligt in de manier waarop de onderzoekers de taal hebben uitgebreid die wordt gebruikt om met robots te communiceren. In hun eerdere werk was de missie van een robot een statische kaart van gebeurtenissen. Als een taak op de kaart stond, moest de robot deze uitvoeren. Als er een tijdregel bestond, gold deze voor de hele missie. Het nieuwe systeem introduceert een laag van logica die reageert op de wereld. Stel je een ziekenhuisrobot voor die de opdracht heeft om bloedmonsters te verzamelen en resultaten af te leveren. In het oude systeem zou de robot een vast schema volgen. In het nieuwe systeem kan de robot de instructie krijgen: "Als je toevallig langs de cardiologieafdeling loopt, moet je ook een elektrocardiogramrapport oppakken en binnen vijftien minuten afleveren." De robot hoeft niet vooraf te weten waar de cardiologieafdeling is; hij volgt simpelweg het pad, en als aan de voorwaarde wordt voldaan, worden de extra taken en hun strikte tijdregels automatisch geactiveerd. Dit maakt de instructies voor de robot veel dichter bij hoe een menselijke supervisor opdrachten zou geven, waarbij wordt aangepast aan wat er daadwerkelijk op de grond gebeurt.

Om dit werkend te krijgen, moesten de onderzoekers een moeilijk wiskundig puzzelstuk oplossen. Ze lieten zien dat het vinden van het beste pad voor een robot met deze voorwaardelijke regels hetzelfde is als het oplossen van een complex routingsprobleem, vergelijkbaar met het vinden van de meest efficiënte manier om een reeks locaties met specifieke tijdvensters te bezoeken. Ze vertaalden dit naar een formaat dat computers kunnen oplossen met behulp van een techniek genaamd mixed-integer linear programming. Deze methode garandeert dat de robot een pad vindt dat aan alle regels voldoet, maar het heeft een nadeel. Naarmate het aantal taken en voorwaarden groeit, wordt de omvang van het wiskundige probleem zo groot dat zelfs krachtige computers vast kunnen lopen en uren of dagen nodig hebben om een antwoord te vinden. Dit is een veelvoorkomende bottleneck in de robotica: hoe flexibeler de instructies, hoe moeilijker het voor de computer is om het plan te bedenken.

De oplossing van de onderzoekers was om te stoppen met het proberen op te lossen van het hele probleem tegelijkertijd. Ze realiseerden zich dat veel missies bestaan uit kleinere, zelfstandige groepen taken die nauw met elkaar verbonden zijn, maar slechts losjes verbonden zijn met de rest van de missie. Bijvoorbeeld, een reeks schoonmaaktaken die worden getriggerd door een morsing, kan een zelfstandige eenheid zijn die begint wanneer de robot de morszone betreedt en eindigt wanneer hij deze verlaat. De onderzoekers ontwikkelden een algoritme om deze groepen, of "sub-taken", binnen de grotere missie automatisch te vinden. Ze losten vervolgens de timing en het pad voor elke kleine groep onafhankelijk op. Zodra ze het beste pad voor elke kleine groep hadden, behandelden ze elke groep als een enkele stap in de grotere missie, waarbij ze de tijd die nodig was om die groep te voltooien, invoerden. Dit veranderde één enorme, onoplosbare puzzel in een reeks kleine, gemakkelijke puzzels.

De resultaten van deze benadering waren opmerkelijk. In hun tests vergeleken de onderzoekers hun nieuwe methode met de oude manier van het oplossen van de gehele missie in één keer. Voor eenvoudige missies waren beide methoden snel. Maar naarmate de missies complexer werden, met meer voorwaarden en striktere tijdregels, vertraagde de oude methode drastisch, soms minuten of zelfs uren. De nieuwe decompositie-methode bleef echter snel en loste dezelfde problemen vaak in minder dan een seconde op. In de moeilijkste gevallen was de nieuwe methode tot wel tienduizend keer sneller. Cruciaal was dat de onderzoekers wiskundig bewezen dat deze snelheid niet ten koste ging van de kwaliteit. De plannen gegenereerd door de missie in stukken te verdelen, waren net zo goed als de plannen gegenereerd door het geheel in één keer op te lossen. Ze vonden dezelfde optimale paden en voldeden aan dezelfde tijdregels.

De onderzoekers demonstreerden dit met twee scenario's uit de echte wereld. In het ene scenario moest een robot in een magazijn drie planken bezoeken en terugkeren naar een dock. Als de robot een pad nam dat een olievlek kruiste, was hij verplicht om drie specifieke gebieden schoon te maken voordat hij verder kon gaan. Het systeem plande succesvol een route die de vlek indien mogelijk vermeed, maar als de kortste route vereiste dat de vlek werd overgestoken, voegde de robot automatisch de schoonmaaksequentie in zijn plan in, waarbij werd gewaarborgd dat de schoonmaak binnen de vereiste tijdlimieten werd voltooid. In een tweede scenario moest een Mars-rover bodemmonsters analyseren. Als de rover langs een specifieke rotsformatie reed, moest hij naar een nieuwe locatie navigeren en binnen een strikt tijdvenster een monster verzamelen. Het systeem plande een route die de rotsformatie indien mogelijk vermeed, maar wanneer het terrein de rover dwong om erlangs te rijden, paste het plan zich naadloos aan om de extra monsternemingstaak te bevatten.

Dit werk vormt een belangrijke stap vooruit in het autonomer en aanpasbaarder maken van robots. Door de missiespecificaties zowel voorwaardelijk als temporeel complex te maken, hebben de onderzoekers ingenieurs een instrument gegeven om instructies te schrijven die natuurlijker aanvoelen en minder breekbaar zijn. Het vermogen om deze complexe instructies op te splitsen in beheersbare stukken betekent dat robots nu missies kunnen afhanden die voorheen computationeel te zwaar waren om te plannen. De onderzoekers merkten op dat hoewel hun huidige werk zich richt op enkelvoudige robots, de volgende stap is om dit framework uit te breiden naar groepen robots die samenwerken. Voor nu vormt de methode een robuuste manier om ervoor te zorgen dat wanneer een robot de opdracht krijgt om iets complex te doen in een veranderende wereld, hij snel en correct kan uitzoeken hoe hij dat precies moet doen.