Università di Modena e Reggio Emilia

Agent Group
Università
di Modena
e Reggio
Emilia
Theory and Practice of Fieldbased Motion Coordination in
Multi-Agent Systems
Marco Mamei, Franco Zambonelli
DISMI – Università di Modena e Reggio Emilia – ITALY
{ mamei.marco, franco.zambonelli }@unimo.it
Università
di Modena
e Reggio
Emilia
Background and Motivations
 Main challenge in open and dynamic application scenario is the
need for robustness despite environment dynamism.
 With this regard the Autonomous Agent approach is promising,
in that it promotes a shift from design-time interaction patterns
to run-time interaction patterns.
Agent Group
 To shape these interaction patterns, agents need to be context-
aware. An agent can meaningfully interact and coordinate with
other agents only if it is aware of “what is around”.
 …However, current systems focus mainly in providing general-
purpose contextual information and almost disregard how to use
the information.
– E.g. Pub/sub models
Università
di Modena
e Reggio
Emilia
What we are looking for…

On the contrary, enabling adaptive and costeffective coordination requires minimizing: agents’
efforts in acquiring AND exploiting contextual
information.
–
Agent Group
–

In most situations human agents want to act - they do not
want to study large context info.
In most situations software agents cannot be provided with
enough AI to effectively understand large context info.
Special purpose contextual information: .
–
–
(CONS) context information cannot easily be re-used in
several applications.
(PRO) easy to decide what to do
Agent Group
Università
di Modena
e Reggio
Emilia
Our Domain and Follow Though
Case Study…
 Coordinating mobility in Pervasive Computing Scenarios
– Agents have to organize their respective movements
according to some policy
Marco
Marco and
Franco want to
maintain a
formation while
moving in the
building.
Franco
Università
di Modena
e Reggio
Emilia
What we found
Co-Fields
 Special purpose contextual information: a “red
carpet” leading to the right location.
 Field based motion coordination
Agent Group
– The Flocking-Formation Problem
Theory of Field Approach…
Università
di Modena
e Reggio
Emilia
 Agents are seen as balls
Agent Group
rolling on a surface…
dynamical system
formalism.
 Differential Equations
coord i ( X 1 , X 2 ,..., X n , t )
 v 
dt
X j
dx j
Integrate …
Agent Group
Università
di Modena
e Reggio
Emilia
From Theory to Practice…
Tuples On The Air
 The TOTA Middleware
– P2P Network, where each peer runs a local
version of the TOTA middleware
 Distributed tuples injected and spread in
the network implement the concept of
field.
– T=(C,P)
 TOTA maintains tuples’ shape despite
network dynamics
Università
di Modena
e Reggio
Emilia
Flocking Example
1
2
0
0
1
1
0
0
Agent Group
1
0
2
1
Px
1
Marco creates a flock
field having a
minimum at two hop
distance
1
0
0
Università
di Modena
e Reggio
Emilia
Flocking Example
0
1
1
1
2
0
1
1
Agent Group
2
0
2
Px
0
1
1
2
2
Università
di Modena
e Reggio
Emilia
Flocking Example
0
1
2
1
1
2
2
0
Px
Agent Group
3
3
1
1
2
0
3
2
Università
di Modena
e Reggio
Emilia
Flocking Example
3
0
1
2
1
1
2
2
0
Px
Agent Group
3
3
1
1
2
0
3
2
Università
di Modena
e Reggio
Emilia
Flocking Example
0
1
2
1
1
2
2
0
Px
Agent Group
3
2
1
1
2
0
3
2
3
Università
di Modena
e Reggio
Emilia
Flocking Example
0
1
2
1
0
3
1
2
2
Px
Agent Group
0
1
1
2
0
3
2
3
Università
di Modena
e Reggio
Emilia
Flocking Example
1
0
0
0
0
1
1
0
0
Px
Agent Group
2
1
0
0
1
1
1
1
Agent Group
Università
di Modena
e Reggio
Emilia
Implementation
The same code
installed on
simulated
nodes, runs also
on the IPAQ
Università
di Modena
e Reggio
Emilia
Programming TOTA Applications
 Programming the agents
Agent Group
 Programming the tuples
