Communication-Aware Coordination of Multi-Agent Systems under Spatio-Temporal Constraints

QC 20251009

Abstract

Under det senaste decenniet har den snabba tillväxten av beräkningskraft i inbyggda system drivit på ett växande intresse för autonoma system med realtidsplanering och styrförmåga, avsedda att uppfylla rumsligt och tidsmässigt definierade mål. Många sådana system har redan blivit en del av vardagen—till exempel robotdammsugare, drönarleveranser och självkörande taxibilar. I detta sammanhang har regler- och robotikforskarsamhällena lagt ned betydande ansträngningar på att utveckla formella ramverk som gör det möjligt att specificera mål på ett stringent sätt och att verifiera systemens framsteg mot att uppfylla dessa. Mer specifikt, när det gäller system bestående av, möjligen heterogena, autonoma agenter, är utvecklingen av skalbara och tillförlitliga koordineringsalgoritmer som kan driva agenterna mot gemensamma mål, samtidigt som de verkar under begränsade kommunikationsmöjligheter, av avgörande betydelse.

Arbetet som presenteras i denna avhandling befinner sig i skärningspunkten mellan koordination av multiagentsystem och formell verifiering. Det övergripande målet är att utveckla uppdragsallokerings-, planerings- och styralgoritmer för att koordinera multiagentsystem under glesa kommunikationstopologier, med syftet att uppfylla systemövergripande spatio-temporala mål. För detta ändamål använder vi Signal Temporal Logic (STL) som det primära modelleringsramverket, vilket ger ett precist och entydigt språk för att specificera systemnivåns mål. Parallellt utnyttjar vi ramverket Control Barrier Functions (CBFs) för att överbrygga gapet mellan hög nivå-specifikationer och låg nivå-styrmål, vilka sedan kan angripas med hjälp av verktyg från icke-linjär och icke-slät analys.

Med denna grund introducerar den första delen av avhandlingen ett nytt ramverk för att representera uppgiftsberoenden mellan agenter genom en uppgiftsgraf, där kanterna beskriver samarbetsuppgifter mellan agenter. Baserat på denna representation utformar vi algoritmer som gör det möjligt att bryta ned eller omdirigera uppgiftsberoenden mellan agenter som saknar direkt kommunikation, via agenter som delar kommunikationslänkar. Denna nedbrytning utgör en central möjliggörare för återkopplingsbaserade styrmetoder som kan uppfylla systemövergripande mål på ett skalbart och reaktivt sätt, genom att säkerställa överensstämmelse mellan givna uppgifter och de kommunikationsberoenden som nätverkets topologi medför.

Den andra delen av avhandlingen presenterar en styrarkitektur för att driva ett multiagentsystem mot uppfyllelsen av ett systemövergripande mål, under antagandet att den associerade uppgiftsgrafen är acyklisk. Det föreslagna reglersystemet implementeras i sampled-data-form, vilket är typiskt för inbyggda system, samtidigt som vi tillhandahåller analytiska resultat som garanterar måluppfyllelse i kontinuerlig tid. Detta dubbla perspektiv överbrygger gapet mellan den digitala naturen hos inbyggd styrning och den kontinuerliga tidens dynamik i det fysiska systemet.

Den tredje och sista delen av avhandlingen avviker något från innehållet i de två första genom att fokusera på trajektoriesyntes. Mer specifikt utvecklar vi en sampling-baserad planeringsalgoritm för att generera banor som uppfyller spatio-temporala mål för system med linjär dynamik. Vi kommer vidare att behandla utvidgningen av det föreslagna ramverket till multiagentinställningar som framtida forskning.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-371346