Topology-preserving flocking of nonlinear agents using optimistic planning

We consider the generalized flocking problem in multiagent systems, where the agents must drive a subset of their state variables to common values, while communication is constrained by a proximity relationship in terms of another subset of variables. We build a flocking method for general nonlinear agent dynamics, by using at each agent a near-optimal control technique from artificial intelligence called optimistic planning. By defining the rewards to be optimized in a well-chosen way, the preservation of the interconnection topology is guaranteed, under a controllability assumption. We also give a practical variant of the algorithm that does not require to know the details of this assumption, and show that it works well in experiments on nonlinear agents.     

Fault-tolerant flocking for a group of autonomous mobile robots

Consider a system composed of mobile robots that move on the plane, each of which independently executing its own instance of an algorithm. Given a desired geometric pattern, the flocking problem consists in ensuring that the robots form this pattern and maintain it while moving together on the plane. In this paper, we explore flocking in the presence of faulty robots, where the desired pattern is a regular polygon. We propose a distributed fault tolerant flocking algorithm assuming a semi-synchronous model with a k-bounded scheduler, in the sense that no robot is activated no more than k times between any two consecutive activations of any other robot.The algorithm is composed of three parts: failure detector, ranking assignment, and flocking algorithm. The role of the rank assignment is to provide a persistent and unique ranking for the robots. The failure detector identifies the set of currently correct robots in the system. Finally, the flocking algorithm handles the movement and reconfiguration of the flock, while maintaining the desired shape. The difficulty of the problem comes from the combination of the three parts, together with the necessity to prevent collisions and allow the rotation of the flock. We formally prove the correctness of our proposed solution.     

Control of dynamic response of a continuum model of a large space structure

The problem of active control of the transient dynamic response of large space structures, modeled as equivalent continua, is investigated here. The effects of initial stresses, in the form of inplane stress resultants in an equivalent plate model, on the controllability of transverse dynamic response, are studied. A singular solution approach is used to derive a fully coupled set of nodal equations of motion which also include nonproportional passive damping. One approach considers a direct attack on this system of nodal equations. An alternative scheme implements a reduced-order model of coupled ordinary differential equations which are obtained in terms of the amplitudes of the pseudomodes of the nominally undamped system. Optimal control techniques are employed to develop a feedback control law. Algorithms for the efficient solution of the Riccati equation are implemented. Several examples are presented which involve the suppression of vibration of the transient dynamic response of the structure using an arbitrary number of control force actuators.     

On the use of limited autonomous mobility for dynamic coverage maintenance in sensor networks

Sensor networks consist of small wireless sensor nodes deployed randomly over an area to monitor the environment or detect intrusion. The coverage provided by sensor networks is very crucial to their effectiveness. Many of the important applications of sensor networks demand autonomous mobility for the sensor nodes. Early failure of sensor nodes can lead to coverage loss that requires coverage maintenance schemes. In this paper, we propose Dynamic Coverage Maintenance (DCM) schemes that exploit the limited mobility of the sensor nodes. The main objective of coverage maintenance is to compensate the loss of coverage with minimum expenditure of energy. Existing autonomous sensor deployment schemes such as the “potential field approach” are not useful for DCM because the nodes initially distribute themselves such that there is no redundancy in coverage. We propose a set of DCM schemes which can be executed on individual sensor nodes having a knowledge of only their local neighborhood topology. The process of moving a node to a new location for maintenance of coverage is termed “migration”. We propose four algorithms to decide which neighbors to migrate, and to what distance, such that the energy expended is minimized and the coverage obtained for a given number of live nodes is maximized. The decision and movement are completely autonomous in the network, and involves movement of one-hop neighbors of a dead sensor node. We also propose an extension to these algorithms, called Cascaded DCM, which extends the migrations to multiple hops. We have developed a graphical simulator Java Sensor Simulator (JSS) to visually inspect the working of the algorithms. We have also compared the performance of the different algorithms in terms of the improvement in coverage, average migration distance of the nodes, and the lifetime of the network. Cascaded DCM was seen to offer the maximum network lifetime and coverage.     

Forming a desired structure topology for a group of autonomous agents based on local self-coordination

A model for the cooperation of autonomous agents of a multiagent system based on self-coordination is developed. A method is proposed to set up controls for each agent based on Kirchhoff matrices, sets of mutual-position vectors, and combined attraction–repulsion potential functions. The proposed approach was modeled for the formation of a multiagent system structure with desired topology.     

Coordination of groups of mobile autonomous agents using nearest neighbor rules

In a recent Physical Review Letters article, Vicsek et al. propose a simple but compelling discrete-time model of n autonomous agents (i.e., points or particles) all moving in the plane with the same speed but with different headings. Each agent's heading is updated using a local rule based on the average of its own heading plus the headings of its "neighbors." In their paper, Vicsek et al. provide simulation results which demonstrate that the nearest neighbor rule they are studying can cause all agents to eventually move in the same direction despite the absence of centralized coordination and despite the fact that each agent's set of nearest neighbors change with time as the system evolves. This paper provides a theoretical explanation for this observed behavior. In addition, convergence results are derived for several other similarly inspired models. The Vicsek model proves to be a graphic example of a switched linear system which is stable, but for which there does not exist a common quadratic Lyapunov function.     

