Assignment 1 Multiagent Robotic Systems

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

• Please either upload your solution (in the form of a pdf file) at the elearning
web page, or give a hard copy to the instructor (preferred option).
• Each problem has 10 points.
Problem 1
State a summary of first five lectures, 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
Go to the following youtube link, and watch a TED talk by Dr. Magnus Egerstedt
titled “Swarm robotics – From local rules to global behaviors”.
https://www.youtube.com/watch?v=ULKyXnQ9xWA
Then, write down a one paragraph summary, just highlighting the main point or the
‘take-away’ message of the talk. Be brief and to the point.
Problem 3
In class we saw that an undirected graph G is connected if and only if its Laplacian’s
second smallest eigen value, λ2 is non-zero. Using a similar argument as the one in
class, show that the number of connected components (i.e. connected subgraphs
that are disconnected from each other) is equal to the number of zero eigen values
of the Laplacian.
1
Problem 4
Let the subspace S be
S = span{1}
⊥
,
i.e.,
x ∈ S ⇔ x
T 1 = 0
Show that S is L−invariant, i.e., LS ⊆ S (i.e., Lx ∈ S, ∀ x ∈ S), where L is the
Laplacian of an undirected, connected graph.
Problem 5
K1,6 is a star graph with one central node and six leaf nodes as shown in Fig. 1.
Figure 1: Star graph, K1,6.
Your task is to show that K1,6 can never be an induced subgraph of a ∆-disk proximity graph.
Problem 6
If li,j is the shortest path distance (number of edges one needs to follow) between
vertices vi and vj
, the diameter of the graph is defined as
diam(G) = max
vi
,vj∈V
li,j
Similarly, if we let l
∗
i
(known as the eccentricity of vertex vi) be the longest distance
to any vertex from the vertex vi
, i.e.,
l
∗
i = max
vj∈V
li,j
then the radius of a graph is defined as
radius(G) = min
vi∈V
l
∗
i
Find the radius and diameter of the following graphs.
2
G1 G2 G3
Figure 2:
Problem 7
Following are some undirected networks on four nodes with the same initial positions.
In which of these networks, nodes converge fastest under the distributed consensus
dynamics? Explain your answer.
(a) (b) (c) (d)
Figure 3:
Problem 8
What is the necessary and sufficient condition for the consensus to happen in the
case of static directed networks? Derive this condition.
3