Positional Consensus in Multi-Agent Systems using a Broadcast Control Mechanism

In this paper a strategy for controlling a group of agents to achieve positional consensus is presented. The proposed technique is based on the constraint that every agents must be given the same control input through a broadcast communication mechanism. Although the control command is computed using state information in a global framework, the control input is implemented by the agents in a local coordinate frame. We propose a novel linear programming formulation that is computationally less intensive than earlier proposed methods. Moreover, we introduce a random perturbation input in the control command that helps us to achieve perfect consensus even for a large number of agents, which was not possible with the existing strategy in the literature. Moreover, we extend the method to achieve positional consensus at a pre-specified location. The effectiveness of the approach is illustrated through simulation results.

Negotiation schemes for multi-agent cooperative search

Because of limited sensor and communication ranges, designing efficient mechanisms for cooperative tasks is difficult. In this article, several negotiation schemes for multiple agents performing a cooperative task are presented. The negotiation schemes provide suboptimal solutions, but have attractive features of fast decision-making, and scalability to large number of agents without increasing the complexity of the algorithm. A software agent architecture of the decision-making process is also presented. The effect of the magnitude of information flow during the negotiation process is studied by using different models of the negotiation scheme. The performance of the various negotiation schemes, using different information structures, is studied based on the uncertainty reduction achieved for a specified number of search steps. The negotiation schemes perform comparable to that of optimal strategy in terms of uncertainty reduction and also require very low computational time, similar to 7 per cent to that of optimal strategy. Finally, analysis on computational and communication requirement for the negotiation schemes is carried out.

Deploy and search strategy for multi-agent systems using Voronoi partitions

In this paper we analyze a deploy and search strategy for multi-agent systems. Mobile agents equipped with sensors carry out search operation in the search space. The lack of information about the search space is modeled as an uncertainty density distribution over the space, and is assumed to be known to the agents a priori. In each step, the agents deploy themselves in an optimal way so as to maximize per step reduction in the uncertainty density. We analyze the proposed strategy for convergence and spatial distributedness. The control law moving the agents has been analyzed for stability and convergence using LaSalle's invariance principle, and for spatial distributedness under a few realistic constraints on the control input such as constant speed, limit on maximum speed, and also sensor range limits. The simulation experiments show that the strategy successfully reduces the average uncertainty density below the required level.

Self assessment schemes for multi-agent cooperative search

In this paper, we present self assessment schemes (SAS) for multiple agents performing a search mission on an unknown terrain. The agents are subjected to limited communication and sensor ranges. The agents communicate and coordinate with their neighbours to arrive at route decisions. The self assessment schemes proposed here have very low communication and computational overhead. The SAS also has attractive features like scalability to large number of agents and fast decision-making capability. SAS can be used with partial or complete information sharing schemes during the search mission. We validate the performance of SAS using simulation on a large search space consisting of 100 agents with different information structures and self assessment schemes. We also compare the results obtained using SAS with that of a previously proposed negotiation scheme. The simulation results show that the SAS is scalable to large number of agents and can perform as good as the negotiation schemes with reduced communication requirement (almost 20% of that required for negotiation).

Stability of synchronization in a multi-cellular system

Networks of biochemical reactions regulated by positive-and negative-feedback processes underlie functional dynamics in single cells. Synchronization of dynamics in the constituent cells is a hallmark of collective behavior in multi-cellular biological systems. Stability of the synchronized state is required for robust functioning of the multi-cell system in the face of noise and perturbation. Yet, the ability to respond to signals and change functional dynamics are also important features during development, disease, and evolution in living systems. In this paper, using a coupled multi-cell system model, we investigate the role of system size, coupling strength and its topology on the synchronization of the collective dynamics and its stability. Even though different coupling topologies lead to synchronization of collective dynamics, diffusive coupling through the end product of the pathway does not confer stability to the synchronized state. The results are discussed with a view to their prevalence in biological systems. Copyright (C) EPLA, 2010

Multi-Agent Rendezvous Algorithm with Rectilinear Decision Domain