TOTA API
Agent Group
Università
di Modena
e Reggio
Emilia
void
inject (TotaTuple tuple);
Vector
read (Tuple template);
Vector
readOneHop (Tuple template);
Tuple
keyrd (Tuple template);
Vector
keyrdOneHop (Tuple template);
Vector
delete (Tuple template);
void
subscribe (Tuple template, ReactiveComponent comp, String rct);
void
unsubscribe (Tuple template, ReactiveComponent comp);
void
move (TotaTuple tuple);
void
store (TotaTuple tuple);
Agent Group
Università
di Modena
e Reggio
Emilia
Flocking Agent
public class FlockAgent extends AbstractAgent {
public void run() {
FlockingTuple ft = new FlockingTuple();
ft.content = "flock";
tota.inject(ft);
while(true)
{
FlockingTuple ft = new FlockingTuple();
ft.content = "flock";
Vector pv = tota.readOneHop(ft);
/* get minimum */
Peer min = getDownhill(pv);
if(min == null)
return;
Very Simple:
Agents are balls
/* get min coordinates...*/
GenPoint target = min.getCoordinates();
just rolling
if(target == null)
upon the field
return;
surface…
this.move(target);
}
}
Università
di Modena
e Reggio
Emilia
Programming TOTA Applications
 Programming the agents
Agent Group
 Programming the tuples
Università
di Modena
e Reggio
Emilia
TOTA Tuples
TotaTuple
Agent Group
StructureTuple
MessageTuple
HopTuple
MetricTuple
SpaceTuple
Università
di Modena
e Reggio
Emilia
Tuple Programming
public final void propagate() {
if(decideEnter()) {
boolean prop = decidePropagate();
changeTupleContent();
Agent Group
makeSubscriptions();
tota.store(this);
if(prop)
tota.move(this);
}
}
Agent Group
Università
di Modena
e Reggio
Emilia
Flocking Tuple
public class FlockingTuple extends HopTuple
{
public int value = 2;
protected void changeTupleContent()
{
super.changeTupleContent();
if(hop <= 2) value --;
else if(hop >2) value ++;
}
}
Università
di Modena
e Reggio
Emilia
From Practice to Experiment
 Tuples must be propagated and maintained.
 Propagation is based on a simple hop-by-hop
epidemic mechanism.
 We developed an algorithm to maintain the tuples
locally…
Agent Group
3
1
2
A
B
C
4
5
6
7
E
F
G
H
D
3
4
 What happens is realistic scenarios?
Agent Group
Università
di Modena
e Reggio
Emilia
Experiment I
 Inject a tuple
 Change the topology and record the
number of messages sent to update the
tuple distributed shape.
 Evaluate the average number of
messages exchanged by peers
0,1,2,3,… hop away from the topology
change.
 Average these numbers over a large set
of experiments
Results
Università
di Modena
e Reggio
Emilia
1,6
0,6
avg. density = 5.7;
avg. diameter = 15.1
avg. density = 7.2;
avg. diameter = 14.8
avg. density = 8.8;
avg. diameter = 12.7
0,4
0,3
1,2
avg. # messages sent
avg. # messages sent
Agent Group
0,5
avg. density = 5.7;
avg. diameter = 15.1
avg. density = 7.2;
avg. diameter = 14.8
avg. density = 8.8;
avg. diameter = 12.7
1,4
0,2
1
0,8
Locality scopes emerge in a
network without predefined
boundaries.
0,6
Network topology changes do
not affect far nodes, but tend
to remain confined
0,4
0,1
0,2
…sign of scalability
0
0
0
1
2
3
4
5
# hops from topology change
6
7
8
0
1
2
3
4
5
# hops from topology change
6
7
8
Università
di Modena
e Reggio
Emilia
Other Already Implemented
Applications
 More motion coordination
 Routing in MANET
Agent Group
 Location based access to information
 Content based routing (DHT)
 Modular Robot Control Algorithms
Università
di Modena
e Reggio
Emilia
On Going and Future Directions
 Conduct other experiments on performances
 Develop more applications, trying to move
beyond motion coordination
Agent Group
 Develop global programming languages and
compiler to automatically obtain single agents
code:
– Amorphous Computer (MIT) or Spatial
Programming (Rutgers Univ.)
Università
di Modena
e Reggio
Emilia
Further Info
Agent Group
http://agentgroup.ing.unimo.it