Ph.D. (Engg) : Multi-Agent Coordination using Convex Formations and Binary Tree Structures

Multi-agent systems are increasingly deployed in missions involving large-scale tasks with complex objectives that are beyond the capability of a single agent. Such missions demand computationally efficient coordination strategies that ensure safety, reliable operation, and ease of implementation, particularly in dynamic and uncertain environments. This thesis investigates coordination strategies in multi-agent systems, specifically addressing the problems of distribution of agents on an enclosing boundary, cooperative target capture and containment, and traversal through constrained spaces.

The first part of the thesis presents a convex layer-based strategy that assigns collision-free paths to a swarm of point-sized agents to reach an enclosing circular boundary. Leveraging the construction of convex layers from the initial positions of agents, a novel search space for an agent on a convex layer is defined as an angular region enclosed between the lines passing through the agent’s position and normal to its supporting edges. A goal assignment policy is proposed, which designates a unique goal position on the boundary within the search space of an agent. Subsequently, the proposed framework is extended to polygonal boundaries, considering disc-shaped agents. Therein, the proposed policy assigns a goal position to each agent in order of decreasing overlap between their search spaces and the polygonal boundary, while excluding angular regions corresponding to already assigned goal positions. Further, a layer-wise speed assignment rule is proposed, which ensures collision-free trajectories for the agents. Simulation studies assess the proposed method under various real-world considerations, including the finite size of the agents, a six-degree-of-freedom quadrotor model, uncertainties in initial position information, and communication delays.

In the second part, the problem of multiple pursuers engaging a single evader is considered in two complementary scenarios. Firstly, the problem of capturing the evader in an unbounded region is addressed. As the key construct, the evader’s proximity region is characterized by the region generated by the Voronoi diagram constructed using the positions of the pursuers and the evader. Pursuers’ velocity inputs are deduced as a function of the position and velocity of the vertices of the evader’s proximity region and the evader. A motion policy is proposed that directs the vertices of the evader’s proximity region toward its centroid, under which the region is analytically shown to shrink exponentially over time, irrespective of the evader’s motion policy. In addition, using the Chebyshev radius of the proximity region, an upper bound on the time of evader capture is derived. Simulation studies demonstrate the effectiveness of the proposed method under various evader maneuvers and in scenarios where evader position information is noisy. In a scenario complementary to evader capture, a containment problem is considered, wherein multiple pursuers are desired to encapsulate a moving evader. Considering the engagement between the evader and the centroid of the convex hull of pursuers, a variable deviated pursuit guidance law is proposed, which achieves a tail-chase rendezvous between the evader and the centroid. Subsequently, a cooperative control strategy is presented, which drives the convex hull of pursuers to confine the evader through a prescribed edge while preserving the formation rigidity. Simulation results demonstrate the efficacy of the proposed method under various evader maneuvers.

The final part of the thesis addresses the problem of sequential traversal of multiple UAVs through a narrow gap. A hierarchical binary tree is constructed with its nodes defined by the UAVs’ initial positions and the gap entry point, presenting a routing framework that provides an ordered sequence of waypoints to each UAV. A cost function is formulated that accounts for the UAV path lengths and the angles between branches at the tree nodes, and a binary tree is constructed by minimizing that cost using a genetic algorithm coupled with a greedy strategy. In conjunction, a decentralized scheduling policy is proposed, in which each UAV is assigned conflict-free time slots at nodes that are identified with potential collisions. Simulation scenarios illustrate the effectiveness of the proposed method, and Monte Carlo studies assess its scalability.

Overall, the thesis presents deterministic and computationally efficient multi-agent coordination strategies by leveraging ideas from convex geometry and binary trees. Experimental flight trials on a nano-quadrotor platform are also conducted, further demonstrating the practicality of the proposed coordination methods.