Providing Guaranteed Behaviors for Groups of Low-Capability Mobile Agents

I consider the problem of designing algorithms for coordinated groups of low-capability, error-prone mobile agents. It is my thesis that some important collective behaviors of groups of low-capability mobile agents can be guaranteed by the application of provably-correct distributed algorithms. This thesis is demonstrated by the provision of new algorithms that guarantee mobile agent behavioral properties in the face of noise and agent error, as well as proofs that characterize the requirements of particular tasks.

The contributions of this dissertation include both algorithms for solving classes of tasks that are foundational to processes involving groups of mobile agents and proofs regarding the impact limited capabilities have on the ability of agents to perform various tasks.

The capability proofs lie in two principle areas. The first set of proofs relate to the differences between stigmergic and broadcast communication; these proofs bound the time and number of additional agents required to emulate broadcast communication using stigmergy. The second set of proofs bound the capabilities needed to ensure that agents are able to locate one another in an unknown environment. In addition to these stand-alone proofs, there are also proofs accompanying each algorithm presented.

The main classes of tasks solved relate to agents forming and maintaining a group. A family of algorithms is provided, each of which guarantees rendezvous in bounded time for some class of agent capabilities. For agents with bounded-error knowledge of time and place these rendezvous algorithms are within a logarithmic term of being asymptotically optimal. A technique is presented for generating pair-wise cohesion constraints for various agent types; these constraints provide each agent with a set of allowable behaviors that provably keep the agents connected. A set of related communication protocols achieve global cohesion using an underlying pair-wise cohesion algorithm, allowing swarms of agents to move cohesively without being constrained by connection topology. Finally, a set of protocols is presented for having agents form into groups even when the agents do not trust one another.

Taken together, the algorithms and proofs in this dissertation contribute to the understanding of how agent capability and behavior are related, significantly improve the scope of problems that can be solved via provable algorithms, and improve several existing time bounds.