=Paper=
{{Paper
|id=None
|storemode=property
|title=Design and Implementation of a NetLogo Interface for the Stand-Alone FYPA System
|pdfUrl=https://ceur-ws.org/Vol-741/ID10_Briola_Mascardi.pdf
|volume=Vol-741
|dblpUrl=https://dblp.org/rec/conf/woa/BriolaM11
}}
==Design and Implementation of a NetLogo Interface for the Stand-Alone FYPA System==
https://ceur-ws.org/Vol-741/ID10_Briola_Mascardi.pdf
Design and Implementation of a NetLogo Interface
for the Stand-Alone FYPA System
Daniela Briola and Viviana Mascardi
Dipartimento di Informatica e Scienze dell’Informazione (DISI)
Università degli Studi di Genova
Email: {briola, mascardi}@disi.unige.it
Abstract—FYPA (Find Your Path, Agent!) is a multiagent sys- addressed by FYPA and the proposed solution, and provides
tem currently used by Ansaldo STS for off-line daily computation an evaluation of AnsaFYPA and StandaFYPA performances;
of paths of trains inside stations. Its exploitation for on-line re- Section III provides some background knowledge on NetLogo,
planning in case of unavailability of resources is envisaged in the
very near future, since the system’s performances demonstrated discusses the reasons why we did not implement StandaFYPA
to be suitable for real time usage. in NetLogo, and shows how we used NetLogo for develop-
In this paper we present StandaFYPA, the stand-alone version ing the StandaFYPA graphical interface; Section IV shows
of FYPA that we developed for running batteries of tests on our StandaFYPA at work; finally, Section V outlines some future
own, without needing to access existing Ansaldo applications. directions of research and concludes.
StandaFYPA is equipped with a graphical interface implemented
in NetLogo for off-line visualization, that we describe here in II. S TAND - ALONE FYPA
details.
A. The problem faced by FYPA
I. I NTRODUCTION The abstract problem faced by the FYPA multiagent system
FYPA (Find Your Path, Agent!) [2], [4], [5] is a multiagent has already been described in [2], [4], [5] and consists of
system used by Ansaldo STS, the Italian leader in design and • A set of indivisible resources that must be assigned to
construction of signaling and automation systems for conven- different agents in different time slots (each resource can
tional and high speed railway lines, for solving a resource be used by only one agent in each time slot).
allocation problem by means of distributed negotiation. • A set of agents with different priorities, each needing to
The system is currently used by Ansaldo STS for off-line use some of the available resources for one or more time
computation of paths of trains inside stations, whereas its slots; agents have preferences over the set of resources
on-line application for real-time unavailability management is they can obtain.
foreseen in the very near future. • A directed graph of dependencies among resources: an
The “Ansaldo FYPA” system (AnsaFYPA from now on), agent can start using resource R only if it used exactly
namely the system currently operating in Ansaldo STS centers, one resource from {R1 , R2 , ..., Rn } in the previous time
reads configuration data from a legacy system and send results slot (we represent these dependencies as arcs R1 → R,
to it, using Web Services. In 2009 we started the development R2 → R, ..., Rn → R in the graph).
of a stand-alone version of the system in order to carry • A set of resources named “start points” that can be
out batteries of tests without needing any Ansaldo legacy assigned to agents without requiring the prior usage of
system, whose access from outside Ansaldo was of course other resources (no arc enters in the corresponding node).
not allowed. Hence, we implemented the “Stand-alone FYPA” • A set of resources named “end points” that, once assigned
system (StandaFYPA in the sequel) by reusing as much as to one agent, allow the agent to complete its job (no arc
possible code we already developed for Ansaldo, and by exits from the corresponding node).
implementing the new functionalities we needed for making • A set of couples of conflicting arcs in the graph of
StandaFYPA self-contained. dependencies: an agent releasing R1 for accessing R2 ,
AnsaFYPA and StandaFYPA are different only as far as the where the usage of R2 depends on the previous usage
input/output management is concerned: we changed the type of R1 , might conflict with an agent releasing R3 for
source of input data and we modified the output visualization. accessing R4 . The two agents might indeed need to use
In particular, we added a post-execution simulator to the the same transportation means for accessing R2 from
StandaFYPA system implemented by means of a NetLogo R1 and R4 from R3 respectively, and the transportation
[6] program able to read the output files of the agents and means might be non sharable as well.
to graphically represent the moves of trains (agents) on the • A static allocation plan that assigns resources to agents
railway tracks (resources). for pre-defined time slots, in such a way that no conflicts
The performances of StandaFYPA and its NetLogo interface arise.
are the main subjects of this paper, which is organized in Since agents happen to use resources for longer than
the following way: Section II briefly recalls the problem planned and resources can break up, a dynamic re-allocation
of resources over time is often required. Thus, the solution in few seconds. Ansaldo STS is using AnsaFYPA as a plug-
of the real world problem is a dynamic re-allocation of the in of its commercial application, and uses it to organize the
resources to the agents such that: movements of trains in a station for an entire day. In the sequel
1) the re-allocation is feasible, namely free of conflicts; in we report data of two experiments carried out by Ansaldo STS
our scenario, conflicts may arise both because two or engineers on the field (courtesy of Ansaldo STS).
more agents would want to access the same resource The first station considered during the testing of the
in the same time slot, and because two or more agents AnsaFYPA system was Mestre: this station has 59 Nodo
would want to use conflicting arcs in the same time slot; agents, 528 Treno agents (during day 28th of March 2011)
2) the re-allocation task is completed within a pre-defined and each Nodo agent manages approximately tree entering
amount of time; arcs. The total number of incompatibilities is 430. A simplified
3) each agent minimizes the changes between its new plan representation of Mestre station is shown in Figure 1.
and its static allocation plan: the start and end point must The simulation carried out by Ansaldo STS engineers
always remain those stated in the static allocation plan, took 18 minutes to be completed. This time is also due
but the nodes in between may change, as well as the to the scheduling chosen by the Ansaldo STS system: the
time slots during which resources are used; User Agents Manager creates a new train every 2 seconds,
4) each agent minimizes the delay in which it reaches the so the simulation time is at least equal to the number of
end point with respect to its static allocation plan; trains multiplied for 2 seconds: in this example, at least 17
5) the number of agents and resources involved in the re- minutes. This means that the system requires less than two
allocation process is kept to the minimum. seconds, considering all the simulation time, to manage the
reallocations/conflicts that arise between trains when a new
In FYPA, every train is managed by a “Treno agent” and
train enters the station. This amount of time is acceptable for
every resource inside the station (a node of the graph) is
using AnsaFYPA on-line as well.
managed by a “Nodo agent”1 . Railway tracks connecting
The second station that was used for testing AnsaFYPA
nodes (the arcs of the graph) are resources to be assigned
is Pisa. Pisa is managed by 60 Nodo agents, each having
to trains. The resource allocation problem is solved by means
about 20 entering arcs. Every arc has 130 incompatibilities on
of a complex negotiation protocol that converges towards a
average. This station is definitely more complex than Mestre
solution provided that
because of the many more incompatibilities. The simulation
• there are always more free resources than agents; of the real traffic in Pisa station on the 20th of January 2011,
• at least one complete free path connecting every start with 395 trains crossing the station, took only 13 minutes to be
point to an end point exists; completed (with one train entering the station every 2 seconds,
• the number of arcs in the graph ensures a redundancy in like in the previous example). A graph-like representation of
the choice of paths; Pia station is reported in Figures 2 and 3, where the station is
• agents enter the graph at the time stated by their static partitioned into its left and right sub-graphs.
allocation plan or later; The tests we carried out on StandaFYPA show that it
• it cannot occur that two trains reserve the same resource performs in the same way as AnsaFYPA if considering the
in a “not disputable” way. “allocation phase”, that is, if considering the simulation start-
Both AnsaFYPA and StandaFYPA solve the above problem. ing when the first train enters the station. StandaFYPA is faster
The table below summarizes the differences between the two than AnsaFYPA in its “set up” phase (the phase where Nodo
systems, which are concerned with technical details of their agents are created with the information regarding arcs and
implementations and not with the functionalities they provide. incompatibilities) because the direct access to a database is
definitely faster than using web services and parsing very large
AnsaFYPA StandaFYPA files. The StandaFYPA system takes about thirty seconds to
OS Linux Windows (XP or Vista)
set up, while the AnsaFYPA needs some minutes.
Input Text Files Database
Data Interf. Web Services (WSIG) Connection to DB III. N ET L OGO AND ITS USAGE IN S TAND - ALONE FYPA
Paths Saved in an external file Computed run time from DB
Arcs Mainly One-Way Bidirectional A. NetLogo
GUI Ansaldo STS program NetLogo
This section provides a short introduction to NetLogo and is
B. Evaluation of the AnsaFYPA and StandaFYPA systems based on [1] and on http://ccl.northwestern.edu/netlogo/docs/.
NetLogo is a programmable modeling environment for
AnsaFYPA demonstrated to give good performances when simulating natural and social phenomena. It is particularly well
tested by Ansaldo STS engineers: using a station with about suited for modeling complex systems developing over time.
fifty nodes, two hundreds arcs and at least ten trains in the Modelers can give instructions to hundreds or thousands of
station at the same time, the system was able to find a solution agents all operating independently. This makes it possible to
1 Being developed for an Italian company, FYPA code uses Italian tags for
explore the connection between the micro-level behavior of
agent names: in this paper we keep the names of agents as they are in the individuals and the macro-level patterns that emerge from the
code, to avoid inconsistencies with respect to the images captured from JADE. interaction of many individuals.
Figure 1. The simplified representation of Mestre station (courtesy of Ansaldo STS)
Figure 2. The graph-like representation of Pisa station (right side, courtesy of Ansaldo STS)
Figure 3. The graph-like representation of Pisa station (left side, courtesy of Ansaldo STS)
NetLogo supports three types of agents: turtles, patches, version of the FYPA algorithm mainly because of the follow-
and links. Patches represent square (in 2D) or box (in 3D) ing reasons:
cells on the main 2D (or 3D) view of the world. Turtles are 1) NetLogo is not suitable to simulate a negotiation among
agents that can move around on the world surface, and draw. agents based on a “deterministic view” (namely, a ne-
Links represent relationships between turtles. There is also an gotiation based on a protocol with predefined roles and
“observer agent” that has a view of the whole NetLogo world actions);
and is used for running the main parts of the program (linked 2) NetLogo is not suitable to simulate an interaction where
to buttons on the interface) as well as providing a way of agents exchange messages;
interacting command by command on the main interface. 3) NetLogo does not support a continuous model of time
One of the benefits of using NetLogo, which is in fact we adopted in FYPA.
the reason why we used it in StandaFYPA, is its graphical
Besides these main and almost general motivations, there
interface. By default, the interface contains just a 2D spatial
are more specific ones due to the features of the physical world
view of the model environment, which is a square lattice. In
where our agents (trains and nodes) live, and to the protocol
addition to the 2D spatial view, the developer can add other
we designed.
elements such as buttons to set model parameters and graphs
The environment of our MAS can be represented as a graph
to monitor results. The 2D view has several different options
with nodes and many arcs connecting them, and agents that
that prove useful in modeling. The size of the grid (the number
cross the graph. In NetLogo, links represent a connection
of cells) can be changed, as can the size of the cells themselves
between two agents, but only one link between each couple
(in pixels).
of agents is allowed: the existence of multiple railway tracks
among two nodes was difficult to model. Furthermore, the
B. Why not implementing StandaFYPA in NetLogo
most natural way of using NetLogo is to ask the entire
NetLogo is very useful to simulate the evolution of a system population of agents of some kind to do something, using
consisting of thousands of simple agents divided into different the command “ask agentset to do something”: this command
categories. Hence, it is suitable to implement applications selects one agent from the set in a random way and than
whose main aim is to evaluate the emergent behavior of the executes the code for that agent. Then it randomly chooses
system and where there is no need to follow the life cycle of another agent and so on, until all the agents of that kind
individual agents. In that kind of applications, decisions about have been selected. In this way, the execution of the entire
what action is to be done are usually made using a probabilistic protocol is forced to be sequential, and not simultaneous as
choice. Also, simulated time does not require a sophisticated in FYPA happens, and hence all the problems arising from
management and the built-in representation of time provided the concurrent choice of a resource (path, arc or node) do not
by NetLogo by means of Ticks (a discrete representation of emerge and cannot be dealt with.
time shared among agents) is enough. Although there are ways to avoid this sequential behavior
We could not use NetLogo to implement the stand-alone of the “ask command”, and hence this last problem should
have been overcome, we soon realized that, in order to use Nodes, the node reservation procedure and so on. Then we
NetLogo to implement StandaFYPA, we should have forced will present some more complex examples (using sometimes
NetLogo to behave in a completely different way with respect a Dummy agent from JADE platform) to show the interactions
to its own philosophy. Instead, NetLogo proved a very suitable among Trains and Nodes.
tool for implementing a nice graphical interface for off-line To fully understand the examples we should recall the FYPA
visualization of train paths: we used it for exploiting this system uses Italian names for agents, in particular:
functionality, as described in the next section. • User Agents (UA) are called “Treno”
• Resource Agents (RA) are called “Nodo”
C. NetLogo graphical interface for StandaFYPA
• Resource Agents Manager is called “Prenotazioni-
NetLogo offers an integrated graphical representation of the Stazione”
simulation, so it is almost simple to let the user see how the • User Agents Manager is called “MovimentiIndotti”
simulation is going on. Instead of programming the graphical • Paths Manager Agent (PA) is called “PercorsiAlternativi”
front end of an application, to see for example where the These examples have been executed on a personal computer
agents are moving, one can use NetLogo that provides these with MS Windows XP Professional c , 2 GB RAM and an
visualization facilities for free. AMD Athlon c 64 processor 3000+.
We took advantage of them for off-line visualization of the
StandaFYPA output. Our NetLogo program reads the structure A. Example 1: Resource reservation
of the station and the movements of a set of Trains during In this example we show how Nodo agents interact to
the time from the log files that are output by StandaFYPA maintain the state of the graph updated.
(manually reworked to meet the input format needed by our Considering the graph shown in Figure 5, N odo 3 and
NetLogo program). Due to NetLogo limitations, we are not N odo 4 manage arc number 6 which has an incompatibility
able to draw more that one arc between two nodes. with arc 5, managed by N odo 2 and N odo 5. These arcs
Nodes and trains are NetLogo turtles, whereas arcs are are managed (namely, “in the scope of”) by two Nodo agents
NetLogo link agents. Time is represented using NetLogo because they are bidirectional.
T icks: at every tick, each train will read from a private list Let us simplify the example using a Dummy agent (da0)
(initialized with its movements on the graph) and will move instead of a Train and let us suppose that this agent needs
on a new node (or will remain on the node where it is, if it to leave N odo 3 to move on N odo 4. In this case da0 will
should stay there). send a reservation request to N odo 4 and then a confirmation
NetLogo needs four types of files: message to it.
• Nodes.txt: a list of nodes with their physical position on In Figure 6 the messages exchanged between Nodo agents
the NetLogo output screen; are reported: N odo 4 informs N odo 2, N odo 3 and N odo 5
• Arcs.txt: a list of the arcs connecting two nodes (one arc that there is a reservation request they must be informed of,
for each pair at most); and then it sends a new message, with performative CON-
• Trains.txt: list of all the trains involved in the simulation; FIRM, to inform its neighbors that the previous reservation
• Movements.txt: list representing the position of trains on request has been confirmed.
nodes, for each NetLogo time tick. The execution of this example in JADE takes less than 1
Figure 4 shows the interface of our NetLogo program. When second to be completed.
the program is started, all the agents read the information they B. Example 2: Path reservation, with free nodes
need from these four files. The user can decide to run the In this example we describe the procedure to reserve a path,
simulation “tick by tick” or “as a movie” (selecting the flag and we start from the simplest situation, that is, all the nodes
“Forever” among the options of the “Go” button): in the first are free and there is only one train in the station.
case, the user will ask the system, pressing the button “Go”, to In the table below, the original plan of T reno 1 is reported:
move on the simulation of only one tick (updating the trains considering the station shown in Figure 5, T reno 1 needs to
position), while in the second case the system will update the reserve the path Nodo 1, Nodo 3, Nodo 4 and Nodo 6. In
graph every Delta seconds (that is, every Delta seconds the Figure 7 the complete interaction between T reno 1 and nodes
tick counter will be incremented and the position of trains is shown.
updated), showing in this way the trains moving on the graph. Train Step Node From (ms) To (ms)
Delta is a value that the user can change to slow down or Treno 1 1 Nodo 1 210000 240000
speed up the simulation, using the sliding bar shown at the Treno 1 2 Nodo 3 240000 310000
top of the interface. Treno 1 3 Nodo 4 310000 340000
Treno 1 4 Nodo 6 340000 380000
IV. S TANDA FYPA AT WORK In Figure 8 the movements of T reno 1 in the station
In this section we will describe the main features of are reported: these images come from the NetLogo interface
StandaFYPA using some examples: we will start with simple described in Section III-C. Starting from the creation of
ones to show the basic interactions in the negotiation protocol, T reno 1, the execution of this example in JADE takes less
how the changes of the state of the graph are spread among than 1 second to be completed.
Figure 4. StandaFYPA graphical interface implemented with NetLogo
Figure 5. Station represented as a graph
Figure 6. Example 1: JADE sniffer view
Figure 7. Example 2: JADE sniffer view
First step Second step
Third step Fourth step
Figure 8. Example 2: NetLogo screenshots
C. Examples 3 and 4: Path reservation with occupied nodes requested by T reno 1). The behavior of T reno 1 will change
Now let us consider a further more complex situation that considering the maximum delay it can undergo and the priority
we label with “Example 3”. Suppose that T reno 1 has priority of da0.
equal to 2. The station and T reno 1’s original plan are the Let us suppose that T reno 1 can now accept 4000 millisec-
same ones of the above example. onds as maximum delay, and that da0 priority is 3 (da0 is a
We will show how the Treno agent acts if one of the train with a lower priority than T reno 1).
resources it is trying to reserve is already occupied. As the reader can see in Figure 9, when T reno 1 sends it
In this example we assume that another train (a dummy QUERY-IF messages, it receives an INFORM from N odo 4
agent, da0) has already a reservation for the resource N odo 4 that specifies that the resource is already occupied by train
for the interval 310000 - 340000 (that is the same interval da0, with priority 3, and that the resource will be again
available from 340001 (till 370001, that is, is free for the V. C ONCLUSIONS AND F UTURE W ORK
same time interval but starting from 340001). In this paper we discussed the StandaFYPA systems, its
T reno 1 can calculate the total delay it should accept: in differences with respect to AnsaFYPA, its performances on
this case, 3000 milliseconds, that is an acceptable delay. The real case situations (Pisa and Mestre stations) and its behavior
train decides to maintain its path (even if it could steal the in small examples that we used for debugging purposes.
resource from da0) shifting the reservations: it asks N odo 3 to We already started to look for similar case studies in the
stay more on it, and then it moves on N odo 4 when specified same area to verify if StandaFYPA may be used to solve them
in the INFORM message. All the nodes will answer with a [3]: by analyzing these new case studies in detail and trying
CONFIRM, so the train will again confirm its reservations and to solve them using our StandaFYPA system we will also be
will get a reserved path. able to understand how our protocol can be modified to cope
The interaction among the agents (excluding the last CON- with them and, in general, how it can be made more flexible.
FIRM messages sent back by T reno 1) is shown in Figure Some technical improvements that are on their way are:
9, while the complete simulation made with the NetLogo
• implementing the code to automatically export
interface is reported in Figure 10. Starting from the creation
StandaFYPA log files in the format requested by
of T reno 1, the execution of this example in JADE takes less
our NetLogo graphical interface (currently, some manual
than 2 seconds to be completed.
adjustment is required);
In this situation, the priority of da0 does not care because
• modifying the database (and the code) to model directed
T reno 1 can accept the delay suggested by N odo 4.
arcs instead of bidirectional arcs.;
However, let us suppose that the dummy agent da0, that has
• modifying the protocol to let Treno agents “ask help”: if a
already a reservation for the resource N odo 3 for the interval
Treno agent T 1 needs a resource that is already reserved
240000 - 310000, has priority 3 and that the maximum delay
by another Treno agent T 2 with an higher priority (so
for T reno 1 is 1000.
T 1 is not able to steal the resource), T 1 could ask T 2 to
In this example T reno 1 steals the resource from da0
find another path in the station, that is, it could ask T 2
because it has an higher priority and the delay it should
to release the resource and let T 1 move on that;
accept shifting its reservations is too high (we do not provide
• inserting the configuration parameters regarding the “time
screenshots for this example).
outs” into the database, in order to allow the user specify
An even more complex situation, that we label with “Exam-
how long a Nodo or a Treno agent must wait for an
ple 4”, takes place if the dummy agent da0, that has already
answer.
a reservation for the resource N odo 4 for the interval 310000
- 340000, has priority 1 and that the maximum delay for ACKNOWLEDGMENTS
T reno 1 is 1000. This paper is based on Chapter 5 of Daniela Briola’s
Being 3000 milliseconds of total delay not acceptable and Ph.D. Thesis, [2]. We thank Riccardo Caccia from Ansaldo
being the priority of da0 higher than the one of T reno 1, STS for his help and support during all the stages of FYPA
the train can only search for another path. It asks the Paths development.
Manager Agent (PA) to get the list of alternative paths (from
N odo 1 to N odo 6), avoiding N odo 4. The content of the R EFERENCES
QUERY-IF message sent by T reno 1 to PA is the next one: [1] M. J. Berryman and S. D. Angus. Tutorials on agent-based modelling with
1; N odo 1; N odo 6; N odo 4; [N odo 1, N odo 3, NetLogo and network analysis with Pajek. In R. L. Dewar and F. Detering,
editors, Proceedings of the 22nd Canberra International Physics Summer
N odo 4, N odo 6]; N odo 4 School, pages 351–375, 2010.
while the content of the INFORM message received from [2] D. Briola. Negotiation in Multiagent Systems: Protocols, Ontologies and
PA is the next one: Applications. PhD thesis, DISI, University of Genova, Italy, 2011.
[3] D. Briola and V. Mascardi. Multi agent resource allocation: a comparison
[(1 f alse; 2 true; 5 true; 6 f alse), of five negotiation protocols. In this volume.
(1 f alse; 3 true; 5 true; 6 f alse)] [4] D. Briola, V. Mascardi, and M. Martelli. Intelligent agents that monitor,
that is the list of alternative paths (where 1 f alse means diagnose and solve problems: Two success stories of industry-university
collaboration. In Journal of Information Assurance and Security, vol-
N odo 1 that is not a “Stop Node”). In this case, T reno 1 ume 4, pages 106–117, 2009.
selects the path (1 f alse; 2 true; 5 true; 6 f alse) and it [5] D. Briola, V. Mascardi, M. Martelli, R. Caccia, and C. Milani. Dynamic
succeeds in reserving it, as shown in Figure 11. In Figure 12 resource allocation in a MAS: A case study from the industry. In From
Objects to Agents Workshop, WOA 2009, Proceedings, 2009.
the complete simulation made with the NetLogo interface is [6] Uri Wilensky, at the Center for Connected Learning (CCL) and Computer-
reported. Starting from the creation of T reno 1, the execution Based Modeling, Northwestern University, Evanston, IL. Netlogo: Ref-
of this example in JADE takes less than 2 seconds to be erence homepage, 1999. http://ccl.northwestern.edu/netlogo/.
completed.
Figure 9. Example 3: JADE sniffer view
First step Second step
Third step Fourth step
Figure 10. Example 3: NetLogo screenshots
Figure 11. Example 4: JADE sniffer view
First step Second step
Third step Fourth step
Figure 12. Example 4: NetLogo screenshots