ETD

• Behavior Trees
• cooperation
• distributed control
• multi-agent

This thesis presents the development, implementation, and validation of a distributed control architecture designed to support the cooperation and coordination of multi-agent teams. The proposed framework addresses the main challenges associated with decentralized task execution, including high-level planning, distributed deliberation, intention sharing, conflict resolution, action parallelization, and the integration between symbolic decision-making and low-level control.

The architecture is organized into a set of interconnected functional blocks, each responsible for a specific stage of the control process. The planning module generates a high-level control policy for each agent according to the shared goal, the capabilities available within the team, and the logical representation of the problem. The resulting policies are implemented through Behavior Trees, which provide a modular, reactive, and interpretable structure for representing alternative action sequences and coordinating the execution of complex tasks.

The planning procedure is based on a backward-chaining expansion mechanism that distributes the task among the agents according to their available capabilities. In addition to the complete planning algorithm, which generates the control policies from an initial set of empty trees, partial replanning procedures are introduced to efficiently manage changes in the team configuration or in the set of available capabilities. These procedures make it possible to update only the affected portions of the Behavior Trees without repeating the entire planning process.

During task execution, the deliberation module periodically evaluates the Behavior Tree associated with each agent and generates a proposal corresponding to the action that the agent intends to execute. A priority-assignment mechanism then associates a priority value with each proposal. Different strategies are considered, including static agent priorities, aging-based mechanisms, failure-probability-based criteria, and custom state-dependent priority functions.

The proposals are exchanged through a distributed communication mechanism that allows every agent to acquire a consistent representation of the intentions of the other members of the team. Based on this shared proposal set, a priority-based filtering procedure selects the actions that can be executed. The selection process resolves conflicts caused by the use of exclusive resources, mutually disruptive action effects, or the invalidation of action preconditions. At the same time, compatible proposals are preserved, allowing multiple agents to operate in parallel and improving the overall efficiency of the team.

The selected proposals are then converted into executable subtasks and transmitted to the low-level controllers. These controllers compute the physical control inputs required to perform the selected capabilities. At the beginning of each deliberation cycle, the physical state of the robots and the environment is mapped into a logical state, which is subsequently used to update the high-level policies and generate new proposals.

The proposed planning and control framework is supported by a theoretical analysis of its main properties. In particular, the thesis investigates the termination of the planning procedure, the finite-time success of the generated Behavior Trees, the finite-time achievement of the shared goal from the corresponding regions of attraction, and the goal-consistency properties of the team under the considered execution assumptions.

The architecture is validated through four representative multi-agent scenarios and two complementary experimental environments. A logical simulation environment is used to evaluate the complete and partial planning algorithms and to measure the ideal performance of the high-level control structure. A physics-based simulation environment reproduces the complete control pipeline, including deliberation, communication, coordination, state abstraction, low-level actuation, and robot-environment interaction. The experimental analysis considers planning time, tree size, execution success rate, task completion time, parallel execution time, and agent utilization, demonstrating the applicability of the proposed framework to heterogeneous multi-agent cooperation tasks.

Questa tesi presenta lo sviluppo, l’implementazione e la validazione di un’architettura di controllo distribuita progettata per supportare la cooperazione e il coordinamento di squadre multi-agente. Il framework proposto affronta le principali problematiche associate all’esecuzione decentralizzata dei task, tra cui la pianificazione di alto livello, la deliberazione distribuita, la condivisione delle intenzioni, la risoluzione dei conflitti, la parallelizzazione delle azioni e l’integrazione tra il processo decisionale simbolico e il controllo di basso livello.

L’architettura è organizzata in un insieme di blocchi funzionali interconnessi, ciascuno responsabile di una specifica fase del processo di controllo. Il modulo di pianificazione genera una politica di controllo di alto livello per ciascun agente sulla base dell’obiettivo condiviso, delle capacità disponibili all’interno della squadra e della rappresentazione logica del problema. Le politiche risultanti sono implementate mediante Behavior Trees, che forniscono una struttura modulare, reattiva e interpretabile per rappresentare sequenze alternative di azioni e coordinare l’esecuzione di task complessi.

La procedura di pianificazione si basa su un meccanismo di espansione backward-chaining che distribuisce il task tra gli agenti in funzione delle capacità da essi possedute. Oltre all’algoritmo di pianificazione completa, che genera le politiche di controllo a partire da un insieme iniziale di alberi vuoti, vengono introdotte procedure di ripianificazione parziale per gestire in modo efficiente variazioni nella configurazione della squadra o nell’insieme delle capacità disponibili. Tali procedure consentono di aggiornare esclusivamente le porzioni dei Behavior Trees interessate dalle modifiche, evitando di ripetere l’intero processo di pianificazione.

Durante l’esecuzione del task, il modulo di deliberazione valuta periodicamente il Behavior Tree associato a ciascun agente e genera una proposta corrispondente all’azione che l’agente intende eseguire. Un meccanismo di assegnazione delle priorità associa quindi un valore di priorità a ciascuna proposta. Vengono considerate diverse strategie, tra cui priorità statiche associate agli agenti, meccanismi basati sull’aging, criteri dipendenti dalla probabilità di fallimento e funzioni di priorità personalizzate e dipendenti dallo stato.

Le proposte vengono scambiate attraverso un meccanismo di comunicazione distribuito che consente a ciascun agente di ottenere una rappresentazione coerente delle intenzioni degli altri membri della squadra. Sulla base dell’insieme condiviso di proposte, una procedura di filtraggio basata sulle priorità seleziona le azioni che possono essere eseguite. Il processo di selezione risolve i conflitti causati dall’utilizzo di risorse esclusive, da effetti di azioni mutuamente distruttivi o dall’invalidazione delle precondizioni di altre azioni. Allo stesso tempo, le proposte compatibili vengono preservate, consentendo a più agenti di operare in parallelo e migliorando l’efficienza complessiva della squadra.

Le proposte selezionate vengono successivamente convertite in sotto-task eseguibili e trasmesse ai controllori di basso livello. Questi ultimi calcolano gli ingressi di controllo fisici necessari all’esecuzione delle capacità selezionate. All’inizio di ogni ciclo di deliberazione, lo stato fisico dei robot e dell’ambiente viene trasformato in uno stato logico, utilizzato successivamente per aggiornare le politiche di alto livello e generare nuove proposte.

Il framework di pianificazione e controllo proposto è supportato da un’analisi teorica delle sue principali proprietà. In particolare, la tesi analizza la terminazione della procedura di pianificazione, il successo in tempo finito dei Behavior Trees generati, il raggiungimento in tempo finito dell’obiettivo condiviso a partire dalle corrispondenti regioni di attrazione e le proprietà di consistenza rispetto all’obiettivo della squadra sotto le ipotesi di esecuzione considerate.

L’architettura viene validata attraverso quattro scenari multi-agente rappresentativi e due ambienti sperimentali complementari. Un ambiente di simulazione logica viene utilizzato per valutare gli algoritmi di pianificazione completa e parziale e per misurare le prestazioni ideali della struttura di controllo di alto livello. Un ambiente di simulazione fisica riproduce invece l’intera catena di controllo, includendo deliberazione, comunicazione, coordinamento, astrazione dello stato, attuazione di basso livello e interazione tra robot e ambiente. L’analisi sperimentale considera il tempo di pianificazione, la dimensione degli alberi, il tasso di successo dell’esecuzione, il tempo di completamento del task, il tempo di esecuzione parallela e il grado di utilizzo degli agenti, dimostrando l’applicabilità del framework proposto a task cooperativi svolti da squadre multi-agente eterogenee.