1 Leader-to-Formation Stability
Herbert G.Tanner George J.Pappas Vijay Kumar
Abstract—We investigate the stability for robot formations from a different perspective,focusing on the dependence of group con-figuration to incoming input singals or disturbances.Our idea builds on the notion of input-to-state stability to define leader-to-formation stability(LFS),as a means to analyze error propagation and performance characterization.Contrary to other notions of stability for interconnected systems,in leader-to-formation stabil-ity the focus is shifted from disturbance rejection to quantifying transient and steady state behaviour,thus being able to relax con-ditions,address a larger class of systems and provide insight to issues of performance improvement in relation to interconnection topology.The new concepts are implemented numerically in the ca of a formation of mobile robots where(LFS)also indicates the formation structures that ensure the smallest errors during maneuvering.
I.I NTRODUCTION
Interconnected systems have lately received considerable at-tention,motivated by recent advances in computation and com-munication,which provide the enabling technology for appli-cations such as automated highway systems[1],cooperative robot reconnaissance[2],[3]and manipulation[4],[5],forma-ti
onflight control[6],[7],satellite clustering[8]and control of groups of unmanned vehicles[9],[10],[6].Formation control is one aspect of the study of a patricular class of interconnected systems.
One rearch thrust aims at network architectures and coor-dination methods as a means of generating a group behavior in a formation of vehicles.In behavior-bad approaches[2], [11],[12]the group behavior emerges as a combination of group member behaviors,lected among a t of primitive ac-tions.Agent behavior has alternatively been designed so that the group members move as being particles in a rigid virtual structure[13].Similar ideas have been combined with potential field-like controllers for multi agent control[14],[4],[15],and decentralized formation forming[16].The leader-follower ap-proach[17],[18],[19]distinguishes a designated group leader which the other agents follow either directly or indirectly. Another rearch direction focus on the stability of the in-terconnected system.In[20]a distributed control scheme is designed for spatially interconnected systems that is shown to inherit the same topological structure with the target system. String stability[21],[22],[1]and mesh stability[23],the latter Herbert Tanner is with the Department of Electrical and Systems Engineer-ing,3401Walnut Street,Suite301C,University of Pennsylvania,Philadelphia, PA19104-6228(e-mail:tanner@grasp.cis.upenn.edu)
George Pappas is with the Department of Electrical and Systems Engineering, 200South33rd Street,
University of Pennsylvania,Philadelphia,PA19104(e-mail:pappasg@ee.upenn.edu)
Vijay Kumar is with the Department of Mechanical Engineering and Ap-plied Mechanics,3401Walnut Street,Suite301C,University of Pennsylvania, Philadelphia,PA19104-6228,(e-mail:kumar@grasp.cis.upenn.edu)being the generalization of the former in more than two dimen-
sions,express the property of the system to attenuate distur-bances as they propagate through the interconnections.While
earlier works[24],[21],[22],[25]have ud the notion of string stability in the frequency domain,string stability of in-terconnected systems has recently been studied in a state space
framework[1].In[1],sufficient conditions for string stability were derived,requiring global Lipschitz continuity of vector fields and exponential stability of the unconnected subsystems.
Weaker notions of string stability include string stability [1],which is the only type of stability that can be guaranteed for an interconnected system without a special structure.It is
拉杆箱十大排名
also known that in certain cas string stability is impossible [26],[25],[22].
The class of formations discusd in this paper generally do
not fall under the class of string stable interconnected systems. On the other hand,it is generally the ca that formations are stable at least locally,in the n that local controllers can en-sure some boundedness of errors.A question then aris as to whether further stability analysis can be performed to address issues such as boundedness of propagating errors and perfor-mance characterization.This question motivates the introduc-tion of a different framework,that brings forward the depen-dence of the internal state of an interconnected system to in-coming input signals or disturbances,rather than ensuring con-vergence of signals to zero.
In this paper we define Leader-to-Formation Stability(LFS), a different notion of stability for leader-following formations, and we u it to characterize how the motion of the group lead-ers can affect the motion of the group.This notion is bad on input-to-state stability[27]and its propagation properties through certain interconnections[28],[29].In previous work [30],[31],[32]we have been able to characterize the effect of the behavior of the group leaders to the rest of the group for cer-tain types of formation interconnections and obtain quantitative measures of the stability of the formation with respect to the motion of the leaders.In this paper we generalize the results and exploit LFS for analysis and design of robot formations.
II.D EFINITIONS AND P RELIMINARY R EMARKS
We consider formations that are bad on leader-follower ar-chitectures.In that framework,a formation will be broadly de-fined as a network of vehicles interconnected through their con-trollers,with the latter being designed so that the motion of the vehicles meet certain specifications.In the formations consid-ered,a number of vehicles are identified as designated leaders in the n that their motion is not constrained by the forma-tion specifications.Related work[6],[17],[18],[33],[34]has motivated the u of graphs to reprent agent interaction.We
2
therefore briefly introduce some notions from graph theory[35]
that will facilitate our analysis.
A.Graph Theory Preliminaries
A directed graph consists of a vertex t and an di-rected edge t,where a directed edge is an ordered pair
of distinct vertices.A vertex is incident with an edge if it is one of the two vertices of the edge.An edge in a directed graph is said to be incoming with respect to and outcoming
with respect to.Such an edge has vertex as a tail and vertex as a head.The indegree of a vertex in a directed graph is de-fined as the number of edges that have this vertex as a head.A
subgraph of a graph is a graph such that
and.A subgraph of is an induced sub-
graph if two vertices of are adjacent in if and only they are adjacent in.A path of length in a directed graph is a quence of distinct vertices such that for every ,.A weak path is a quence
of distinct vertices such that for each either or is an edge in.A directed graph is weakly connected or simply connected if any two vertices can be joined with a weak path.The distance between two vertices and in a graph is the length of the shortest path from to .The diameter of a graph is the maximum distance between two distinct vertices.A(directed)cycle is a connected graph where every vertex is incident with one incoming and one out-coming edge.An acyclic graph is a graph with no cycles.The incidence matrix of an oriented graph with vertices and edges(assuming some enumeration on the edge t)is an matrix,the of which is if is the head of edge,if it is the tail and otherwi.
B.Formation Graphs
A formation is generally described in terms of its shape. We have en,for example,‘line’,‘column’,‘diamond’and ‘wedge’formations[2],[9].This is a global geometric descrip-tion of a formation as oppod to the particular interconnection structure that the control designer has chon to implement this geometry.We will refer to this geometric formation description using the term shape.In this paper we will consider formations that are bad on leader-following.In this ca shape can be defined as follows:
Definition II.1.The shape of a formation of robots with leaders moving in is a point in a-dimensional submanifold of.
Broadly speaking,the shape will be a point in a hyper-surface of the total dimensional state space,defined after imposing constraints related to the position of the formation leaders.The desired shape,,is a particular region in that hypersurface.In the ca where can be locally parame-terized as a point then the shape error is simply given by the Euclidean distance1:
一年级下册英语The choice of an appropriate metric for describing shape in SE(3)is a dif-ferent important issue[36],and will not be discusd in this paper.The agent interconnections can then be designed to implement
the desired shape.The type of agent interconnections consid-ered are leader-following relationships,which we cho to rep-rent by means of a graph.The leader-follower architecture
dictates an orientation on this graph.
The formation will be associated with and identified by a di-
rected graph that reprents both its shape and the control spec-ifications that realize it.
飞镖怎么叠Definition II.2(Formation Control Graph).A formation control graph is a directed graph with: Afinite t of vertices and a map as-signing to each vertex a control system
where and.
An edge t encoding leader-follower rela-tionships between agents.The ordered pair
belongs to if depends on the state of agent,.
A collection of edge specifications,defining
control objectives(tpoints)for each
for some.The specifications,implement a certain desired shape for the formation.
According to Definition II.2,each vertex reprents the dy-
namics of a particular robot.For robot,the tails of all incom-ing edges to vertex reprent leaders of,their t denoted by .Robot is controlled so as to meet the specifications for all.Similarly,we can define the t of im-mediate followers of agent as the heads of all edges having as tail.Vertices of indegree zero,reprent formation leaders, denoted by.For the formation leaders in no specification is prescribed with respect to other agents.In-stead,formation leaders aim at achieving group objectives such as following a reference trajectory or navigating within an ob-stacle populated environment.
In the prent analysis,the formations control graphs consid-ered are acyclic.The ca of cycles within a formation graph is considered elwhere[30].The primary reason for this assump-tion is that a cycle may not always be stable[37]and stability analysis will involve the u of versions of the small gain theo-rem[30].
Formation specifications capture shape information.The for-mation shape can specified with respect to some common ref-erence frames,which can be assumed to be the local frames of the formation le
aders:
Formation specifications are defined in terms of a desired shape vector.If is the desired shape component corresponding to agent,then the desired state for will be expresd as,where can be the state of any formation leader.
Edges,on the other hand,express possible ways to realize a desired shape.The t of possible edges can be restricted due to nsing and/or communication constraints.Given a t of possible edges,one can decompo the formation specifications to individual edge specifications as follows:
(1)
3 where is the incidence matrix of the formation control graph
and denotes the Kronecker matrix product[38].If the t
of edges can realize the desired shape,then the left hand side
of(1)will be independent of the formation leaders states.For
agents with multiple leaders,on the other hand,there will be a
degree of redundancy in their incoming edges specifications.
With the specification for edge being cal-
culated using(1),a tpoint for agent can be expresd as
follows:
For agents with multiple leaders,the specification redundancy
can be resolved by projecting the incoming edges specifications
into orthogonal components:
(2)
where are projection matrices with.
Then the error for the clod loop system of robot can be
defined as the deviation from the prescribed tpoint:
Since there are no edge specifications for the formation leaders,
errors for the leaders are defined with respect to some overall
‘high level’formation objective.Such an objective could be,
for example,tracking of a reference trajectory.In general,the
clod loop system for any leader would take the form:
where is(asymtptotically)stable and is an ex-
ogenous input signal related to this formation objective.Alter-
natively,can be viewed as a disturbance affecting the clod
loop leader dynamics.The formation error is defined as the
deviation of the formation shape from the desired:
4
to which the formation is viewed as a nonlinear operator from the space of leader input/disturbances to the space of the for-
mation internal state.LFS express the dependence of the for-
mation shape on the input signals given to the leaders.Inequal-ity(3)provides a‘nonlinear gain estimate’through functions and,taking into account the initial conditions.In-tuitively,a formation control scheme bad on local controllers
would be able to stabilize interconnection errors if the reference
白底头像signals nt to the leaders are t to zero.On the other hand,a high speed maneuver from the part of
the leaders in respon to a reference input signal is expected to have adver effects on the stability of the followers.
It is known[41],[28]that certain interconnections of ISS
systems prerve the ISS property.As indicated by our pre-vious work[32],[30],certain formation interconnections pre-rve ISS and therefore it would be straightforward to estab-lish Leader-to-Formation Stability.In this paper we general-ized the results to arbitrary interconnections of leaders and followers conforming with the conditions of Definition II.2. Bad on alternative characterizations of input-to-state sta-bility,Definition II.3implies the following:
Corollary II.4.If a formation is LFS,in the n of Definition II.3,then the formation error satisfies:
Corollary II.4reveals that the steady state LFS gain rves as an ultimate bound for the formation error.This motivates the definition of the following LFS measure:
Definition II.5.Consider a formation that is LFS.Then the scalar quantity:
is called the LFS performance measure for the formation.
The LFS measure can be thought of as a radius of the ball in which the steady state formation error will remain,when the inputs to the formation leaders are bounded inside unit balls.
III.LFS P ROPAGATION
Fig.2.A generic formation control graph structure.
Any induced formation control subgraph of depth two has the structure depicted in Figure2.For simplicity,assume an enumeration of the induced formation control graph where the leaders(depth zero)are assigned the numbers,agents at depth one are assigned the numbers and the followers at depth two are assigned the numbers. Let the dynamics of the agents be expresd as follows:
(4a)
咬牙切齿(4b)
(4c)
The agents are driven by control laws of the form:
(5a)
(5b)
(5c)
resulting in clod loop error dynamics which can be written as:
小品剧本(6a)
(6b)
(6c)
The main result of the paper is bad on the invariance of the LFS property under cascading and draws from well known results on ISS:
Lemma III.1([28]).Suppo that in the system:
the subsystem is ISS with respect to and,and the-subsystem is ISS with respect to,that is,
where and are class functions and and are class functions.Then the complete-system is ISS with:
咏梅陆游where
5 and(6c)is LFS with respect to:
then the induced formation control graph is LFS with respect to :
with and
(7a)
(7b) Proof.See Appendix.
经验宝宝In the ca where the agent dynamics are linear,then LFS does not require specific assumptions on the agent dynamics. Moreover,one can obtain much less conrvative results than tho derived by direct application of(7),by exploiting the lin-ear structure.Application of the feedback control laws
(8a)
(8b)
(8c) where,,and are such that,
are Hurwitz,and,and satisfy:
results in clod loop error dynamics that can be written as:
(9a)
(9b)
(9c) This model is equivalent to the one ud for a string of LTI systems in[42].In this ca,the LFS gains are given as follows: Proposition III.3.Consider the formation of Figure2where the clod loop error dynamics of the agents are given by(9). Then,(9)is LFS with respect to:
where a parameter,
,and each satisfying:
Proof.See Appendix.
We conclude this ction with an analytical justification of the intuitive fact that the larger the diameter of a formation control graph,the larger the amplification of leader perturba-tions,unless the formation is string stable[1].Using(10)we can calculate the input LFS gain of a string of vehicles,which for simplicity it is assumed to be described by linear dynamics. Figures3-4depict the change in the LFS performance measure of the formation as more vehicles are considered in the string. In Figure3,the LFS input gain of the leader-follower pair is small enough to make errors attenuate and maintain stability. The performance measure approaches a steady state value.On the contrary,if the LFS input gain of the leader-follower pair is such that allows significant error propagation the formation performance measure deteriorates rapidly(note the logarithmic
allows the string to be augmented without performance degradation.
IV.T HE E FFECT OF F EEDFORWARD I NFORMATION The results of Section III assumed for each agent feedback information from its leaders.The u of local information al-lows the construction of decentralized control schemes which are generally scalable and robust.As it could be expected, however,utilization of additional information could possibly enhance the performance of the formation[32],although this is not necessarily the ca[33].This ction prents ways in which such additional information can be ud to improve the LFS performance characteristics of a formation. Information obtained by some agents may have more signifi-cant effect to the stability of a particular leader-follower dynam-ics than from others.One way to improve the stability charac-teristics of some leader-follower dynamics is to u feedforward
6
measure implies error amplification.
information from the pair leader,denoted by the head of a par-
ticular edge:
Corollary IV.1.Assume that in system(4),for some
control law a control law can
render(6c)asymptotically stable.Then,for the leader-
follower pair,.
Proof.The result is a conquence of the fact that if(6c)is
asymptotically stable,then there will be a class-function
such that for the edge error,.
It follows that the pair is LFS with.
For the linear ca,the result requires only a rank condition:
Corollary IV.2.Assume that in(9)for some,
is full column rank.Then the control law
where yields.
Proof.Since is full column rank,it has a left inver and
therefore one canfind a satisfying
.Then for the clod loop error dynamics of:
and since is stable,
Let.Then for(12)with
,the Lyapunov function will satisfy:
