Efficient algorithms for mobile agents in networks

网络中移动代理的高效算法

• 批准号: RGPIN-2022-04919
• 负责人: Narayanan, Lata
• 金额: $ 2.99万
• 依托单位: Concordia University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750117
• 关键词: Efficient; algorithms; mobile; agents; 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.

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