Efficient algorithms for mobile agents in networks

点击翻译按钮获取中文摘要

This proposal focuses on efficient algorithms for agents interacting and moving on networks. These agents could be autonomous mobile robots, self-driving cars, drones, swarms of simple robots, software agents, or people in a social network. Many networks are dynamic rather than static. For instance, in wireless networks formed by mobile nodes, such as IoT devices, buses, satellites, or autonomous mobile robots, links are created or broken because of the mobility of nodes. In road networks, traffic changes impact the travel time of roads which in turn changes the weights of the links. The dynamic nature of the network increases greatly the challenge of solving problems such as routing, exploration, and transportation.  The very large  scale  of networks created by IoT devices or mobile robots causes more challenges. We need  distributed algorithms, in which agents can  collaborate with each other to complete tasks. Any communication between the agents should ideally be  local. How best can the agents communicate and collaborate to perform tasks such as  search or  transportation? What is the impact of the capabilities of the agents, in terms of memory, communication abilities, energy storage, computational abilities, and faulty behaviour? Finally in some settings, the agents may not collaborate, but instead behave selfishly and strategically. In particular, consider a residential network of houses in a city, and agents of different types residing at the nodes. If these agents move strategically to new locations to suit their own preferences for types of neighbours, what conditions in terms of number of agents of different types or network topology can result in a stable situation or equilibrium? What conditions favour diverse neighbourhoods as stable outcomes? Are there techniques to increase the diversity in social networks? The long-term objective of my research is to improve our understanding of the interplay between network structure, the dynamic nature of networks, and distributed computing by mobile agents moving on networks. In the next granting period, I will focus on three specific problems that can help illuminate the more general principles. My short-term objectives are to design and analyze efficient centralized and distributed local algorithms for: - collaborative  exploration by autonomous mobile robots in static and dynamic networks. - routing and transportation in static and dynamic road and communication networks. - increasing diversity in social networks.