Algorithms for Mobile Agents

移动代理算法

• 批准号: RGPIN-2016-06455
• 负责人: Czyzowicz, Jurek
• 金额: $ 1.89万
• 依托单位: Québec en Outaouais
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=648482
• 关键词: Algorithms; Mobile; Agents

Mobile agents are devices that typically possess the following capabilities:***• mobility within the environment;***• a sensing instrument that can perceive various features of the environment ;***• a computing device with storage capacity;***• a communication mechanism that can exchange information with other agents.***Typically, mobile agents are tasked with traversing the environment in order to learn it, map it and/or search for a specific target. In distributed computing, one of the fundamental problems concerns rendezvous or a gathering of agents dispersed across the environment (or some other pattern formation). ***Applications using mobile agents are numerous. Physical robots or humans (e.g., soldiers or rescue personnel) often perform searches in hazardous environments. Software agents migrate over a network to perform remote data collection (e.g. indexing web pages or looking for network faults). Further applications come from other domains such as wireless and ad-hoc networks, operations research, game theory, scheduling, nanotechnology, distributed spatial control, social networks etc.Most research on searching and exploration concerns a single agent. However, in various domains, the task must be performed by a set of collaborating agents. It may then prove challenging to partition the task(s) appropriately among the agents in order to ensure an adequate synchronization of their actions. For tasks requiring a large number of agents, the agents need to be produced at low cost. On the other hand, since such agents are often assigned to specific tasks, not all of their capabilities may be required. This gives rise to an important feasibility question: What is the minimum set of agent capabilities that is required to successfully complete a given task?***The main objectives of my project include the study and resolution of the feasibility question for fundamental tasks assigned to mobile agents. If feasibility is determined to be no longer an issue, I will then investigate these related optimization problems: ****• What is the minimum number of mobile agents needed to accomplish the assigned task? ***• What is the minimum time needed by a team of agents? ***• What is the minimum energy (battery power) needed by each agent to successfully accomplish an assigned task? ***• What is the minimum amount of memory needed by each agent? ***• Can tasks be accomplished when communication between the agents becomes restricted?***• What is the maximum number of rogue agents of the given collection that may become disabled or destroyed, so that the remaining agents are still capable of successfully accomplishing a given task?***In some cases, the agents may have no control over their movement. It is entirely determined by their interaction with the environment and can be substantiated by the laws of physics or probability. Some of my feasibility and optimization questions will be addressed for such collections of passively mobile agents.********

移动的代理是通常具有以下能力的设备：***·在环境中的移动性;***·可以感知环境的各种特征的传感仪器;***·具有存储能力的计算设备;***·可以与其他代理交换信息的通信机制。通常，移动的代理的任务是遍历环境，以便学习它，映射它和/或搜索特定的目标。在分布式计算中，一个基本问题是关于分散在环境中的代理的集合或聚集（或其他模式形成）。* 使用移动的代理的应用程序很多。物理机器人或人类（例如，士兵或救援人员）经常在危险环境中执行搜索。软件代理通过网络迁移以执行远程数据收集（例如，索引网页或查找网络故障）。进一步的应用来自其他领域，如无线和ad-hoc网络，运筹学，博弈论，调度，纳米技术，分布式空间控制，社交网络等。大多数搜索和探索的研究涉及一个单一的代理。然而，在不同的域中，任务必须由一组协作代理来执行。然后可能证明在代理之间适当地划分任务以确保它们的动作的充分同步是具有挑战性的。对于需要大量试剂的任务，试剂需要以低成本生产。另一方面，由于这些代理通常被分配给特定任务，因此可能不需要它们的所有功能。这就产生了一个重要的可行性问题：成功完成给定任务所需的代理功能的最小集合是什么？*我的项目的主要目标包括研究和解决分配给移动的代理的基本任务的可行性问题。如果确定可行性不再是一个问题，那么我将研究这些相关的优化问题：*·完成指定任务所需的移动的代理的最小数量是多少？* * *·每个座席成功完成指定任务所需的最低能量（电池电量）是多少？* 每个代理需要的最小内存量是多少？*·当代理之间的通信受到限制时，是否可以完成任务？*·给定集合中可能被禁用或销毁的流氓代理的最大数量是多少，以便剩余的代理仍然能够成功完成给定任务？*在某些情况下，代理可能无法控制其移动。这完全取决于它们与环境的相互作用，并可以由物理定律或概率来证实。我的一些可行性和优化问题将针对被动移动的代理的这种集合来解决。**