The aim of this paper is to develop a computationally efficient decentralized rendezvous algorithm for a group of autonomous agents. The algorithm generalizes the notion of sensor domain and decision domain of agents to enable implementation of simple computational algorithms. Specifically, the algorithm proposed in this paper uses a rectilinear decision domain (RDD) as against the circular decision domain assumed in earlier work. Because of this, the computational complexity of the algorithm reduces considerably and, when compared to the standard Ando's algorithm available in the literature, the RDD algorithm shows very significant improvement in convergence time performance. Analytical results to prove convergence and supporting simulation results are presented in the paper.

Positional Consensus of Multi-Agent Systems Using Linear Programming Based Decentralized Control with Rectilinear Decision Domain

In this paper we develop a Linear Programming (LP) based decentralized algorithm for a group of multiple autonomous agents to achieve positional consensus. Each agent is capable of exchanging information about its position and orientation with other agents within their sensing region. The method is computationally feasible and easy to implement. Analytical results are presented. The effectiveness of the approach is illustrated with simulation results.

Automated Multi-Agent Search Using Centroidal Voronoi Configuration

This paper addresses the problem of automated multiagent search in an unknown environment. Autonomous agents equipped with sensors carry out a search operation in a search space, where the uncertainty, or lack of information about the environment, is known a priori as an uncertainty density distribution function. The agents are deployed in the search space to maximize single step search effectiveness. The centroidal Voronoi configuration, which achieves a locally optimal deployment, forms the basis for the proposed sequential deploy and search strategy. It is shown that with the proposed control law the agent trajectories converge in a globally asymptotic manner to the centroidal Voronoi configuration. Simulation experiments are provided to validate the strategy. Note to Practitioners-In this paper, searching an unknown region to gather information about it is modeled as a problem of using search as a means of reducing information uncertainty about the region. Moreover, multiple automated searchers or agents are used to carry out this operation optimally. This problem has many applications in search and surveillance operations using several autonomous UAVs or mobile robots. The concept of agents converging to the centroid of their Voronoi cells, weighted with the uncertainty density, is used to design a search strategy named as sequential deploy and search. Finally, the performance of the strategy is validated using simulations.

Multi-agent search using?sensors with heterogeneous capabilities

In this thesis we address the problem of multi-agent search. We formulate two deploy and search strategies based on optimal deployment of agents in search space so as to maximize the search effectiveness in a single step. We show that a variation of centroidal Voronoi configuration is the optimal deployment. When the agents have sensors with different capabilities, the problem will be heterogeneous in nature. We introduce a new concept namely, generalized Voronoi partition in order to formulate and solve the heterogeneous multi-agent search problem. We address a few theoretical issues such as optimality of deployment, convergence and spatial distributedness of the control law and the search strategies. Simulation experiments are carried out to compare performances of the proposed strategies with a few simple search strategies.

Fault-Tolerant Average Execution Time Optimization for General Purpose Multi-Processor System-on Chips

Fault-tolerance is due to the semiconductor technology development important, not only for safety-critical systems but also for general-purpose (non-safety critical) systems. However, instead of guaranteeing that deadlines always are met, it is for general-purpose systems important to minimize the average execution time (AET) while ensuring fault-tolerance. For a given job and a soft (transient) error probability, we define mathematical formulas for AET that includes bus communication overhead for both voting (active replication) and rollback-recovery with checkpointing (RRC). And, for a given multi-processor system-on-chip (MPSoC), we define integer linear programming (ILP) models that minimize AET including bus communication overhead when: (1) selecting the number of checkpoints when using RRC, (2) finding the number of processors and job-to-processor assignment when using voting, and (3) defining fault-tolerance scheme (voting or RRC) per job and defining its usage for each job. Experiments demonstrate significant savings in AET.

Multi-agent Search using Voronoi partitions

This paper addresses the problem of multiagent search in an unknown environment. The agents are autonomous in nature and are equipped with necessary sensors to carry out the search operation. The uncertainty, or lack of information about the search area is known a priori as a probability density function. The agents are deployed in an optimal way so as to maximize the one step uncertainty reduction. The agents continue to deploy themselves and reduce uncertainty till the uncertainty density is reduced over the search space below a minimum acceptable level. It has been shown, using LaSalle’s invariance principle, that a distributed control law which moves each of the agents towards the centroid of its Voronoi partition, modified by the sensor range leads to single step optimal deployment. This principle is now used to devise search trajectories for the agents. The simulations were carried out in 2D space with saturation on speeds of the agents. The results show that the control strategy per step indeed moves the agents to the respective centroid and the algorithm reduces the uncertainty distribution to the required level within a few steps.

