Search

Computation offloading technology in an FEC (Fog/Edge Computing) environment requires the process of transmitting code/data and execution results from a mobile device (MD) to an edge server (ES). In this case, a mobile agent may be used for efficient transmission of code/data. However, the mobile agent migrates with task processing commands and execution results at the time of migration, which can cause time delays and reliability degradation problems due to increased size. This paper proposes a method of securing the applicability and reliability of the mobile agent system by implementing migration algorithm and a method of reducing the weight of the mobile agent for computation offloading. In addition, we demonstrate the legitimacy of the proposed method based on the results of the migration and mounting module execution experiment of the mobile agent equipped with code/data in the FEC environment and the comparative analysis experiment of the migration time according to the size of the mobile agent. [ABSTRACT FROM AUTHOR]

Abstract This paper studies the well-known problem of gathering multiple mobile agents moving in a graph, but unlike previous results, we consider the problem in the presence of an adversarial mobile entity which we call the malicious agent. The malicious entity can occupy any empty node and prevent honest mobile agents from entering this node. This new adversarial model is interesting as it models transient mobile faults that can appear anywhere in a network. Moreover, our model lies between the less powerful delay-fault model , where the adversary can block an agent for only a finite time, and the more powerful but static fault model of black holes that can even destroy the agents. We study the problem for ring networks and we provide a complete characterization of the solvability of gathering, depending on the size n of the ring and the number of agents k. We consider both oriented or unoriented rings with either synchronous or asynchronous agents. We prove that in an unoriented ring network with asynchronous agents the problem is not solvable when k is even, while for synchronous agents the problem is unsolvable when both n is odd and k is even. We then present algorithms that solve gathering for all the remaining cases, thus completely solving the problem. Finally, we provide a proof-of-concept implementation of the synchronous algorithms using programmable Lego Mindstorms EV3 robots. [ABSTRACT FROM AUTHOR]

This paper considers the distributed control problem of nonholonomic mobile agents with input delay to track a target. In contrast to the existing works in which some controllers have been designed for ideal conditions, the destructive factor of input delay is considered in the dynamics of the agents in this work. At first, a distributed controller is suggested for each agent to track the target in the absence of input delay. In this case, each nonholonomic mobile agent is divided into two subsystems and two terminal sliding mode controllers are designed for the two subsystems. Based on the proposed controllers, a switching control strategy is obtained to guarantee the finite time tracking control of nonholonomic mobile agents. Then, this controller is extended based on a future state estimator for tracking control in the presence of input delay. The stability analysis of distributed controllers and estimator is also provided. Simulation results illustrate the effectiveness of the suggested algorithms. [ABSTRACT FROM AUTHOR]

Abstract A pair of agents (robots) are moving in a graph with the goal of meeting at the same node or while traversing the same edge. An asynchronous adversary knows the prescribed walks of the two agents and is in complete control of the speed of each agent during its walk. We provide a complete characterization of pairs of walks that enforce rendezvous against an asynchronous adversary after traversing a given number of edges. The characterization is efficient in that it can be checked in polynomial time. We argue that the certificate of rendezvous enforcement that is produced by the checking algorithm contains a wealth of information on why rendezvous is enforced. [ABSTRACT FROM AUTHOR]

Mobile Agent systems are prevalent in Distributed Environment due to the autonomy and adaptability in diversified situations. Mobile Agents are capable of movement from one platform to another and hence it is a need to ensure the safety of the Mobile Agent during the phase of transit. Since Mobile Agents are capable of deciding their itinerary dynamically, a decision support system which helps to ensure the trustworthiness of a platform would complement the decision. A Trust Scoring System is therefore proposed to measure the trustworthiness of a platform based on a metric termed Trust Score. Trust Score varies dynamically with respect to time and is based on a function comprising of five parameters namely Persistence, Competence, Reputation, Credibility and Integrity. In order to reduce the computational latency, another metric named Trust Rank for platforms, based on Trustability co-efficient of variation is introduced. The experimentation is done in cloud environment with platforms located at different geographic regions. The performance is evaluated in terms of response time and accuracy of decision. From the experimental results, it is evident that the Trust Ranking mechanism consumes less response time and improves the accuracy of decision of Mobile Agents during their itineraries, compared to that of the prototype system that uses Trust Score alone as a measure of decision-making. [ABSTRACT FROM AUTHOR]

Two mobile agents, starting at arbitrary, possibly different times from arbitrary locations in the plane, have to meet. Agents are modeled as discs of diameter 1, and meeting occurs when these discs touch. Agents have different labels which are positive integers. Each agent knows its own label, but not the label of the other agent. Agents are equipped with compasses and have synchronized clocks. They make a series of moves. Each move specifies the direction and the duration of moving. This includes a null move which consists in staying inert for some time, or forever. In a non-null move agents travel at the same constant speed, normalized to 1. We assume that agents have sensors enabling them to estimate the distance from the other agent (defined as the distance between centers of discs), but not the direction towards it. We consider two models of estimation. In both models an agent reads its sensor at the moment of its appearance in the plane and then at the end of each move. This reading (together with the previous ones) determines the decision concerning the next move. In both models the reading of the sensor tells the agent if the other agent is already present. Moreover, in the monotone model, each agent can find out, for any two readings in moments t1 and t2, whether the distance from the other agent at time t1 was smaller, equal or larger than at time t2. In the weaker binary model, each agent can find out, at any reading, whether it is at distance less than ρ or at distance at least ρ from the other agent, for some real ρ > 1 unknown to them. Such distance estimation mechanism can be implemented, e.g., using chemical sensors. Each agent emits some chemical substance (scent), and the sensor of the other agent detects it, i.e., sniffs. The intensity of the scent decreases with the distance. In the monotone model it is assumed that the sensor is ideally accurate and can measure any change of intensity. In the binary model it is only assumed that the sensor can detect the scent below some distance (without being able to measure intensity) above which the scent is too weak to be detected. We show the impact of the two ways of sensing on the cost of meeting, defined as the total distance travelled by both agents until the meeting. For the monotone model we show an algorithm achieving meeting at cost O(D), where D is the initial distance between the agents. This complexity is optimal. For the binary model we show that, if agents start at distance smaller than ρ (i.e., when they sense each other initially) then meeting can be guaranteed at cost O(ρ log λ), where λ is the larger label, and that this cost cannot be improved in general. Finally we observe that, if agents start at distance αρ, for some constant α > 1 in the binary model, then sniffing does not help, i.e., the worst-case optimal meeting cost is of the same order of magnitude as without any sniffing ability. [ABSTRACT FROM AUTHOR]

