Algorithms for 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.