Real-Time Strategy game inspired Multi-Agent path planning

Abstract

Bruken av autonome roboter og robotstyring står i fokus for nåtidens industrielle og vitenskapelige forskning. Ved bruk avansert teknologi kan samfunnet nå håndtere kompliserte og farlige situasjoner ved å bruke fjernstyrte enheter overvåket av mennesker. Til tross for store fremskritt innen kontroll av individuelle roboter eller små grupper av roboter, er det fortsatt behov for metoder for effektiv håndtering av store robotsvermer. Real-time strategy(RTS)-spill har lenge kunnet kontrollere hundrevis av enheter effektivt, men det er et hull i forskningen mellom robotikk- og spillindustrien. Denne masteroppgaven ønsker å bygge videre på broen mellom disse feltene ved å undersøke eksisterende metoder i begge felt for å finne tilnærminger og prinsipper brukt i spillutvikling som er overførbare til kontroll av store robotsvermer.

I denne oppgaven vil det bli presentert en oversikt over eksisterende metoder for multi-agentkontroll, samt designprinsipper for å forbedre brukeropplevelsen basert på prinsipper fra videospillutvikling og menneske maskin-interaksjon (MMI). En responsiv asynkron multi-agent-stiplanlegger med robust statisk kollisjonsunngåelse er utviklet og implementert, sammen med visuelle hjelpemidler og tekstbaserte tilbakemeldingsverktøy for å forbedre ytelsen ved å gi operatøren en intuitiv brukeropplevelse. Planleggeren er basert på en eksisterende implementering av en raskt-utforskende tilfeldig grafalgoritme i kombinasjon med et probabilistisk veikart for å muliggjøre håndtering av flere forespørsler på samme grafstruktur. Algoritmene er designet for å operere i høy-dimensjonale ikke-konvekse miljøer, og den foreslåtte planleggeren vil bli demonstrert i en rekke miljøer for å vise hvordan operasjonsmiljøet påvirker planleggerens ytelse. Planleggeren er designet for å passe inn i en større arkitektur inspirert av eksisterende toppmoderne AI systemer utviklet for å spille RTS-spill. Arbeidet utført i denne oppgaven vil forhåpentligvis inspirere videre forskning og utvikling for å bygge broen mellom spillindustrien og robotikk for å oppnå effektive systemer for storskala kontroll av robotsvermer.

The use of robotic control and autonomous robots is at the forefront of today’s industry and scientific research. With the help of advanced technology, society can now handle complicated and hazardous situations using remotely operated units overseen by humans. Despite great strides in controlling individual robots and even small groups of robots, there is still a need for methods to manage large teams of robots effectively. Real-time strategy(RTS) games have long been able to control hundreds of units effectively, but more research needs to be conducted between the fields of robotics and gaming to bridge the gap. This master’s thesis aims to further bridge this gap by examining existing methods in both fields to find the approaches and principles used in gaming that are translatable for controlling large-scale robotic teams.

This thesis will present an overview of existing methods for multi-agent control, as well as design principles based on principles from gaming and the field of Human-Computer Interaction(HCI) to elevate user experience. A responsive asynchronous multi-agent path planner with robust static collision avoidance is developed and implemented, along with visual aids and text-based feedback tools, to enhance performance by giving the operator an intuitive user experience. The planner is based on an existing implementation of a rapidly-exploring random graph algorithm in combination with a probabilistic roadmap to provide the ability to handle multiple queries on the same graph structure. The algorithms are designed to operate in high-dimensional non-convex environments and the proposed planner will be demonstrated in a range of environments to showcase how they affect performance. The planner is designed to fit in a more extensive architecture inspired by existing state-of-the-art AI systems developed for playing RTS games. The work done in this thesis will hopefully inspire further research and development to bridge the gap between gaming and robotics to achieve effective systems for large-scale control of robotic teams.