Probabilistic time geography considers the encounter of moving agents to be random; therefore, a quantitative time geography analysis must consider the actual encounter probability. The existing algorithm of encounter probability is oriented over a discrete space and is sensitive to the unit definition of a virtual grid; thus, it is not suitable for continuous space. For this reason, a new method is presented in this paper for the encounter of two moving agents in continuous space. When the encounters are less than a specified distance threshold apart, an encounter event occurs based on the probability of the product, which is calculated by their respective probability density functions over their respective potential location areas. This probability provides a quantitative basis for predicting the likelihood of two agents meeting, as well as the location of this meeting point. Finally, the validity of the proposed model is verified by an experiment, which uses tracking data to calculate the encounter probabilities of three zebras and analyse the distribution characteristics of these probabilities over time and space. [ABSTRACT FROM AUTHOR]

Multi-agent applications that include teams of mobile sensing agents are challenging since they are inherently dynamic and a single movement of a mobile sensor can change the problem that the entire team is facing. A variation of the Distributed Constraint Optimization model for Mobile Sensor Teams (DCOP_MST) was previously adjusted to represent such problems along with local search algorithms that were enhanced with exploration methods. This paper considers the use of the Max-sum algorithm for solving problems of deploying a mobile sensor team in an unknown environment to track and monitor points of interest (targets), represented by the DCOP_MST model. The DCOP_MST model allows the representation of different functions for aggregating the joint coverage of targets by multiple sensors. The use of different functions has a dramatic effect on the complexity of the Max-sum algorithm. When using cardinality functions, Max-sum can be performed efficiently regardless of the arity of constraints. When Max-sum is used to solve applications that require other (more complex) aggregation functions, its complexity is exponential in the arity of the constraints and thus, its usefulness is limited. In this paper we investigate the performance of the Max-sum algorithm on two implementations of the DCOP_MST model. Each implementation considers a different joint credibility function for determining the coverage for each target, with respect to the locations and the credibility of agents. In the first, the coverage is calculated according to the number of agents that are located within sensing range from the target. This function can be calculated efficiently. The second takes the angle between the lines of sight of different agents to a target into consideration. The larger the difference in the angle between the lines of sight, the higher the coverage efficiency. We analyze the challenges in adjusting the Max-sum algorithm in both scenarios and propose enhancements of the algorithm that make it more efficient. We provide empirical evidence of the advantages resulting from these enhancements in comparison to the naive algorithm. [ABSTRACT FROM AUTHOR]

Mobile agents environment is a new application paradigm with unique features such as mobility and autonomy. Traditional deadlock detection algorithms in distributed computing systems do not work well in mobile agent systems due to the unique feature property of the mobile agent. Existing deadlock detection and resolution algorithms in mobile agent systems have limitations such as performance inefficiency and duplicate detection/resolution when multiple mobile agents simultaneously detect/resolve the same deadlock. To address these problems, we propose an improved deadlock detection and resolution algorithm that adopts priority-based technique and lazy reaction strategy. The priority-based technique aims to ensure that there is only one instance of deadlock detection and resolution, and it also helps reduce mobile agent movement and data traffic together with the lazy reaction strategy. The liveness and safety properties of the proposed algorithm are proved in this paper. Theoretical analysis and experimental results show that the proposed algorithm provides better performance in terms of agent movement, data traffic, and execution time. [ABSTRACT FROM AUTHOR]

Mobile agent (MA), a part of the mobile computing paradigm, was recently proposed for data gathering in Wireless Sensor Networks (WSNs). The MA-based approach employs two algorithms: Single-agent Itinerary Planning (SIP) and Multi-mobile agent Itinerary Planning (MIP) for energy-efficient data gathering. The MIP was proposed to outperform the weakness of SIP by introducing distributed multi MAs to perform the data gathering task. Despite the advantages of MIP, finding the optimal number of distributed MAs and their itineraries are still regarded as critical issues. The existing MIP algorithms assume that the itinerary of the MA has to start and return back to the sink node. Moreover, each distributed MA has to carry the processing code (data aggregation code) to collect the sensory data and return back to the sink with the accumulated data. However, these assumptions have resulted in an increase in the number of MA's migration hops, which subsequently leads to an increase in energy and time consumption. In this paper, a spawn multi-mobile agent itinerary planning (SMIP) approach is proposed to mitigate the substantial increase in cost of energy and time used in the data gathering processes. The proposed approach is based on the agent spawning such that the main MA is able to spawn other MAs with different tasks assigned from the main MA. Extensive simulation experiments have been conducted to test the performance of the proposed approach against some selected MIP algorithms. The results show that the proposed SMIP outperforms the counterpart algorithms in terms of energy consumption and task delay (time), and improves the integrated energy-delay performance. [ABSTRACT FROM AUTHOR]

