DIANA : Distributed and Safe Autonomous Navigation for a Swarm of Autonomous Vehicles

Abstract

The autonomous systems are typical examples of complex distributed cyber-physical systems (CPS). The main characteristics of such systems is the use of autonomous vehicles. They are increasingly used in various mission-critical tasks such as surveillance and rescue operations. To execute the required tasks, the autonomous swarm systems should fulfil such important dependability requirements as safety and reliability. On the hand, while designing a swarm system, we should guarantee that the robotic systems in the swarm do not collide with each other and objects in the operating environment, i.e., ensure motion safety. On the other hand, to ensure that the robots have sufficient resources to reliably complete the required goals, we should also achieve efficiency while implementing the swarm mission, i.e., minimise the travelling distance of the robots vehicles. In this thesis, we propose a novel integrated approach that ensures motion safety and efficiency while planning and controlling an operation of swarms of autonomous robots. We validate our approach in different case studies and compare them with some state-of-the art benchmarks. Moreover, we rely on formal modelling to derive the safety constraints guaranteeing that the swarm system can cope with both predicted and dynamically emerging safety hazards. We define an architecture of the controlling software that combines static and dynamic mechanisms for safe and efficient swarm control and navigation. To ensure efficiency, while preserving safety, we propose a new parallel algorithm for swarm mission planning. This algorithm is a combination of evolutionary computing methods, machine learning and deterministic approaches that coordinated by a central management component. The algorithm controls the swarm actions on three different layers: the offline, online and vehicle layer as well as allows us to plan and optimise at the run-time the routes of the vehicles to maximise safety while minimising the travelling distance. Our solution promotes a holistic approach to designing CPS – from a formal requirements definition to a software implementation that fulfils the defined requirements in an efficient way. The results of benchmarking demonstrate that our approach allows safe and efficient control of swarms.

----------- Autonoma system ar typiska exempel på komplexa distribuerade cyber-fysiska system (CPS). De viktigaste användningsområdet av sådana system är autonoma fordon. Autonoma fordon används alltmer i olika uppdragskritiska uppgifter som övervaknings- och räddningsinsatser. För att utföra de uppgifter som krävs borde autonoma svärmsystem uppfylla viktiga pålitlighetskrav som säkerhet och tillförlitlighet. Samtidigt, när vi utformar ett svärmsystem, bör vi garantera att robotsystemen i svärmen inte kolliderar med varandra och föremål i driftsmiljön, dvs säkerställa rörelsesäkerhet. För att säkerställa att robotarna har tillräckliga resurser för att på ett tillförlitligt sätt fullgöra de nödvändiga målen, bör vi också vara effektiva när vi genomför svärmuppdraget, dvs. minimera robotfordonets färdavstånd. I denna avhandling föreslår vi ett nytt integrerat tillvägagångssätt som säkerställer manoveringssäkerhet och effektivitet samtidigt som man planerar och kontrollerar en operation av svärmar av autonoma robotar. Vi validerar vår strategi i olika fallstudier och jamför dem med några toppmoderna implementationer. Vi använder också formell modellering för att härleda säkerhetsbegränsningarna som garanterar att svärmsystemet klarar av både förutsagda och dynamiskt framkommande säkerhetsrisker. Vi definierar en arkitektur för den styrande programvaran som kombinerar statiska och dynamiska mekanismer för säker och effektiv svärmkontroll och navigering. För att säkerställa effektivitet, samtidigt som säkerheten bevaras, foreslår vi en ny parallell algoritm för planering av svärmuppdrag. Denna algoritm är en kombination av evolutionära datormetoder, maskininlärning och deterministiska tillvägagångssätt som samordnas av en central styrkomponent. Algoritmen kontrollerar svärmåtgärderna i tre olika lager: ett offline-, ett online- och ett fordonslager som låter oss planera och optimera fordonens rutter för att maximera säkerheten och samtidigt minimera körsträckan. Vår lösning främjar en helhetssyn på utformningen av CPS - från en formell kravdefinition till en programvaruimplementation som uppfyller de definierade kraven på ett effektivt sätt. Resultaten av benchmarkingen visar att vårt tillvägagångssätt möjliggör säker och effektiv kontroll av svärmar.