Tuesday, 10 June 2014
Thursday, 5 June 2014
Some definitions used in graphs
A walk : Sequence of vertices and edges v_i and e_i such that for 1 <= i <= k, the edge e_i has endpoints v_(i-1) and v_i.
The length of a walk is the number of edges in it.
A trail is a walk with no repeated edges.
A path is a walk with no repeated vertex.
fact - path be a trail, but path may or may not be a trial.
The distance d(u,v) between vertices u and v equals the shortest length of a u,v path.
A circuit is a closed trail.
A cycle is a closed path.
A graph is connected if any two of its vertices are joined by a path.
A tree is an undirected graph in which any two vertices are connected by exactly one simple path.
The length of a walk is the number of edges in it.
A trail is a walk with no repeated edges.
A path is a walk with no repeated vertex.
fact - path be a trail, but path may or may not be a trial.
The distance d(u,v) between vertices u and v equals the shortest length of a u,v path.
A circuit is a closed trail.
A cycle is a closed path.
A graph is connected if any two of its vertices are joined by a path.
A tree is an undirected graph in which any two vertices are connected by exactly one simple path.
Tuesday, 3 June 2014
Laplacian matrix of a graph
The incidence matrix of an oriented graph -
Orientation of a graph X is the assignment of direction to each edge.
An arc of a graph is an ordered pair of adjacent vertices.
Formal definition -
An orientation of X can be defined as a function sigma from the arcs of X to {-1,1} such that, if (u,v) is an arc, then sigma(u,v) = -sigma(v,u).
Let D be the incidence matrix of the graph X.
The laplacian of X is the matrix Q(X) = D*D'
Laplacian does not depend on the orientation.
Q is symmetric => its eigen values are real.
Its positive semidefinite => evas are all non-negative.
TREES - The number of spanning trees is determined by the laplacian.
[Spanning tree - The spanning tree of a connected undirected graph G is a tree that includes all the vertices and some or all of the edges of G.]
Let e = uv be an edge of X.
The graph obtained by deleting the edge e is denoted by X \ e. Its edge set is denoted by E(X) \ e.
Vertex set remains the same.
contracting the edge e => X / e.
Orientation of a graph X is the assignment of direction to each edge.
An arc of a graph is an ordered pair of adjacent vertices.
Formal definition -
An orientation of X can be defined as a function sigma from the arcs of X to {-1,1} such that, if (u,v) is an arc, then sigma(u,v) = -sigma(v,u).
Let D be the incidence matrix of the graph X.
The laplacian of X is the matrix Q(X) = D*D'
Laplacian does not depend on the orientation.
Q is symmetric => its eigen values are real.
Its positive semidefinite => evas are all non-negative.
TREES - The number of spanning trees is determined by the laplacian.
[Spanning tree - The spanning tree of a connected undirected graph G is a tree that includes all the vertices and some or all of the edges of G.]
Let e = uv be an edge of X.
The graph obtained by deleting the edge e is denoted by X \ e. Its edge set is denoted by E(X) \ e.
Vertex set remains the same.
contracting the edge e => X / e.
Consensus algorithms. part II
Consensus - when the individuals agree on the value of a variable of interest, they are said to have reached consensus.
To achieve consensus, there must be a shared variable of interest, called the information state, as well and consensus algorithms for negotiating to reach consensus on the information state.
Examples of information state - local representation of the center and shape of a formation, the rendezvous time, the length of a perimeter to be monitored, the direction of motion for a multivehicle swarm and the probability that a military target has been destroyed.
By necessity, consensus algorithms assume only neighbor to neighbor interaction between vehicles.
Fundamental Consensus algorithms. -
Basic idea - impose similar dynamics on the information states of each vehicle.
Information state update is modeled using a differential equation or difference equation depending on type of communication.
To achieve consensus, there must be a shared variable of interest, called the information state, as well and consensus algorithms for negotiating to reach consensus on the information state.
Examples of information state - local representation of the center and shape of a formation, the rendezvous time, the length of a perimeter to be monitored, the direction of motion for a multivehicle swarm and the probability that a military target has been destroyed.
By necessity, consensus algorithms assume only neighbor to neighbor interaction between vehicles.
Fundamental Consensus algorithms. -
Basic idea - impose similar dynamics on the information states of each vehicle.
Information state update is modeled using a differential equation or difference equation depending on type of communication.
Monday, 2 June 2014
Consensus algorithm algorithms in cooperative control. Part I
Motivation for cooperative control -
greater efficiency and operational capability than autonomous vehicles on solo missions.
Applications - space based interferometers, combat, surveillance and reconnaissance systems, hazardous material handling, distributed reconfigurable sensor networks.
Concepts in cooperative control -
Formation control, rendezvous, attitude alignment, flocking, foraging, task and role assignment, payload transport, air traffic control and cooperative search.
Challenges -
1. develop a system of subsystems rather than single system.
2. The communication bandwidth and connectivity of the team. - unreliable channels, what, when and whom to communicate with.
3. team goals and individual goals should be negotiated.
4. Limited computational resources in each individual vehicle.
Common assumptions done -
1. availability of global team knowledge.
2. ability to plan group actions in a centralized manner.
3. proper communication among the individuals.
Axiom - Shared information is a necessary condition for cooperation.
Information exchange is the central issue in cooperative control.
Coordination information/ coordination variable - the information that is necessary for cooperation.
The objective is to determine algorithms that can ensure the convergence of the coordination variable to pre-specified values in presence of
1. imperfect sensors.
2. communication dropout.
3.sparse communication topologies.
4.noisy and unreliable communication links.
greater efficiency and operational capability than autonomous vehicles on solo missions.
Applications - space based interferometers, combat, surveillance and reconnaissance systems, hazardous material handling, distributed reconfigurable sensor networks.
Concepts in cooperative control -
Formation control, rendezvous, attitude alignment, flocking, foraging, task and role assignment, payload transport, air traffic control and cooperative search.
Challenges -
1. develop a system of subsystems rather than single system.
2. The communication bandwidth and connectivity of the team. - unreliable channels, what, when and whom to communicate with.
3. team goals and individual goals should be negotiated.
4. Limited computational resources in each individual vehicle.
Common assumptions done -
1. availability of global team knowledge.
2. ability to plan group actions in a centralized manner.
3. proper communication among the individuals.
Axiom - Shared information is a necessary condition for cooperation.
Information exchange is the central issue in cooperative control.
Coordination information/ coordination variable - the information that is necessary for cooperation.
The objective is to determine algorithms that can ensure the convergence of the coordination variable to pre-specified values in presence of
1. imperfect sensors.
2. communication dropout.
3.sparse communication topologies.
4.noisy and unreliable communication links.
Subscribe to:
Posts (Atom)