Discrete time second order sliding mode observer for uncertain linear multi-output system

This paper presents a second order sliding mode observer (SOSMO) design for discrete time uncertain linear multi-output system. The design procedure is effective for both matched and unmatched bounded uncertainties and/or disturbances. A second order sliding function and corresponding sliding manifold for discrete time system are defined similar to the lines of continuous time counterpart. A boundary layer concept is employed to avoid switching across the defined sliding manifold and the sliding trajectory is confined to a boundary layer once it converges to it. The condition for existence of convergent quasi-sliding mode (QSM) is derived. The observer estimation errors satisfying given stability conditions converge to an ultimate finite bound (within the specified boundary layer) with thickness O(T-2) where T is the sampling period. A relation between sliding mode gain and boundary layer is established for the existence of second order discrete sliding motion. The design strategy is very simple to apply and is demonstrated for three examples with different class of disturbances (matched and unmatched) to show the effectiveness of the design. Simulation results to show the robustness with respect to the measurement noise are given for SOSMO and the performance is compared with pseudo-linear Kalman filter (PLKF). (C) 2013 Published by Elsevier Ltd. on behalf of The Franklin Institute

Multi-agent Reinforcement Learning for Traffic Signal Control

Optimal control of traffic lights at junctions or traffic signal control (TSC) is essential for reducing the average delay experienced by the road users amidst the rapid increase in the usage of vehicles. In this paper, we formulate the TSC problem as a discounted cost Markov decision process (MDP) and apply multi-agent reinforcement learning (MARL) algorithms to obtain dynamic TSC policies. We model each traffic signal junction as an independent agent. An agent decides the signal duration of its phases in a round-robin (RR) manner using multi-agent Q-learning with either is an element of-greedy or UCB 3] based exploration strategies. It updates its Q-factors based on the cost feedback signal received from its neighbouring agents. This feedback signal can be easily constructed and is shown to be effective in minimizing the average delay of the vehicles in the network. We show through simulations over VISSIM that our algorithms perform significantly better than both the standard fixed signal timing (FST) algorithm and the saturation balancing (SAT) algorithm 15] over two real road networks.

A multi-microprocessor architecture for solving partial differential equations

This paper presents the architecture of a fault-tolerant, special-purpose multi-microprocessor system for solving Partial Differential Equations (PDEs). The modular nature of the architecture allows the use of hundreds of Processing Elements (PEs) for high throughput. Its performance is evaluated by both analytical and simulation methods. The results indicate that the system can achieve high operation rates and is not sensitive to inter-processor communication delay.

Anthranilic acid oxidase system of Tecoma stans—II. : Studies on the properties of a purified anthranilic acid oxidase system and its separation into different enzymic components

An enzyme system which catalysed the conversion of anthranilic acid to catechol has been purified 20-fold from a cell-free leaf extract of Tecoma stans. The optimum substrate concentration was 10−3 M and optimum temperature for the reaction was 45°. The presence of a multi-enzyme system was inferred from inhibition studies. The formation of catechol was inhibited by Mg2+, Zn2+, and Co2+ ions, whereas anthranilic acid disappearance was not affected to the same extent. The effect of metal chelating agents like EDTA, cyanide and pyrophosphate showed a similar trend. PCMB inhibited catechol formation but had no effect on anthranilic acid disappearance. The reaction was not inhibited by catalase, nor was it activated by peroxide-donating systems. This ruled out the possibility of peroxidative type of reaction. The overall reaction is markedly activated by NADPH and THFA. This multi-enzyme was separated into three different components, by fractionation with Alumina Cγ and calcium phosphate gels. The overall reaction catalysed by these components can be represented as anthranilic acid→3-hydroxy anthranilic acid→o-aminophenol→catechol.