Optimal distribution of a hierarchy of network management agents

In this paper, we consider several mathematical and algorithmic problems which arise naturally in the optimal deployment of modern network management systems. Specifically, we will consider the problem of minimizing the total communication costs within an architecture consisting of a distributed hierarchy of cooperating intelligent agents. We consider several communication cost models, and describe provable optimal schemes for distributing agents among machines in each of these models.     

Experimental investigation on coverage performance of a chaotic autonomous mobile robot

In many autonomous mobile robotic missions the complete and fast coverage of the workspace, scanned by an unpredictable trajectory, plays a crucial role. To satisfy these special demands in the design of an autonomous mobile robot, a motion controller, based on the dynamical behavior of a known discrete chaotic system, the Logistic map, is presented in this paper. The proposed method is based on a microcontroller for realizing a chaotic random bit generator and converting the produced chaotic bit sequence, to the robot’s trajectory of motion. The experimental results confirm that this approach, with an appropriate sensor for obstacle avoidance, can obtain very satisfactory results in regard to the fast scanning of the robot’s workspace with unpredictable way.     

An autonomous dynamic balance of an electrical bicycle in motion using variable structure under‐actuated control

Based on previous studies, two strategies, the controls of the center of gravity (CG) and the angle of steering handle, are employed to stabilize the bicycle in motion. In general, a pendulum is applied to adjust the CG of the bicycle. An additional factor is the inclination with respect to gravitational direction of the bicycle in motion (i.e., lean angle). As a whole, the system produces three outputs that will affect the dynamic balance of the electric bicycle: the angles of the pendulum, the lean, and the steering. The proposed control method used to generate the handle and pendulum torques is named variable structure under‐actuated control (VSUAC), possessing the number of control inputs smaller than the system output. The purpose of using the VSUAC is the huge uncertainties of a bicycle system, often encountered with irregularities in ground conditions and gusts of wind. Merely using the ordinary proportional‐derivative‐integral (PID) control or other linear control methods usually do not show good robust performance when the aforementioned conditions are present. Finally, the simulations of the electrical bicycle in motion using ordinary PID control, modified proportional‐derivative control (MPDC), and VSUAC are compared to judge the effectiveness and efficiency of the proposed control. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Stable Flocking Motion of Mobile Agents Following a Leader in Fixed and Switching Networks

Multiple mobile agents with double integrator dynamics, following a leader to achieve a flocking motion formation, are studied in this paper. A class of local control laws for a group of mobile agents is proposed. Prom a theoretical proof, the following conclusions are reached: (i) agents globally align their velocity vectors with a leader, (ii) they converge their velocities to the leaders velocity, (iii) collisions among interconnected agents are avoided, and (iv) agent's artificial potential functions are minimized. We model the interaction and/or communication relationship between agents by algebraic graph theory. Stability analysis is achieved by using classical Lyapunov theory in a fixed network topology, and differential inclusions and nonsmooth analysis in a switching network topology respectively. Simulation examples are provided.     

Efficient offset trimming for deformable planar curves using a dynamic hierarchy of bounding circular arcs

We present an efficient algorithm for computing a family of trimmed offsets for planar freeform curves under deformation. The algorithm is based on a dynamic bounding volume hierarchy (BVH) for the untrimmed offsets of a given planar curve, which can be generated efficiently using a hierarchy of recursive bisections of the given curve. The proposed algorithm is effective for deformable planar curves. At each time frame, we segment the input curve into monotone spiral pieces (Barton and Elber, 2011), which is the only pre-processing needed for the dynamic BVH construction. To speed up the on-line generation of dynamic BVH, we employ the bounding circular arcs (BCA) of Meek and Walton (1995) that can be computed very efficiently using the position and tangent information at the endpoints of each monotone spiral curve segment. Using several experimental results, we demonstrate the performance improvement of our algorithm over the previous biarc-based algorithm of Kim et al. (2012).     

Image categorization using a semantic hierarchy model with sparse set of salient regions

Image categorization in massive image database is an important problem. This paper proposes an approach for image categorization, using sparse set of salient semantic information and hierarchy semantic label tree （HSLT） model. First, to provide more critical image semantics, the proposed sparse set of salient regions only at the focuses of visual attention instead of the entire scene was formed by our proposed saliency detection model with incorporating low and high level feature and Shotton＇s semantic texton forests （STFs） method. Second, we also propose a new HSLT model in terms of the sparse regional semantic information to automatically build a semantic image hierarchy, which explicitly encodes a general to specific image relationship. And last, we archived image dataset using image hierarchical semantic, which is help to improve the performance of image organizing and browsing. Extension experimefital results showed that the use of semantic hierarchies as a hierarchical organizing frame- work provides a better image annotation and organization, improves the accuracy and reduces human＇s effort.     

