Optimization Problems in Communication Networks and Multi-Agent Path Finding

Abstract

This dissertation is a compilation of six research papers that are focused on three dif- ferent topics summarized in the text. The first three papers address NP-hard problems arising in ad-hoc wireless com- munication discussed in Chapter 2. In general, the task is to broadcast a message in a given network of wireless devices while minimizing the power consumption. Problems in this category differ in requirements on the network connectivity, models of power consumption, and the ability of the devices to initiate a signal transmission. Some of the common features of these problems are that a device can simultaneously transmit a signal to all devices within its communication vicinity, and that a signal can travel from its originator to its recipient via multiple intermediate devices. The wireless networks are modeled and studied by means of graph theory. Solution techniques for these prob- lems involve mainly methods of integer linear programming and inexact algorithms with or without performance guarantee. The next paper is focused on the problem of minimum broadcast time. Unlike the previous topic, the devices are in this problem supposed to send a signal to at most one neighbouring device at a time. The objective is to determine a sequence of signal trans- mission from a given set of source devices to the remaining ones, while minimizing the time needed for spreading the signal. Chapter 3 describes this problem in detail along with several related problems. The minimum broadcast time problem is also studied from the perspective of integer linear programming as well as the inexact algorithm perspective. Continuous relaxations of the ILP models help to evaluate the quality of the studied inexact methods. The stronger the model is, the more accurate assessment it provides. The last two papers are dedicated to problems belonging to path planning for mul- tiple robots discussed in Chapter 4. In general, these problems involve a group of agents (robots) initially deployed in an environment. The task is to find a sequence of their moves so that they reach pre-defined destination locations while optimizing a given criterion such as minimum makespan or minimum total arrival time. The agents’ movement must obey a set of given rules. An extension of the problem considers agents divided into two (or more) adversarial teams, where the teams have either symmetric or asymmetric objectives. After introducing the adversarial element, the problem of find- ing a winning strategy for a given team becomes PSPACE-hard, like many other two player games with alternating turns.