Assignment 5 Multiagent Robotic Systems

Assignment 5
(SYSM 6v80.001 / MECH 6v29.001 – Multiagent Robotic Systems)

Problem 1 10 points
State a summary of Notes 16.1–17.4, (which include the topics of lloyd’s algorithm, network controllability (upper and lower bounds)) preferably by creating a
concept map diagram (flow diagram). The whole purpose is to make sure that we are
clear about the bigger picture, and reiterate why are we doing and discussing the
specific topics in the class. Do not merely write the topics, instead create connections
between topics to clarify the flow of information.
Problem 2 10 points
Consider the graph in Figure 1, and the following statement:
“Three leader nodes are sufficient to make the graph completely controllable.”
Using the zero forcing method (Notes 17.3), discuss if the statement is true or false? If
it is true, find a set of three leader nodes making the network completely controllable
and justify your choice. If the statement is false, discuss why?
Figure 1: Caption
Problem 3 20 points
(Each part has 5 pints.)
(A) Consider the graph in Figure 2. Let VL = {v4, v5} be a leader set. Using zero
forcing method, what is the minimum rank of the controllability matrix?
1
(B) Consider a graph with unity edge weights and VL ⊂ V be a zero forcing set of
the graph. If we change the edge weights from unity to arbitrary positive values,
what would be the rank of the controllability matrix with the same set of leaders
VL? Please explain your answer.
(C) Can you find a set of three leaders through which the graph in Figure 2 becomes
completely controllable? If yes, which three nodes can be leaders?
(D) This part is about finding the worst leaders from the perspective of zero forcing
method. Can you identify two different sets of leader nodes, each of which containing
four nodes, such that the zero forcing based bound on the rank of the controllability
matrix is four with each of those leader sets.
v4 v5
v8 v1
v9
v6 v3
v7
v2
Figure 2: Graph for Problem 3.
Problem 4 10 points
In Problem 3(A), you computed the zero forcing based controllability bound for VL =
{v4, v5}. Now compute the distance-based bound on the rank of the controllability
matrix (as we discussed in the class and also explained in Notes 17.4). Which one
is a better bound here?
Problem 5 10 points
(Each part has 5 points.)
Consider the graph in Figure 3, in which only black node is a leader node.
Part - A How many external equitable partitions (EEP) does the graph have? Which
of these EEPs is the maximal leader-invariant (LIEEP), and based on that comment
if the system is completely controllable or not.
2
Part - B Now consider that both black and gray nodes are leaders, and repeat
the same as in Part A.
Figure 3: A leader-follower network in Problem 2.
Problem 6 10 points
Let G be a leader-follower network with a single leader ℓG. Similarly, H is another
leader follower network with a single leader ℓH and n follower nodes. Now we obtain
a new graph M by connecting H and n copies of G as follows: Connect a copy of G
to H by replacing a follower node i in H by the leader node ℓG in G. See Figure 4
for the example.
G H
`G `H
M
`M
Figure 4: Construction of M in Problem 3.
Either prove or disprove (by giving a counter example) the following statement:
“If G and H has trivial maximal LIEEPs, then M also has a trivial
maximal LIEEP”
(Recall that trivial maximal LIEEP means that each node in the graph is in a
singleton cell.)
3