Image categorization using a semantic hierarchy model with sparse set of salient regions

Image categorization in massive image database is an important problem. This paper proposes an approach for image categorization, using sparse set of salient semantic information and hierarchy semantic label tree (HSLT) model. First, to provide more critical image semantics, the proposed sparse set of salient regions only at the focuses of visual attention instead of the entire scene was formed by our proposed saliency detection model with incorporating low and high level feature and Shotton’s semantic texton forests (STFs) method. Second, we also propose a new HSLT model in terms of the sparse regional semantic information to automatically build a semantic image hierarchy, which explicitly encodes a general to specific image relationship. And last, we archived image dataset using image hierarchical semantic, which is help to improve the performance of image organizing and browsing. Extension experimental results showed that the use of semantic hierarchies as a hierarchical organizing framework provides a better image annotation and organization, improves the accuracy and reduces human’s effort.     

Multi-agent based simulations using fast multipole method: application to large scale simulations of flocking dynamical systems

This article introduces a novel approach to increase the performances of multi-agent based simulations. We focus on a particular kind of multi-agent based simulation where a collection of interacting autonomous situated entities evolve in a situated environment. Our approach combines the fast multipole method coming from computational physics with agent-based microscopic simulations. The aim is to speed up the execution of a multi-agent based simulation while controlling the precision of the associated approximation. This approach may be considered as the first step of a larger effort aiming at designing a generic kernel to support efficient large-scale multi-agent based simulations. This approach is illustrated in this paper by the simulation of large scale flocking dynamical systems.     

Decentralised control for formation reorganisation of multi-agent systems using a virtual leader

In this article, we study the topology reorganisation of formations for multi-agent systems with a broken agent during motion. The cases with a broken agent in different topologies and different positions are studied, and a decentralised algorithm is proposed to reorganise the different damaged topologies of formations. The main contributions of this article include: first, a collective potential function model is designed to reorganise the topologies, and a repulsive potential function model is proposed to avoid obstacles; second, a decentralised algorithm based on potential functions is presented; third, a virtual agent is designed to be a leader as soon as an agent is damaged, and disappears once the topology is repaired. Finally, some simulation results are studied to demonstrate the efficiency of the proposed algorithm.     

Decentralised online charging scheduling for large populations of electric vehicles: a cyber-physical system approach

As the number of electric vehicles (EVs) grows, their electricity demands may have significant detrimental impacts on electric power grid when not scheduled properly. In this paper, we model an EV charging system as a cyber-physical system, and design a decentralised online EV charging scheduling algorithm for large populations of EVs, where the EVs can be highly heterogeneous and may join the charging system dynamically. The algorithm couples a clustering-based strategy that dynamically classifies heterogeneous EVs into multiple groups and a sliding-window iterative approach that schedules the charging demand for the EVs in each group in real time. Extensive simulation results demonstrate that our approach provides near-optimal solutions at significantly reduced complexity and communication overhead. It flattens the aggregated load on the power grid and reduces the costs of both the users and the utility.     

Decentralised zero-sum differential game for a class of large-scale interconnected systems via adaptive dynamic programming

In this paper, a novel decentralised differential game strategy for large-scale nonlinear systems with matched interconnections is developed by using adaptive dynamic programming technique. First, the Nash-equilibrium solutions of the corresponding isolated differential game subsystems are found by appropriately redefining the associated cost functions accounting for the bounds of interconnections. Then, the decentralised differential game strategy is established by integrating all the modified Nash-equilibrium solutions of the isolated subsystems to stabilise the overall system. Next, the solutions of Hamilton–Jacobi–Isaaci equations are approximated online by constructing a set of critic neural networks with adaptation law of weights. The stability analysis of each subsystem is provided to show that all the signals in the closed-loop system are guaranteed to be bounded by utilising Lyapunov method. Finally, the effectiveness of the proposed decentralised differential game method is illustrated by a simple example.     

Institutions with a hierarchy of authorities in distributed dynamic environments

A single global authority is not sufficient to regulate heterogenous agents in multiagent systems based on distributed architectures, due to idiosyncratic local situations and to the need to regulate new issues as soon as they arise. On the one hand institutions should be structured as normative systems with a hierarchy of authorities able to cope with the dynamics of local situations, but on the other hand higher authorities should be able to delimit the autonomy of lower authorities to issue valid norms. In this paper, we study the interplay of obligations and strong permissions in the context of hierarchies of authorities using input/output logic, because its explicit norm base facilitates reasoning about norm base maintenance, and it covers a variety of conditional obligations and permissions. We combine the logic with constraints, priorities and hierarchies of authorities. In this setting, we observe that Makinson and van der Torre’s notion of prohibition immunity for permissions is no longer sufficient, and we introduce a new notion of permission as exception and a new distinction between static and dynamic norms. We show how strong permissions can dynamically change an institution by adding exceptions to obligations, provide an explicit representation of what is permitted to the subjects of the normative system and allow higher level authorities to limit the power of lower level authorities to change the normative system.