Efficient algorithms for mobile agents in networks

该建议的重点是有效的算法，代理互动和网络上移动。这些代理可以是自主的移动的机器人、自动驾驶的汽车、无人机、成群的简单机器人、软件代理或社交网络中的人。 许多网络是动态的，而不是静态的。例如，在由诸如IoT设备、总线、卫星或自主移动的机器人之类的移动的节点形成的无线网络中，由于节点的移动性而创建或断开链路。在道路网络中，交通量的变化会影响道路的行驶时间，从而改变链接的权重。网络的动态特性大大增加了解决路由、探索和运输等问题的挑战。 物联网设备或移动的机器人创建的超大规模网络带来了更多挑战。我们需要分布式算法，在这种算法中，智能体可以相互协作来完成任务。代理之间的任何通信都应该是本地的。智能体如何最好地进行通信和协作，以执行搜索或运输等任务？代理人的能力，在记忆、沟通能力、能量储存、计算能力和错误行为方面的影响是什么？最后，在某些情况下，代理可能不合作，而是自私和策略性的行为。特别是，考虑一个城市中的住宅网络，以及居住在节点上的不同类型的代理。如果这些代理移动到新的位置，以适应自己的喜好类型的邻居，什么样的条件下的代理的数量不同类型或网络拓扑结构可以导致一个稳定的情况或平衡？什么样的条件有利于多样化的社区作为稳定的结果？是否有技术可以增加社交网络的多样性？ 我的研究的长期目标是提高我们的网络结构，网络的动态性，和分布式计算之间的相互作用的理解移动的移动的代理在网络上移动。在下一个授予阶段，我将重点讨论三个具体问题，这些问题有助于阐明更普遍的原则。我的短期目标是设计和分析有效的集中式和分布式本地算法：-自主移动的机器人在静态和动态网络中的协作探索。- 静态和动态道路和通信网络中的路由和运输。- 社交网络的多样性日益增加。

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.