Algorithms for Mobile Agents

移动代理算法

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

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