Assignment 4 Multiagent Robotic Systems

Assignment 4
(SYSM 6v80.001 / MECH 6v29.001 – Multiagent Robotic Systems)
Problem 1 10 points
State a summary of Notes 13–15, (which include the topics of persistence, combinatorial coverage and graph grammars) 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
We studied a way to assign edge directions in a minimally rigid graph to make them
constraint consistent, and hence, minimally persistent. Assign orientations to edges
in the following graphs to make them persistent. Show all the steps of the Henneberg
construction.
G1 G2
Figure 1: Minimally rigid graphs for Problem 2.
Problem 3 10 points
We have discussed that for a directed graph Gd to be minimally persistent, it must
satisfy the following two conditions: (a) The corresponding undirected graph G
must be minimally rigid, and (b) the direction of edges must make Gd constraint
consistent. Moreover, We have seen how to achieve minimally rigid (undirected)
1
graphs using Henneberg construction rules and then assign them directions to make
them constraint consistent. Now, your job is to solve the following problem (for the
d = 2-dimensional case).
For any odd integer N, provide an algorithm/method to construct directed graphs
that are
1. minimally persistent, and
2. balanced at the same time.
Please also illustrate your method through example(s). (Recall that balanced graph
is the one where in-degree = out-degree for every node.)
Problem 4 10 points
Draw a Gabriel graph induced by the following set of 14 points. The coordinates of
points are:
P =
"
1 2 3 4 5 6 7 8 9 10 11 12 13 14
9 7 14 9 12 6 6 12 1 1 2 5 12 12 #
Figure 2:
Problem 5 15 points
Part a: Show that Gabriel graphs are planar.
Part b: Show that Gabriel graphs are connected.
2
Problem 6 10 points
Graph grammars are a good tool for generating networks with some specific structure. Assume that we have a total of 2n nodes for some positive integer n. Consider
the following rules:
R0 : a a −→ ℓ1 c
R1 : ℓi ℓi −→ ℓi+1 c ; 1 ≤ i ≤ n − 1
What structure do we get at the end? (Later in the course, we will see that the graph
obtained by such graph grammars are completely controllable with only a single
leader. So, we can also use graph grammars to generate controllable networks).
Problem 7 15 points
Consider the three graph grammars in Figure 3. Assume that initially all agents are
labelled α. What is the final product expected after applying these graph grammars.
Figure 3: Graph grammars for Problem 7.
3