Two mobile agents, starting at arbitrary, possibly different times from arbitrary nodes of an unknown network, have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. Agents have different labels which are positive integers. Each agent knows its own label, but not the label of the other agent. In traditional formulations of the rendezvous problem, meeting is accomplished when the agents get to the same node in the same round. We want to achieve a more demanding goal, called rendezvous with detection: agents must become aware that the meeting is accomplished, simultaneously declare this and stop. This awareness depends on how an agent can communicate to the other agent its presence at a node. We use two variations of the arguably weakest model of communication, called the beeping model, introduced in [8]. In each round an agent can either listen or beep. In the local beeping model, an agent hears a beep in a round if it listens in this round and if the other agent is at the same node and beeps. In the global beeping model, an agent hears a loud beep in a round if it listens in this round and if the other agent is at the same node and beeps, and it hears a soft beep in a round if it listens in this round and if the other agent is at some other node and beeps. We first present a deterministic algorithm of rendezvous with detection working, even for the local beeping model, in an arbitrary unknown network in time polynomial in the size of the network and in the length of the smaller label (i.e., in the logarithm of this label). However, in this algorithm, agents spend a lot of energy: the number of moves that an agent must make, is proportional to the time of rendezvous. It is thus natural to ask if bounded-energy agents, i.e., agents that can make at most c moves, for some integer c, can always achieve rendezvous with detection as well. This is impossible for some networks of unbounded size. Hence we rephrase the question: Can bounded-energy agents always achieve rendezvous with detection in bounded-size networks? We prove that the answer to this question is positive, even in the local beeping model but, perhaps surprisingly, this ability comes at a steep price of time: the meeting time of bounded-energy agents is exponentially larger than that of unrestricted agents. By contrast, we show an algorithm for rendezvous with detection in the global beeping model that works for bounded-energy agents (in bounded-size networks) as fast as for unrestricted agents. [ABSTRACT FROM AUTHOR]

Two mobile agents, starting at arbitrary, possibly different times from arbitrary nodes of an unknown network, have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. Agents have different labels which are positive integers. Each agent knows its own label, but not the label of the other agent. In traditional formulations of the rendezvous problem, meeting is accomplished when the agents get to the same node in the same round. We want to achieve a more demanding goal, called rendezvous with detection: agents must become aware that the meeting is accomplished, simultaneously declare this and stop. This awareness depends on how an agent can communicate to the other agent its presence at a node. We use two variations of the arguably weakest model of communication, called the beeping model, introduced in [8]. In each round an agent can either listen or beep. In the local beeping model, an agent hears a beep in a round if it listens in this round and if the other agent is at the same node and beeps. In the global beeping model, an agent hears a loud beep in a round if it listens in this round and if the other agent is at the same node and beeps, and it hears a soft beep in a round if it listens in this round and if the other agent is at some other node and beeps. We first present a deterministic algorithm of rendezvous with detection working, even for the local beeping model, in an arbitrary unknown network in time polynomial in the size of the network and in the length of the smaller label (i.e., in the logarithm of this label). However, in this algorithm, agents spend a lot of energy: the number of moves that an agent must make, is proportional to the time of rendezvous. It is thus natural to ask if bounded-energy agents, i.e., agents that can make at most c moves, for some integer c, can always achieve rendezvous with detection as well. This is impossible for some networks of unbounded size. Hence we rephrase the question: Can bounded-energy agents always achieve rendezvous with detection in bounded-size networks? We prove that the answer to this question is positive, even in the local beeping model but, perhaps surprisingly, this ability comes at a steep price of time: the meeting time of bounded-energy agents is exponentially larger than that of unrestricted agents. By contrast, we show an algorithm for rendezvous with detection in the global beeping model that works for bounded-energy agents (in bounded-size networks) as fast as for unrestricted agents. [ABSTRACT FROM AUTHOR]

We consider the problem of exploration of networks, some of whose edges are faulty. A mobile agent, situated at a starting node and unaware of which edges are faulty, has to explore the connected fault-free component of this node by visiting all of its nodes. The cost of the exploration is the number of edge traversals. For a given network and given starting node, the overhead of an exploration algorithm is the worst-case ratio (taken over all fault configurations) of its cost to the cost of an optimal algorithm which knows where faults are situated. An exploration algorithm, for a given network and given starting node, is called perfectly competitive if its overhead is the smallest among all exploration algorithms not knowing the location of faults. We design a perfectly competitive exploration algorithm for any ring, and show that, for networks modeled by hamiltonian graphs, the overhead of any DFS exploration is at most 10/9 times larger than that of a perfectly competitive algorithm. Moreover, for hamiltonian graphs of size at least 24, this overhead is less than 6% larger than that of a perfectly competitive algorithm. [ABSTRACT FROM AUTHOR]

