ap-4-10.dvi Acta Polytechnica Vol. 50 No. 4/2010 Agent-based Simulation of the Maritime Domain O. Vaněk Abstract In this paper, a multi-agent based simulation platform is introduced that focuses on legitimate and illegitimate aspects of maritime traffic, mainly on intercontinental transport through piracy afflicted areas. The extensible architecture presented here comprises several modules controlling the simulation and the life-cycle of the agents, analyzing the simulation output and visualizing the entire simulated domain. The simulation control module is initialized by various configuration scenarios to simulate various real-world situations, such as a pirate ambush, coordinated transit through a transport corridor, or coastal fishing and local traffic. The environmental model provides a rich set of inputs for agents that use the geo-spatial data and the vessel operational characteristics for their reasoning. The agent behavior model based on finite state machines together with planning algorithms allows complex expression of agent behavior, so the resulting simulation output can serve as a substitution for real world data from the maritime domain. Keywords: multi-agent system, simulation, maritime traffic. 1 Introduction The maritime domain is a complex environment con- sisting of many independent, though often intensively interacting entities that have their own goals and in- tentions. The aim of this research is to simulate not only legitimate maritime traffic, such as an interconti- nental transportation, coastal fishing and recreational traffic, butalso illegitimateaspects, suchas illegalfish- ing, waste dumping and maritime piracy. In this paper, an agent-based simulation of mar- itime traffic is presented, more specifically the design of an architecture of the simulation platform is de- scribed (Section 2) and the simulation configuration and control flow are explained (Section 4). A model of the maritime environment (Section 5) with several types of independent agents striving to achieve their goals (Section 6) is visualized using theGoogleEarth1 platform (Section 7). The simulation is used to provide a noise-free source of maritime data with the desired spatio- temporal resolution to algorithms analyzing the sit- uation, and it serves for developing and prototyp- ing agent-based techniques for understanding, detect- ing, anticipatingandeventuallypreventingpiracyand, possibly, other categories of maritime crime. Because of the recent surge inmaritime piracy, insurance rates have increasedmore than 10-fold for vessels transiting known pirate waters in recent years, and the overall costs of piracy in the Pacific ocean and the Indian ocean alone were estimated at US$ 15 billion in 2006 and have continued to rise [7]. It is therefore appropri- ate to develop a set of techniques and algorithms that are able reduce this threat. A description of these al- gorithms is beyond the scope of this paper, but it can be found in [5]. Although agent-based techniques have been suc- cessfully applied in other trafficand transportationdo- mains and problems (see e.g. [4, 8]), this is – to the best of our knowledge – the first integrated attempt at employing agent-based concepts and techniques in the domain of maritime transport security. 2 Architecture overview The main objective in designing the simulation plat- form was modularity and extensibility; this objective has been met by employing a loosely coupled archi- tecture with clearly defined data and control flows. A diagram depicting the main modules and data flows is depicted on Figure 1. As can be seen, the simula- tion platform consists of several modules that can be arranged into the following groups: Fig. 1: Main modules and data flows. The lines represent the main data flows, the dashed line represents the tempo- ral synchronization controlled by the simulation loop 1http://earth.google.com 94 Acta Polytechnica Vol. 50 No. 4/2010 • SimulationControl– thesemodules control the initialization and execution of the simulation and all related processes (see Section 4). • Data Sources – these modules provide the plat- formwith the off-line data required for initializing and running of the simulation. For a description of the necessary data sources, see Section 3. • Simulation – containingmodules responsible for representing and operating the simulationmodel, both the simulated vessels and the simulated en- vironment in which they operate. • Analysis – containing modules analysing the data coming from the simulation and a module emulating the imperfect aspects of the real world (noisiness and incompletenessofdata). Adetailed description of algorithms andmodules in this cat- egory is beyond the scope of this paper. • PlanningandCoordination–containingmod- ules responsible for more complex coordination andplanningbeyond thebasic vessel behavior im- plemented as part of the simulation. Two differ- ent planners have so far been implemented. A geo-spatial planner plans the route of the vessel taking into account geographical obstacles (coast- line, shallows, etc.) and a planner using the re- sults of a game-theory formulation of the relation between the transport vessel and the agent (the formulation and results are briefly described in Section 6.3). • Presentation – containing modules responsible for presenting the output of the simulation and the analytical modules using the Google Earth KML2 format. 3 Data sources As an essential feature, the platform incorporates sev- eral categories of real-world data and enables inte- grated analysis, specifically general geographical data comprising general information about the ge- ography of the environment, in particular shorelines, ports and shallow waters. This data is supplied di- rectly by Google (Earth); it is used primarily for general vessel navigation and for providing the back- groundgeographical context in theuser frontend. Op- erational geographical data comprises geographi- cal information specific to the operation of the sim- ulated vessel types, in particular the location of the main piracy hubs [1], piracy zones, fishing zones and transit corridors. The operational geographical data governs the operation of individual vessel categories (see Section 6). Vessel attributes describe vessel operational at- tributes such as vessel type, length, tonnage, max speed, etc. This data is extracted fromvessel tracking servers, e.g. AISLive [2], and is used to provide real- istic parameters for simulated vessels. Activity data comprises higher-level information aboutmaritime ac- tivity. This data is typically provided by organiza- tions observing the situation in relevant regions. The Maritime SecurityCentre, Horn ofAfrica (MSCHOA) [3] providesup-to-date informationonpiracy incidents andalerts in theGulf ofAdenandoff theSomali coast, including guidelines on how to proceed when travers- ing these areas. This data is used for pirate behavior modeling, and also for the route planning of transport vessels. 4 Simulation control The simulation is executed from a script with a pre- defined configuration. The loading of the data and parameters and the creation of the needed data struc- tures is carried out in the Scenario Configuratormod- ule. The simulation time flow is synchronous and dis- crete, i.e. the simulation time ismeasured in steps. In each step, a sequence of synchronized actions is exe- cuted. 4.1 Scenario configurator TheScenarioConfiguratorhandles the initialization of all modules and all agents present in the simulation. The configuration of the simulation (e.g. the num- ber of vessels, the files containing vessel andGIS data, etc.) as well as the parameters of each of the mod- ules is specified in a single Groovy3 script file4. The main advantage of this approach is that the script can be both embedded into a pre-compiled package and kept separate (in the source code form) to be able to run different scenarios or to modify the parameters of the simulation without recompilation. The modularity of our architecture enables us eas- ily to initialize only a small subset of Analyzers or to initialize a simulationwithout support forKML-based visualization when running non-interactive batch ex- periments, and logging the results for later post- processing. 4.2 Time flow The main parameters governing the flow of the simu- lation are the simulation step size and simulation step delay. The simulation step size parameter specifies 2Keyhole Markup Language (KML) is an XML-based language schema for expressing geographic annotation and visualization 3http://groovy.codehaus.org/ 4The nature of scenario description is more algorithmic than declarative; it is therefore more convenient to describe the scenario configuration using a script than using a markup language (such as XML). 95 Acta Polytechnica Vol. 50 No. 4/2010 how much time one step takes, measured in simula- tion time (i.e. not related to the real-world wall clock time5). The simulation step delay parameter specifies how much time a simulation thread sleeps after each step (to leave some computing time to other compo- nents, in particular the presentation andanalysis com- ponent. Thisparameter ismeasured inwall clock time. The simulation duration parameter specifies the total simulation time of a particular scenario. The Simulator module holds information about the current simulation step and the total simulation time of the simulation run. This time is measured in simulation-time seconds (i.e. the maximal granular- ity of the simulation time is one second). The sim- ulation time is related to date-anchored time by the Environment module, where the Environment mod- ule is initialized to a specific calendar time (i.e. 24th of December, 2009). In each time step, the Environ- ment module updates the simulation time so that the other modules can derive additional context informa- tion about relating to the given simulation date. The amount of time in each time step (givenby the simulation step size parameter) affects the simulation granularity, and the temporal resolution of the output data obtained from the simulation. If the simulation step size is 1 s, the granularity is the finest, andwe can focus on vessel behavior in detail (e.g. vessel interac- tion in ports etc.). If the simulation step size is set to 1 hour, the simulation runs fast, and we can roughly estimate the future positions of the vessels and events that may happen in the future. 4.3 Simulation cycle In each simulation step, the following sequence of ac- tions is performed: 1. Environmentmodule updates its simulation time. 2. Agent Container is notified and it sequentially sends the information about the new step to each agent. Each agent spends the amount of time on performing a part of its plan (see Section 6 for details). Generated events are sent to the Agent Container, which distributes the events to all relevant listeners and to the Environment that records the event. 3. If – as a result of actions of the agents – new data become available, this is sent to the subscribed Analyzers for processing and analysis. The synchronous nature of the simulation control, together with seed-based randomization, guarantees the determinism and thus the repeatability of the sim- ulation. Deadlockscannotoccur, asaccess to resources is sequential; this also enables the use of unsynchro- nized data structures, which are faster to work with. 5 Environment model The state of the environment is maintained by two datamodules – theGISDataProviderandVesselData Provider and invariable storing the current simulation time/date. The Environment module is a central ac- cess point for the other modules to the environmental data including data about the vessels. The temporal information is represented in stan- dard time and date units. The main units of spatial information are nautical miles; speed is measured in nautical miles per hour or per second. GIS data model The GIS Data Provider stores the geographical data and provides access to this information. The following data is represented and is available for analysis and display: • Somali harbors – a list of Somali harbors with name, location, adescriptionandapproximateca- pacity for pirate vessels. This data is used for pirate vessel initialization and placement. The original file is a KML file. • Fishing zones – a list of possible fishing zones around the Somali coast. The fishing area is rep- resented by a polygon. This data is used for ini- tialization of fishing vessels around the Somali coast. Currently, artificial zones are used; this can later be replaced by a list of real fishing areas if available. • Piracy zones – a list of piracy zones around the Somali coast. Eachpirate vessel chooses a zone in which it is active. The zone selected is the closest one to the pirate’s base harbor. Currently, artifi- cial zones are used; this can later be replaced by a list of real piracy zones if available. • IRTC corridor – data about the International Recommended Transport Corridor6. This data is used by the transport vessels to plan their trajec- tory. Vessel data model The Vessel Data Provider provides data about the ships in the simulation. Each record is about one ves- sel and is identified with a unique identifier, Vessel ID (this ID is equal to the ship’s call signwhen real-world ship parameters are used). Vessel-related data can be categorized into two groups: • Static vessel information – static information stays the same throughout the simulation and cannot be modified. This information can be viewed as a database table where the rows repre- 5Wall clock time is the humanperception of the passage of time from the start to the completion of a task, i.e. the elapsed real-world time as determined by a chronometer such as a wristwatch or wall clock. 6as defined in http://asianyachting.com/news/PirateCorridor.htm 96 Acta Polytechnica Vol. 50 No. 4/2010 Table 1: Main parameters of different types of vessel agents. Vessel type Parameters Long-Range Transport Vessel Start destination, Goal destination Short-Range Transport Vessel Start destination, Goal destination Fishing Vessel Home port, Fishing Zone Pirate Vessel Home port, Area of control, (targeted ship) sents individual vessels and the columns represent the attributes of each vessel. The data is stored in an SQL database for easy access. • Vessel trace information – a dynamic part of vessel information, storing the actual position of the ship as well as the previous positions in the form of time-annotated location records. 6 Agent vessel model The agents reside in the Agent Container, which dis- tributes events gathered from the agents or from the Environment. Eachagent controls oneormorevessels. Theplans for eachvessel are either createdprior to the simulation (e.g. for transport vessels) or, typically, are generated dynamically during the simulation run (e.g. for pirate vessels). 6.1 Vessel types The platform can simulate the simultaneous activity of a large number (thousands) of the following cat- egories of vessels: Long-range transport vessels are large- to very large-size vessels transporting cargo over long distances (typically intercontinental); these are the vesselsmost often targeted by pirates. Short- range transport vessels are small- to medium-size vessels which transport passengers and/or cargo close to the shore or across the Gulf of Aden. These ships are local, and are not attacked by pirates. Fishing vessels are small- to medium-size vessels which go fishing within designated fishing zones; fishing vessels launch from their home harbors and return back after the fishing is completed. These vessels can potentially be attacked by a pirate, but currently only local fish- ing vessels, which cannot be attacked, are simulated. Pirate vessels are small to medium-size vessels op- erating within designated piracy zones and seeking to attack a long-range transport vessel. The pirate con- trol module supports several strategies, some of which can employ multiple vessels. Table 1 summarizes the main parameters of each type of vessel agent. Note that, in general, a vessel agent can controlmore than one vessel (e.g. amother- ship pirate vessel agent controlling several small boats and a hijacked transport ship). The behavioral models for individual categories of vessels have beenmanually synthesized on the basis of information about real strategies,which have been ob- tained from several sources including the IMB Piracy Reporting Centre7 and the Maritime Terrorism Re- search Center8. 6.2 Executable behavior representation Vessel agentbehavior is implementedusing finite state machines (FSM). Agent FSMs consist of states that represent an agent’s principal mental states. Transi- tions between the states are defined by unconditional or by conditional transitions conditioned by external events. Implementation-wise, the simulator allocates a time slice to the agent and the agent delegates the quantum to the FSM. The current state may either use the whole time slice and stay in the current state, or it canutilize only part of the time slice anddelegate the rest of the time to a following state or states. An example of a pirate FSM is depicted in Figure 2. Fig. 2: Finite state machine of the pirate vessel agent 6.3 Path planning A modular route planning architecture has been de- veloped allowing us to combine general shortest-route point-to-point planners with specialized planners for specific areas. A more detailed description of the op- eration of both planners can be found in [5] and [6]. General shortest-route navigation The basic route planner finds a shortest route between two locations on the Earth’s surface considering ves- 7http://www.icc-ccs.org/index.php?option=com content&view=article&id=30 8http://www.maritimeterrorism.com/ 97 Acta Polytechnica Vol. 50 No. 4/2010 sel operational characteristics and environmental con- straints, includingminimumalloweddistance to shore, which candiffer between regions. Theplanner is based on the A* algorithm adapted for a spherical environ- ment and polygonal obstacles. Gulf of Aden transit planner Factors other than route length need to be consid- eredwhen planning a route through the Gulf of Aden. Two specialized planners have been therefore devel- oped for this purpose. The simple corridor planner navigates the ship through the International Recom- mended Transport Corridor and mimics the current practice in the area. As a possible alternative, sev- eral alternative route planners through this area have been implemented. A risk-minimizing route planner uses a pre-generated riskmap to avoid high risk areas. A game-theory planner solves a two player zero-sum game between the transport ship and the attacker to find an optimal path through the gulf. A detailed de- scription can be found in [5]. 7 Visualization The user front-end provides a geo-based visualization of the various outputs providedby the platform, using Google Earth, a KML capable viewer. Fig. 3: GoogleEarth-based front-end showingvessels, their past trajectories and an output fromdynamic incident risk analyzer over the Gulf of Aden The Google Earth-based front-end allows us to in- teractively visualize the various output of the testbed, both the static data described in Section 3 and the dy- namically generated output of the advanced analysis and planning modules. A screenshot of the front-end is given in Figure 3. In addition to ergonomic navigation and 3d cam- era control, the main advantage of the front-end is the ability to present structured data on varying lev- els of detail. The layer-based interface allows us to select different layers of information and compose an information picture with the aspects and the level of detail fit for the specific user’s needs. To leverage the layer-based concept, the testbed output is organized into multiple information layers. The simulation itself provides a number of layers; each of the analysis and planning tools then also adds its own layer. The integrationwith Google Earth is provided via dynamically constitutedKMLfiles servedbyanHTTP server running inside the platform. The KML files are read into the Google Earth application using its HTTP data link feature and automatically refreshed. This way, dynamic data can be displayed (such as a moving vessel), though for performance reasons, the refresh rate is limited to about once a second. Acknowledgement The researchdescribed in this paperwas supervisedby Prof. V. Mařík, FEE CTU in Prague and supported by Office for Naval Research project no. N00014- 09-1-0537 and by the Czech Ministry of Educa- tion, Youth and Sports under Research Programme no. MSM6840770038: Decision Making and Control for Manufacturing III. References [1] Somalia pirate attacks. BBS Google Earth Forum, http://bbs.keyhole.com/ubb/ubbthreads.php?ubb= showflat&Number=1242871%&site id=1, April 2008. [2] AISLive. http://www.aislive.com/, 2009. [3] The maritime security centre, horn of Africa (mschoa). http://www.mschoa.eu, 2009. [4] Glashenko, A., Ivaschenko, A., Rzevski, G., Sko- belev, P.: Multiagent real time scheduling sys- tem for taxi companies. In Proc. of 8th Int. Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 2009), Budapest, Hungary, 2009. [5] Jakob, M., Vaněk, O., Urban, Š., Benda, P., Pěchouček, M.: Adversarial modeling and reason- ing in themaritime domain,Year 1 report. Techni- cal report, Agent Technology Center, Department of Cybernetics, FEE, CTU Prague, 2009. [6] Jakob, M., Vaněk, O., Urban, Š., Benda, P., Pěchouček, M. AgentC:Agent-based testbed for adversarial modeling and reasoning in the mar- itime domain. Proc. of 9th Int. Conf. on Au- tonomous Agents and Multiagent Systems (AA- MAS 2010) – demotrack, May, 2010. [7] Nincic, D.: Maritime piracy in Africa: The hu- manitarian dimension. African Security Review, Vol. 18(3): p. 2–16, 2009. 98 Acta Polytechnica Vol. 50 No. 4/2010 [8] Pěchouček, M., Šǐslák, D.: Agent-based approach to free-flight planning, control, and simulation. IEEE Intelligent Systems, Vol. 24(1): p. 14–17, Jan./Feb. 2009. About the author OndřejVANĚK graduated inTechnicalCybernetics from FEE, CTU in 2008, and is now a PhD student at the Agent TechnologyCenter at the Department of Cybernetics, FEE, CTU. His main research is focused on machine learning in multi-agent systems, coopera- tive and non-cooperative game theory and coordina- tion and cooperation in multi-agent systems. Ondřej Vaněk E-mail: vanek@agents.felk.cvut.cz Dept. of Cybernetics, FEE Czech Technical University in Prague Technická 2, 166 27 Praha, Czech Republic 99