Adaptive communication networks for heterogeneous teams of robots

Abstract

Seemingly, the era of ubiquitous connectivity has arrived, with smart phones, tablets, and small computing devices bringing internet straight to our fingertips - or has it? Two thirds of the world still does not have access to the internet, and a lack of realistic communication guarantees for multi-agent robotic networks are standing in the way of taking these systems from research labs into the real world. In this thesis we consider the problem of satisfying communication demands in a multi-agent system where several robots cooperate on a task and a fixed subset of the agents act as mobile routers. Our goal is to position the team of robotic routers to provide communication coverage to the remaining client robots, while allowing clients maximum freedom to achieve their primary coordination task. We develop algorithms and performance guarantees for maintaining a desired communication quality over the entire heterogeneous team of controlled mobile routers and non-cooperative clients. In the first part of the thesis we consider the problem of router placement while explicitly accounting for client motion over a priori unknown trajectories. We formulate this problem as a novel optimization called the connected reachable k-connected center problem that extends the classical k-center problem. We propose an algorithm to compute a small representative set of clients where this set is of size (klog(n)/[epsilon])O (1), can be constructed in O(nk) time and updated in (klog(n)/[epsilon])O (1) time as clients move along their trajectories. Here k is the number of routers, n is the number of clients, and s is a user-defined acceptable error tolerance. Our router placement algorithm applied to this sparse set provides a configuration of router positions that is bounded by a multiplicative factor, (1 + [epsilon]) from optimal. Secondly, we incorporate a realistic communication model into our router placement optimization problem. We do this by developing a novel method of directional signal strength mapping that has sufficient richness of information to capture complex wireless phenomena such as fading and shadowing, and can be used to derive a simple optimization formulation that is based on quadratic link costs and is solved using our router placement algorithm. Using off-the-shelf hardware platforms we present aggregate results demonstrating that the resulting router placements satisfy communication demands across the network with 4X smaller standard deviation in performance and 3.4X faster convergence time than existing methods, and our solutions assume no environment map and unknown client positions. Finally, we derive distributed controllers for the special case where clients are static. We show that by the tuning of a control parameter our routers maintain a connected network using only local information. We support our theoretical claims with experimental results using AscTec hummingbird platforms as well as iRobot Create platforms of small 10 client and large 500 virtual client implementations.