This paper investigates an open problem introduced in Dieudonné et al. (ACM Trans Algorithms 11(1):1, 2014). Two or more mobile agents start from nodes of a network and have to accomplish the task of gathering which consists in getting all together at the same node at the same time. An adversary chooses the initial nodes of the agents and assigns a different positive integer (called label) to each of them. Initially, each agent knows its label but does not know the labels of the other agents or their positions relative to its own. Agents move in synchronous rounds and can communicate with each other only when located at the same node. Up to f of the agents are Byzantine. A Byzantine agent can choose an arbitrary port when it moves, can convey arbitrary information to other agents and can change its label in every round, in particular by forging the label of another agent or by creating a completely new one. What is the minimum number $${\mathcal {M}}$$ of good agents that guarantees deterministic gathering of all of them, with termination? We provide exact answers to this open problem by considering the case when the agents initially know the size of the network and the case when they do not. In the former case, we prove $${\mathcal {M}}=f+1$$ while in the latter, we prove $${\mathcal {M}}=f+2$$ . More precisely, for networks of known size, we design a deterministic algorithm gathering all good agents in any network provided that the number of good agents is at least $$f+1$$ . For networks of unknown size, we also design a deterministic algorithm ensuring the gathering of all good agents in any network but provided that the number of good agents is at least $$f+2$$ . Both of our algorithms are optimal in terms of required number of good agents, as each of them perfectly matches the respective lower bound on $${\mathcal {M}}$$ shown in Dieudonné et al. (2014), which is of $$f+1$$ when the size of the network is known and of $$f+2$$ when it is unknown. Perhaps surprisingly, our results highlight an interesting feature when put in perspective with known results concerning a relaxed variant of this problem in which the Byzantine agents cannot change their initial labels. Indeed under this variant $${\mathcal {M}}=1$$ for networks of known size and $${\mathcal {M}}=f+2$$ for networks of unknown size. Following this perspective, it turns out that when the size of the network is known, the ability for the Byzantine agents to change their labels significantly impacts the value of $${\mathcal {M}}$$ . However, the relevance for $${\mathcal {M}}$$ of such an ability completely disappears in the most general case where the size of the network is unknown, as $${\mathcal {M}}=f+2$$ regardless of whether Byzantine agents can change their labels or not. [ABSTRACT FROM AUTHOR]

This paper proposes a bearing-only measurement based guidance algorithm for a mobile agent to navigate in a two-dimensional plane. Based on the bearing vectors and the subtended angles related to three stationary beacons, the proposed algorithm allows the agent to reach its desired location. We show that the agent reaches its desired location globally asymptotically based on Lyapunov stability theory. Under some assumptions, the agent is also proved to reach the desired location exponentially based on Lyapunov's indirect method. Simulations and actual experimental tests on quadrotor system are also provided to verify the effectiveness of the proposed algorithm in outdoor environment. [ABSTRACT FROM AUTHOR]

Many factors give rise to the diffusion of basic computing resources in cloud computing environment, such as the distribution, shareability and heterogeneousness of cloud platform and the loose coupling, time variability and randomness of load. Therefore, the paper studies the scheduling problem of basic computing resources in cloud computing environments from the perspective of IaaS resource provider. First, the paper proposes the resource deployment architecture on the basis of mobile Agent paradigm. Second, the paper designs a 'searching-decision making-executing" multistage iterative scheduling model for catching the local features of workload under the constraints of real time and fine-grained. Third, the paper introduces the Skyline computing idea to establish the selecting strategy by using the optimal assigning and scheduling model. Finally, in comparison with RoundRobin Scheduling Algorithm and Utilization Perception Algorithm, the proposed schemes own better performance. [ABSTRACT FROM AUTHOR]

In this paper, a mobile agent based distributed EM (Expectation Maximization) algorithm is developed for density estimation and data clustering in sensor networks. It has been assumed that sensor measurements can be statistically modeled by a common Gaussian mixture model. This algorithm not only executes the EM algorithm in a distributed manner, but reduces the number of iterations of the EM algorithm and increases its convergence rate. Convergence of the proposed method will also be studied analytically and will be shown that the estimated parameters will eventually converge to their true values. Finally, the proposed method will be applied to synthetic data sets in order to show its promising performance. [ABSTRACT FROM AUTHOR]

A set of identical, mobile agents is deployed in a weighted network. Each agent has a battery-a power source allowing it to move along network edges. An agent uses its battery proportionally to the distance traveled. We consider two tasks: convergecast, in which at the beginning, each agent has some initial piece of information, and information of all agents has to be collected by some agent; and broadcast in which information of one specified agent has to be made available to all other agents. In both tasks, the agents exchange the currently possessed information when they meet. The objective of this paper is to investigate what is the minimal value of power, initially available to all agents, so that convergecast or broadcast can be achieved. We study this question in the centralized and the distributed settings. In the centralized setting, there is a central monitor that schedules the moves of all agents. In the distributed setting every agent has to perform an algorithm being unaware of the network. In the centralized setting, we give a linear-time algorithm to compute the optimal battery power and the strategy using it, both for convergecast and for broadcast, when agents are on the line. We also show that finding the optimal battery power for convergecast or for broadcast is NP-hard for the class of trees. On the other hand, we give a polynomial algorithm that finds a 2-approximation for convergecast and a 4-approximation for broadcast, for arbitrary graphs.In the distributed setting, we give a 2-competitive algorithm for convergecast in trees and a 4-competitive algorithm for broadcast in trees. The competitive ratio of 2 is proved to be the best for the problem of convergecast, even if we only consider line networks. Indeed, we show that there is no ( $$2-\epsilon $$ )-competitive algorithm for convergecast or for broadcast in the class of lines, for any $$\epsilon >0$$ . [ABSTRACT FROM AUTHOR]

