Incremental Self-Deployment of Multi-Agent Networks in Unknown Environments

Abstract

Utrykkningspersonell i søk- og redningsoperasjoner utsetter seg ofte for ukjente og farlige miljøer. Med den økende kapasiteten til mikrodroner og andre mobile robot-teknologier, kan noen av risikoene utrykkningspersonell tar for å sikre andres velvære til dels elimineres. For eksempel er det mulig å distribuere en sverm av mikrodroner i et miljø og benytte dem som ankerpunkter som tilrettelegger for innendørs lokalisering av utrykkningspersonell og andre, og på denne måten forbedre sikkerheten til alle involverte parter i et søk-og-redningsoppdrag. Denne masteroppgaven fokuserer på det nevnte eksemplet og studerer hvordan multiagent- nettverk kan distribueres i miljøer med ukjent topologi. Mer presist, foreslås og studeres en ny potensialfeltbasert distribuert høynivå kontrollov for distribusjon av mobile agenter med et ukjent kommunikasjonsområde og liten miljøbevissthet. Essensielt for kontrolloven er at den tar for seg trinnvis distribusjon i motsetning til eksisterende litteratur som fokuserer på parallel distribusjon. Først undersøkes og karakteriseres en distribuert kontrollov for trinnvis distribusjon av agenter i et 1-dimensjonalt hinderfritt miljø. Kontrolloven modelleres som en attraktiv kraft mot massesenteret til et sett virtuelle partikler, generert av agenter som allerede befinner seg i miljøet. Betingelser på de virituelle partiklenes på masse og posisjon utledes slik at en økning i nettverksstørrelsen garanterer at nettverket dekker en større del av miljøet. Inspirert av tilnærmingen benyttet for distribusjon i 1-dimensjonale miljøer, utvides kontrolloven for trinnvis distribusjon i ukjente 2-dimensjonale miljøer. Denne høynivå distribuerte kontrolloven består av to deler: a) en kraft som resulterer fra et attraktivt potensialfelt generert av agenter som allerede befinner seg i miljøet, og b) en kraft som skyldes et frastøtende potensialfelt generert av sensormålinger fra avstandssensorer montert på agenten. Simuleringer utføres i to ulike todimensjonale miljøer. I et ti-ganger-ti-meter konvekst miljø viser simuleringer at distribusjon av tilstrekkelig mange agenter gir et nettverk som spenner over en betydelig del av miljøet. I et ikke-konvekst miljø, bestående av blant annet to smale passasjer, viser simuleringer at distribusjon av tilstrekkelig mange agenter i de fleste situasjoner gir et nettverk som spenner over en betydelig del av miljøet. Imidlertid oppstår det situasjoner hvor ingen agenter klarer å passere de smale passasjene, som resulterer i et nettverk som bare spenner over en brøkdel av miljøet. Resultatene som presenteres i denne avhandlingen viser at den foreslåtte høynivå kontrolloven, på dette stadiet, ikke kan anvendes i virkelige situasjoner da den mangler robusthet. Videre må et mål på nettverks-dekning og et kriterium for avslutning av distribusjon, basert utelukkende på informasjon tilgjengelig lokalt for en agent, utvikles for at den foreslåtte kontrolloven skal kunne benyttes og forhåpentligvis gi resultater som direkte kan bidra til å redusere farene søk- og redningspersonell utsetter seg for.

First responders (FRs) in search-and-rescue missions frequently expose themselves to unknown and dangerous environments. Thanks to the increasing capabilities of micro areal vehicles (MAVs) and other mobile agent technologies, some of the risks FRs must take in order to secure the well-being of others can now be mitigated. For example, it is possible to deploy a swarm of MAVs into the environment and use them as beacons that can facilitate the indoor localization of the FRs and others, and in this way, improve the security of all parties involved in search-and-rescue missions. This master’s thesis focuses on the example above and studies how multi-agent networks can be deployed into environments of unknown topology. More precisely, we propose and study a novel potential field-based distributed high-level control law for deploying mobile agents with an unknown range of communication and little environmental awareness. Importantly, this control law considers incremental deployment in opposition to existing literature that focuses instead on simultaneous deployment. Initially, a distributed control law for incremental deployment within a 1-dimensional obstacle-less environment is investigated and fully characterized. By modelling the control law as an attractive force towards the centre of mass of a virtual set of particles generated by agents already residing within the environment, conditions on the particle masses and locations are found so that an increase in network size guarantees that the network spans a larger portion of the environment. Inspired by the approach taken for deployments in 1-dimensional environments, the control law is expanded for incremental deployments within unknown 2-dimensional environments. The proposed distributed high-level control law consists of two parts: a) a force resulting from an attractive potential field generated by agents already residing within the environment, and b) a force resulting from a repulsive potential field generated by sensor readings from range sensors mounted on the agent. Simulations are performed in two different 2-dimensional environments. In a ten-byten meter convex environment, simulations show that deploying sufficiently many agents yields a network that spans a significant portion of the environment. In a non-convex environment including two narrow passages, simulations show that, in most situations, deploying sufficiently many agents yields a network spanning a significant portion of the environment. However, in some situations, no agent manages to pass the narrow passages yielding a network spanning only a fraction of the environment. The results presented in this report show though that the proposed high-level control law cannot yet be utilized in real-world situations as it lacks robustness. Furthermore, a coverage metric and a deployment termination criterion depending only on information available locally for an agent must be synthesized in order for the proposed approach to be applicable and hopefully yield results that can directly reduce the dangers to which FRs expose themselves.