Preface

This year, the workshop consisted of five contributed talks. Three were full papers and two were talks about results that have been published elsewhere or not yet completed.

In addition to the five contributed talks, the workshop featured two invited talks. The first was given by Fabian Kuhn from the University of Freiburg and was titled "Dealing with Uncertainty in Wireless Communication". The second was given by Gal Kaminka from Bar-Ilan University and was titled "Reusable Teamwork for Multi-Robot Teams".

October 2013

Keren Censor-Hillel Valerie King

Dealing with Uncertainty in Wireless Communication

Over the last 25 years, a variety of abstract models to deal with the characteristic properties of wireless communication have been proposed and many algorithms for wireless networks have been developed. The models range from simple graph-based characterizations of interference to more accurate so-called signal-to-noise-and-interference (SINR) models. As different as the considered models may be, most of them have one thing in common. Whether a node can successfully receive (and decode) a message is determined using some fixed, deterministic rule that depends on the structure of the network and some additional model parameters. Often correctness and performance guarantees of algorithms critically depend on such rigid rules and sometimes even on the fact that each node exactly knows certain model parameters or some other information about the network. In my talk, I will argue that such assumptions can be problematic and I will discuss some existing results and future directions to deal with inherent uncertainties in systems based on wireless communication.

Reusable Teamwork for Multi-Robot Teams

For many years, multi-robot researchers have focused on specific application-inspired basic tasks (e.g., coverage, moving in formation, foraging, patrolling) as a way of studying cooperation between robots. But users want to see increasingly complex missions being tackled, which challenge this methodology: first, some missions cannot be easily decomposed into the familiar basic tasks, making previous knowledge non-reusable; second, the target operating environments challenge the typically sterile settings assumed in many previous works (such challenges include adversaries, multiple concurrent goals, human operators and users, and more).

In this talk, I will argue that the reusable components in complex missions are often found not in the tasks, but in the interactions between robots, i.e., that while taskwork varies significantly, teamwork is largely generic. And while many multi-robot researchers have begun exploring generic task-allocation methods, I will report on my group's work over the last decade, identifying and developing other general mechanisms for teamwork, and integrating them at the architecture level to facilitate development of robust teams at reduced programming effort. I will sample some of our results in developing robots for missions ranging from robust formation maintenance, through patrolling, to soccer and urban search-and-rescue.

Relative Throughput - Measuring the Impact of Adversarial Errors on Packet Scheduling Strategies

In this talk we will explore the problem of achieving efficient packet transmission over unreliable wireless links with worst case occurrence of errors. In such a setup, even an omniscient offline scheduling strategy cannot achieve stability of the packet queue, nor is it able to use up all the available bandwidth. Hence, an important first step is to identify an appropriate metric for measuring the efficiency of scheduling strategies in such a setting. To this end, we propose a relative throughput metric which corresponds to the long term competitive ratio of the algorithm with respect to the optimal. Then, we will explore the impact of the error detection mechanism and feedback delay on our measure. We will compare instantaneous error feedback with deferred error feedback, that requires a faulty packet to be fully received in order to detect the error. We will also propose algorithms for worst-case adversarial and stochastic packet arrival models, and formally analyze their performance. The relative throughput achieved by these algorithms is then shown to be close to optimal by deriving lower bounds on the relative throughput of the algorithms and almost matching upper bounds for any algorithm in the considered settings. Our collection of results demonstrate the potential of using instantaneous feedback to improve the performance of wireless communication systems in adverse environments.

Jamming-Resistant Learning in Wireless Networks

We consider capacity maximization in wireless networks under adversarial interference conditions. There are $n$ links, each consisting of a sender and a receiver, which repeatedly try to perform a successful transmission. In each time step, the success of attempted transmissions depends on interference conditions, which are captured by an interference model (e.g. the SINR model). Additionally, an adversarial jammer can render a $(1-\delta)$-fraction of time steps unsuccessful. For this scenario, we analyze a framework for distributed learning algorithms to maximize the number of successful transmissions. Our main result is an algorithm based on no-regret learning converging to an $O\left(1/\delta\right)$-approximation. It provides even a constant-factor approximation when the jammer exactly blocks a $(1-\delta)$-fraction of time steps. In addition, we consider a stochastic jammer, for which we obtain a constant-factor approximation after a polynomial number of time steps. We also consider more general settings, in which links arrive and depart dynamically. Our algorithms perform favorably in simulations.

A full version of the paper can be found online at http://arxiv.org/abs/1307.5290.