We investigate the parallel traversal of a graph with multiple robots unaware of each other. All robots traverse the graph in parallel forever and the goal is to minimize the time needed until the last node is visited ( first visit time ) and the time between revisits of a node ( revisit time ). We also want to minimize the visit time , i.e. the maximum of the first visit time and the time between revisits of a node. We present randomized algorithms for uncoordinated robots, which can compete with the optimal coordinated traversal by a small factor, the so-called competitive ratio . For any number of robots ring and path graph simple traversal strategies allow constant competitive factors even in the worst case. For grid and torus graphs with n nodes and any number of robots there is an O ( log ⁡ n ) -competitive algorithm for both visit problems succeeding with high probability, i.e. with probability 1 − n − O ( 1 ) . For general graphs we present an O ( log 2 ⁡ n ) -competitive algorithm for the first visit problem, while for the visit problem we show an O ( log 3 ⁡ n ) -competitive algorithm both succeeding with high probability. [ABSTRACT FROM AUTHOR]

Two mobile agents starting at different nodes of an unknown network have to meet. This task is known in the literature as rendezvous. Each agent has a different label which is a positive integer known to it but unknown to the other agent. Agents move in an asynchronous way: the speed of agents may vary and is controlled by an adversary. The cost of a rendezvous algorithm is the total number of edge traversals by both agents until their meeting. The only previous deterministic algorithm solving this problem has cost exponential in the size of the graph and in the larger label. In this paper we present a deterministic rendezvous algorithm with cost polynomial in the size of the graph and in the length of the smaller label. Hence, we decrease the cost exponentially in the size of the graph and doubly exponentially in the labels of agents. As an application of our rendezvous algorithm we solve several fundamental problems involving teams of unknown size larger than 1 of labeled agents moving asynchronously in unknown networks. Among them are the following problems: team size, in which every agent has to find the total number of agents; leader election, in which all agents have to output the label of a single agent; perfect renaming, in which all agents have to adopt new and different labels from the set {1,...,k}, where k is the number of agents; and gossiping, in which each agent has initially a piece of information (value) and all agents have to output all the values. Using our rendezvous algorithm, we solve all of these problems at cost polynomial in the size of the graph and in the smallest length of all labels of participating agents. [ABSTRACT FROM AUTHOR]

An unmanned aerial vehicle (UAV) is a promising carriage for data gathering in wireless sensor networks since it has sufficient as well as efficient resources both in terms of time and energy due to its direct communication between the UAV and sensor nodes. On the other hand, to realize the data gathering system with UAV in wireless sensor networks, there are still some challenging issues remain such that the highly affected problem by the speed of UAVs and network density, also the heavy conflicts if a lot of sensor nodes concurrently send its own data to the UAV. To solve those problems, we propose a new data gathering algorithm, leveraging both the UAV and mobile agents (MAs) to autonomously collect and process data in wireless sensor networks. Specifically, the UAV dispatches MAs to the network and every MA is responsible for collecting and processing the data from sensor nodes in an area of the network by traveling around that area. The UAV gets desired information via MAs with aggregated sensory data. In this paper, we design a itinerary of MA migration with considering the network density. Simulation results demonstrate that our proposed method is time- and energy-efficient for any density of the network. [ABSTRACT FROM AUTHOR]

A team consisting of an unknown number of mobile agents starting from different nodes of an unknown network, possibly at different times, have to explore the network: Every node must be visited by at least one agent, and all agents must eventually stop. Agents are anonymous (identical), execute the same deterministic algorithm, and move in synchronous rounds along links of the network. They are silent: They cannot send any messages to other agents or mark visited nodes in any way. In the absence of any additional information, exploration with termination of an arbitrary network in this model, devoid of any means of communication between agents, is impossible. Our aim is to solve the exploration problem by giving to agents very restricted local traffic reports. Specifically, an agent that is at a node v in a given round is provided with three bits of information answering the following questions: Am I alone at v? Did any agent enter v in this round? Did any agent exit v in this round? We show that this small amount of information permits us to solve the exploration problem in arbitrary networks. More precisely, we give a deterministic terminating exploration algorithm working in arbitrary networks for all initial configurations that are not perfectly symmetric; that is, in which there are agents with different views of the network. The algorithm works in polynomial time in the (unknown) size of the network. A deterministic terminating exploration algorithm working for all initial configurations in arbitrary networks does not exist. [ABSTRACT FROM AUTHOR]

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, have to meet at the same node. Agents move in synchronous rounds. Each agent has a different label. Up to f of the agents are Byzantine. We consider two levels of Byzantine behavior. A strongly Byzantine agent can choose an arbitrary port when it moves and it can convey arbitrary information to other agents, while a weakly Byzantine agent can do the same, except changing its label. What is the minimum number of good agents that guarantees deterministic gathering of all of them, with termination? We solve exactly this Byzantine gathering problem in arbitrary networks for weakly Byzantine agents and give approximate solutions for strongly Byzantine agents, both when the size of the network is known and when it is unknown. It turns out that both the strength versus the weakness of Byzantine behavior and the knowledge of network size significantly impact the results. For weakly Byzantine agents, we show that any number of good agents permits solving the problem for networks of known size. If the size is unknown, then this minimum number is f + 2. More precisely, we show a deterministic polynomial algorithm that gathers all good agents in an arbitrary network, provided that there are at least f + 2 of them. We also provide a matching lower bound: we prove that if the number of good agents is at most f + 1, then they are not able to gather deterministically with termination in some networks. For strongly Byzantine agents, we give a lower bound of f + 1, even when the graph is known: we show that f good agents cannot gather deterministically in the presence of f Byzantine agents even in a ring of known size. On the positive side, we give deterministic gathering algorithms for at least 2 f + 1 good agents when the size of the network is known and for at least 4 f + 2 good agents when it is unknown. [ABSTRACT FROM AUTHOR]

