Optimization Problems in Communication Networks and Multi-Agent Path Finding
MetadataShow full item record
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.
Has partsPaper I: Ivanova, M., Shared Multicast Trees in Ad Hoc Wireless Networks. In: Cerulli R., Fujishige S., Mahjoub A. (eds) Combinatorial Optimization. ISCO 2016. Lecture Notes in Computer Science, vol 9849. The article is available in the main thesis. The article is also available at: https://doi.org/10.1007/978-3-319-45587-7_24
Paper II: Ivanova, M., The Shared Broadcast Tree Problem and MST. Electronic Notes in Discrete Mathematics, 2016; 55: 5-8. The article is available in the main thesis. The article is also available at: https://doi.org/10.1016/j.endm.2016.10.002
Paper III: Ivanova, M., Haugland, D., Integer Programming Formulations for the Shared Multicast Tree Problem. Journal of Combinatorial Optimization, 2019; 38(3): 927–956. The article is not available in BORA due to publisher restrictions. The published version is available at: https://doi.org/10.1007/s10878-019-00428-8
Paper IV: Ivanova, M., Haugland, D., Computing the Broadcast Time of a Graph. The article is not available in BORA.
Paper V: Ivanova, M., Surynek, P., Hirayama, K., Area Protection in Adversarial Path-finding Scenarios with Multiple Mobile Agents on Graphs. In: Proceedings of the 10th International Conference on Agents and Artificial Intelligence (ICAART 2018), pp. 184-191, Funchal, Madeira, Portugal, SciTe Press, 2018, ISBN 978-989-758-275-2. The article is available in the main thesis. The article is also available at: https://doi.org/10.5220/0006583601840191
Paper VI: Ivanova, M., Surynek, P., Nguyen, D.T.N., Maintaining Ad-Hoc Communication Network in Area Protection Scenarios with Adversarial Agents. In: Proceedings of the 31st International Florida Artificial Intelligence Research Society Conference (FLAIRS 2018), pp. 348-353, Melbourne, FL, USA, AAAI Press, 2018. The article is available in the main thesis. The article is also available at: https://www.aaai.org/ocs/index.php/FLAIRS/FLAIRS18/paper/view/17659