We consider the gathering problem of multiple (mobile) agents in anonymous unidirectional ring networks under the constraint that each agent knows neither the number of nodes nor the number of agents. For this problem, we fully characterize the relation between probabilistic solvability and termination detection. First, we prove for any (small) constant p (0

Two identical (anonymous) mobile agents start from arbitrary nodes of an unknown tree and have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. We consider deterministic algorithms for this rendezvous task. The main result of this paper is a tight trade-off between the optimal time of completing rendezvous and the size of memory of the agents. For agents with $$k$$ memory bits, we show that optimal rendezvous time is $$\Theta (n+n^2/k)$$ in $$n$$ -node trees. More precisely, if $$k \ge c\log n$$ , for some constant $$c$$ , we design agents accomplishing rendezvous in arbitrary trees of size $$n$$ (unknown to the agents) in time $$O(n+n^2/k)$$ , starting with arbitrary delay. We also show that no pair of agents can accomplish rendezvous in time $$o(n+n^2/k)$$ , even in the class of lines of known length and even with simultaneous start. Finally, we prove that at least logarithmic memory is necessary for rendezvous, even for agents starting simultaneously in a $$n$$ -node line. [ABSTRACT FROM AUTHOR]

A mobile agent starting at an arbitrary node of an m × k grid, for 1 < m ≤ k, has to explore the grid by visiting all its nodes and traversing all edges. The cost of an exploration algorithm is the number of edge traversals by the agent. Nodes of the grid are unlabeled and ports at each node v have distinct numbers in {0,..., d − 1}, where d = 2, 3, 4 is the degree of v. Port numbering is local, i.e., there is no relation between port numbers at different nodes. When visiting a node the agent sees its degree. It also sees the port number by which it enters a node and can choose the port number by which it leaves a visited node. We are interested in deterministic exploration algorithms working at low cost. We consider the scenario in which the agent is equipped with a stationary token situated at its starting node. The agent sees the token whenever it visits this node. We give an exploration algorithm working at cost O(k2) for 2 × k grids, and at cost O(m2k), for m × k grids, when 2 < m ≤ k. [ABSTRACT FROM AUTHOR]

Abstract: Asynchrony is one of the main challenges in distributed computing. Some tasks, such as distributed Byzantine consensus, are impossible in the asynchronous setting, while they can be carried out synchronously. For other tasks, such as rendezvous in arbitrary graphs, the best known synchronous algorithm has cost much lower than the best asynchronous one. Various degrees of asynchrony and synchrony and comparisons between them in terms of feasibility of distributed tasks have been particularly intensely studied in the context of mobile agents computing. However, somewhat surprisingly, there are no results showing a provable difference of cost between the synchronous and asynchronous versions of a task executed by mobile agents. The aim of this paper is to fill up this gap. We show for the first time that for some natural task executed by mobile agents in a network, the optimal cost of its deterministic solution in the asynchronous setting has higher order of magnitude than that in the synchronous scenario. The task for which we show this difference is well-studied: that of rendezvous of two agents in an infinite oriented grid. More precisely, we consider two agents with distinct integer labels starting at a distance D in the infinite oriented grid. Each agent knows D and its own label but not the label of the other agent and it does not know the position of the other agent relative to its own. Agents do not have any global system of coordinates. They have to meet in a node or inside an edge of the grid, and the cost of a rendezvous algorithm is the number of edge traversals by both agents until the meeting. We show that in the synchronous scenario rendezvous can be performed at cost , where ℓ is the length of the (binary representation of the) smaller label, while cost is needed for asynchronous completion of rendezvous. Hence, for instances with , the optimal cost of asynchronous rendezvous is asymptotically larger than that of synchronous rendezvous. [Copyright &y& Elsevier]

We consider the problem of leader election among mobile agents operating in an arbitrary network modeled as an undirected graph. Nodes of the network are unlabeled and all agents are identical. Hence the only way to elect a leader among agents is by exploiting asymmetries in their initial positions in the graph. Agents do not know the graph or their positions in it, hence they must gain this knowledge by navigating in the graph and share it with other agents to accomplish leader election. This can be done using meetings of agents, which is difficult because of their asynchronous nature: an adversary has total control over the speed of agents. When can a leader be elected in this adversarial scenario and how to do it? We give a complete answer to this question by characterizing all initial configurations for which leader election is possible and by constructing an algorithm that accomplishes leader election for all configurations for which this can be done. [ABSTRACT FROM AUTHOR]

Abstract: We study the impact of the topological structure on the complexity of the Black hole search (Bhs) problem using mobile agents that communicate via tokens. First, we show that the token model can support the same cost as in the whiteboard model, despite the fact that communication between mobile agents is considerably more restricted (and complex) in a token model than in a whiteboard one. More precisely, in this paper, we focus on three specific topologies, namely: an asynchronous (i) hypercube, (ii) torus and (iii) complete network. With knowledge of which of these topologies is being used, we present token-based solutions for Bhs where the number of moves executed by a team of two co-located anonymous agents can be reduced to . These proposed solutions do not require the availability of a map and do not assume FIFO on either nodes or links. Second, we consider the use of scattered agents for Bhs in an asynchronous (i) torus and (ii) complete network. We show that, using 3 scattered agents and 7 tokens in total, a black hole can be located with moves in an oriented asynchronous torus. Again, the solution does not assume FIFO on the links and nodes. If the number of scattered agents in a torus increases, the cost is reduced but communication between these agents becomes significantly more complicated. We propose an algorithm that solves Bhs using ( ) scattered agents, with only 1 token per agent, with moves. Beyond theoretical proofs, we also discuss simulations of an actual system in order to evaluate our proposed solutions. [Copyright &y& Elsevier]

This paper presents a novel real-time path planning algorithm, called InsertBug, for an autonomous mobile agent in completely unknown environment. By using the algorithm, all the planned paths are described and stored by vectors. The algorithm combines range sensor data with safety radius to determine the blocking obstacles and calculate the shortest path by choosing the intermediate points. When there is obstacle blocking the current path, the intermediate points will be calculated, and the planned path will be regenerated by inserting the intermediate points. The local optimum avoidance strategy is also considered in this algorithm by specifying a fixed direction. The agent will return to the optimal direction after running out of the local optimum. Different simulation parameters are taken to show the advantages of this algorithm. Moreover, the performance of this algorithm has also been evaluated by comparing with another usual method via simulations. The results show that the safety performance and time requirements of this algorithm are significant superior to the algorithm contrasted with. [ABSTRACT FROM AUTHOR]

A survey on the routing protocols based on ant-like mobile agents is given. These protocols are often employed in Mobile Ad Hoc Networks (MANET). Mobile Ad Hoc Networks are collections of wireless mobile nodes such as PDAs, laptop computers, and cellular phones having wireless communication capability that dynamically form a temporary network without using any existing network infrastructures such as wireless access points. The only infrastructure in MANET is the wireless communication interfaces on the devices. In such a circumstance, where some of the wireless devices are not within wireless range of each other, multi-hop routing is required to transmit messages to the destination. A node that wants to start communication with other nodes that are not within its one-hop wireless transmission range has to request intermediate nodes to forward their communication packets to the destination. In this paper, we survey a variety of proposed network protocols to accommodate this situation. We focus especially on biologically-inspired routing algorithms that are based on the ant colony optimization algorithm. [ABSTRACT FROM AUTHOR]

This paper addresses cooperative search for multiple stationary ground targets by a group of unmanned aerial vehicles with limited sensing and communication capabilities. The whole surveillance region is partitioned into cells where each cell is associated with a probability of target existence within the cell, which constitutes a probability map for the whole region. Each agent keeps an individual probability map and updates the map individually with measurements according to Bayesian rule. A nonlinear transformation of the probability map is introduced to simplify the computation by linearizing the Bayesian update. A consensus-like distributed fusion scheme is proposed for multiagent map fusion. We prove that all the individual probability maps converge to the same one that reflects the true existence or nonexistence of targets within each cell. Coverage and topology control algorithms are designed for the path planning of mobile agents. Moreover, the performance of the fusion scheme for asynchronous implementations of sampling and communication is analyzed. Finally, the effectiveness of the proposed algorithms is illustrated via simulations. [ABSTRACT FROM PUBLISHER]

This paper studies synchronization via pinning control on general complex dynamical networks, such as strongly connected networks, networks with a directed spanning tree, weakly connected networks, and directed forests. A criterion for ensuring network synchronization on strongly connected networks is given. It is found that the vertices with very small in-degrees should be pinned first. In addition, it is shown that the original condition with controllers can be reformulated such that it does not depend on the form of the chosen controllers, which implies that the vertices with very large out-degrees may be pinned. Then, a criterion for achieving synchronization on networks with a directed spanning tree, which can be composed of many strongly connected components, is derived. It is found that the strongly connected components with very few connections from other components should be controlled and the components with many connections from other components can achieve synchronization even without controls. Moreover, a simple but effective pinning algorithm for reaching synchronization on a general complex dynamical network is proposed. Finally, some simulation examples are given to verify the proposed pinning scheme. [ABSTRACT FROM AUTHOR]

Big data and distributed computing are of great importance in wireless sensor networks (WSNs).They are always bonded together, and the latter one upholds the former one. In distributed computing, mobile agent model is the mainstream technology. With autonomy, communicativeness, mobility, and role, mobile agent model is more suitable for large-scale, resources-restrained WSN to deal with big data. This paper mainly studies migration schemes for mobile agents, determines core factors of migration strategy, and proposes SMLA and DMLA algorithms. And aiming at revealing the characteristics of target tracking, this paper puts forward pid-DMLA algorithm; and considering multiple agents' cooperation, it presents Mpid-DMLA algorithm. Moreover, this paper evaluates and analyzes the advantages and disadvantages of the above-mentioned four algorithms by simulations. [ABSTRACT FROM AUTHOR]

We consider the coalescence or gathering problem: a set of k mobile agents (robots) with distinct identifiers have to locate one another and gather at a common location. Agents may face several challenges: swarms of agent may be too large to simultaneously observe one another, agent sensors may be subject to noise, and some agents may be malicious. For small swarms, we design an algorithm coalescing all trustworthy agents despite sensor noise and an arbitrary number of malicious agents. This algorithm requires that all coalescing agents be able to simultaneously observe a single agent, limiting its practical scalability. For arbitrarily large swarms we design an algorithm achieving coalescence as long as the number of malicious agents near any given trustworthy agent is bounded. In both cases, our algorithms work by reduction to blackbox solutions to well-studied problems, allowing them to be used in any environment and for any type of agents for which deterministic rendezvous, agent state estimation, and pair-wise cohesion algorithms are available. [ABSTRACT FROM AUTHOR]

Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent is continuous, does not leave its route and covers all of it. Meeting in a graph means that both agents must be at the same time in some node or in some point inside an edge of the graph, while meeting in a terrain means that both agents must be at the same time in some point of the terrain. Does there exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerful adversary? We give deterministic rendezvous algorithms for agents starting at arbitrary nodes of any anonymous connected graph (finite or infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior. In the geometric scenario agents may have different compasses and different units of length. While our algorithms work in a very general setting - agents can, indeed, meet almost everywhere - we show that none of these few limitations imposed on the environment can be removed. On the other hand, our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary interior points of a terrain as previously stated agents will eventually get to within an arbitrarily small positive distance from each other. [ABSTRACT FROM AUTHOR]

Abstract: Mobile agents act as the task executors in migrating workflow system. As the size of workflow is increased by including many tasks and branches, multiple mobile agents should be used where each agent is responsible for a branch of the workflow process and fulfills the workflow goal by cooperating with its partners. In this case, the workflow process needs to be partitioned into a set of sub-processes before execution so that each sub-process can be assigned to one mobile agent. This paper proposes a structured process partition approach that includes process structure partition and Quality of Service(QoS) objective partition. The former partitions a structured process into a set of sub-processes with dominant relations and each sub-process consists of a sequence of tasks. The latter distributes QoS objectives, such as the expected budget or deadline of the whole workflow, over all of the sub-processes. In addition, a sub-process execution planning algorithm with QoS objective based on Markov Decision Process (MDP) is also put forward in this paper. The experiment results show that the effects of workflow partition method and MDP based process planning method are sound. [Copyright &y& Elsevier]

Navigation of a group of autonomous agents that are required to maintain a formation is a challenging task which has not been studied much especially in 3-D terrains. This paper presents a novel approach to collision free path finding of multiple agents preserving a predefined formation in 3-D terrains. The proposed method could be used in many areas like navigation of semi-automated forces (SAF) at unit level in military simulations and non-player characters (NPC) in computer games. The proposed path finding algorithm first computes an optimal path from an initial point to a target point after analyzing the 3-D terrain data from which it constructs a weighted graph. Then, it employs a real-time path finding algorithm specifically designed to realize the navigation of the group from one waypoint to the successive one on the optimal path generated at the previous stage, preserving the formation and avoiding collision. Software was developed to test the methods discussed here. [ABSTRACT FROM AUTHOR]

Current mobile agent algorithms for mapping faults in computer networks assume that the network is static. However, for large classes of highly dynamic networks (e.g., wireless mobile ad hoc networks, sensor networks, vehicular networks), the topology changes as a function of time. These networks, called delay-tolerant, challenged, opportunistic, etc., have never been investigated with regard to locating faults. We consider a subclass of these networks modeled on an urban subway system. We examine the problem of creating a map of such a subway. More precisely, we study the problem of a team of asynchronous computational entities (the mapping agents) determining the location of black holes in a highly dynamic graph, whose edges are defined by the asynchronous movements of mobile entities (the subway carriers). We determine necessary conditions for the problem to be solvable. We then present and analyze a solution protocol; we show that our algorithm solves the fault mapping problem in subway networks with the minimum number of agents possible, k= γ+1, where γ is the number of carrier stops at black holes. The number of carrier moves between stations required by the algorithm in the worst case is $O(k \cdot n_{C}^{2}\cdot l_{R} + n_{C}\cdot l_{R}^{2})$ , where nC is the number of subway trains, and lR is the length of the subway route with the most stops. We establish lower bounds showing that this bound is tight. Thus, our protocol is both agent-optimal and move-optimal. [ABSTRACT FROM AUTHOR]

Wireless sensor networks are increasingly adopted both in aircraft and civil structural health monitoring. However, due to the limited resources on a wireless sensor node, structural evaluation ability of the wireless sensor network is also limited, especially for large-scale structures. This paper presents a multi-agent cooperation system based on mobile agent technology for wireless sensor network-based structural health monitoring which deals with the evaluation of large-scale structure. Mobile agent with the signal processing or evaluation algorithm is designed to migrate among different sensor nodes and perform network self organization, data processing, information fusion, and damage estimation. This method can reduce the request to the sensor nodes and achieve a better monitoring and evaluation performance through multiagent cooperation. The proposed mobile multiagent system is evaluated by a large dimension aerospace aluminum structure monitoring experiment in which strain distribution and joint failure are monitored by different sensors. Experimental results show that the system can significantly improve the monitoring performance for large-scale structures. [ABSTRACT FROM AUTHOR]

Mobile agent (MA) systems provide new capabilities for energy-efficient data processing by flexibly planning its itinerary for facilitating agent-based data collection and aggregation. In this paper, we present a cooperative data processing algorithm based on mobile agent (MA-CDP), and considers MA inmultihop environments and can autonomously clone andmigrate themselves in response to environmental changes. MA accounts for performing data processing and making data aggregation decisions at nodes rather than bringing data back to a central processor, and redundant sensory data will be eliminated. The results of our simulation show that MA-based cooperative data processing provides better performance than directed diffusion in terms of end-to-end delivery latency, packet delivery ratio, and energy consumption. [ABSTRACT FROM AUTHOR]