formal advanced mission planning specification

Faculty of Engineering University of Porto Formal Advanced Mission Planning Specification Pedro Filipe Lopes Maçaira Nogueira Master Dissertation conducted within the Program of Integrated Master in Electrical and Computers Engineering Branch: Automation DISSERTATION Supervisor: Eng. João Tasso Borges de Sousa July 31, 2013 © Pedro Nogueira, 2013 i Resumo Recentemente, os avanços tecnológicos têm levado ao aparecimento e proliferação dos sistemas multi-veículos. Os crescentes interesses de pesquisa nestes sistemas têm-se multiplicado em várias questões. O tema desta tese é o estudo associado com o desenvolvimento de um modelo para sistemas multi-veículos que será implementado como uma aplicação de planeamento, que irá abranger questões como “task allocation”, “world modelling” e “networks topologies”. Em primeiro lugar, foi realizado um estudo inicial em sistemas multi-veículos com o intuito de compreender as principais motivações para a implementação desses sistemas e como são implementados. Simultaneamente, foi feito um estudo sobre o estado da arte, não só para estes sistemas, mas também para compreender os paradigmas do planeamento. Em segundo lugar, o trabalho focou-se na compreensão de como cada agente do sistema deve ser caracterizado, de forma a fornecer informação essencial quando se define um estado do sistema. Este foi o ponto de partida para construir os modelos conceptuais iniciais de cada um. Depois de ter esses modelos especificados e tendo em conta o estudo efectuado sobre “networks topologies”, foi desenvolvido um modelo para abstracção e mapeamento de operações de cooperação. Todos os modelos desenvolvidos foram fundidos, compondo assim um modelo final do sistema. Depois de ter o modelo do sistema desenvolvido, este foi codificado utilizando uma plataforma “open source” para planeamento, programação e programação por restrições, chamado EUROPA. Esta plataforma permite construir planeadores e tem como objectivo facilitar o processo de integração de planeamento, programação e satisfação de restrições em aplicações para utilizadores finais. Finalmente, o modelo foi aplicado em alguns cenários operacionais exemplo, a fim de provar a sua capacidade de planeamento de operações em sistemas multi-veículos e entender as suas vantagens e desvantagens. ii iii Abstract In recent years, the technological advances have led to the appearance and proliferation of multi-vehicles systems. The increasing research interests in these systems have multiplied onto different issues. The subject of this thesis is the study associated with the development of a multi-vehicle system model to be implemented as a planning application, which will cover issues as task allocation, world modelling and networks topologies. At first, an initial study of the background on multi-vehicles network, in order to understand the main motivations on deploying multi-vehicles systems, and how these were deployed, was done. Alongside, a study on the State of the Art was done not only to these systems but also on planning paradigms. Secondly, the work focused on understanding how each system agent should be characterized in order to provide essential information when defining a system state. This was the starting point to build the initial concept models for the agents. After having these models specified and regarding the study done on the networks topologies, a model to abstract and map cooperative operations was developed. All the developed models were merged into one compounding the final system model. After having the desired system model, it was encoded using an open source platform for planning, scheduling and constraint programming, called EUROPA. It allows building planners and has the objective to facilitate the process of integrating advanced planning, scheduling and constraint reasoning into end-user applications. Finally, the model was applied to some operational scenarios examples in order to prove its ability to output plans for multi-vehicle systems and understand its advantages and disadvantages. iv v Acknowledgments I would like to thank my parents for whom I am deeply grateful for all the sacrifices made, providing me the opportunity to be where I am today, and for the robust education they gave me, which I am proud of and helped me made the person I am today. I also want to thank my brother for being an inspiration for me, through all the success he has achieved and the principles he transmitted to me as an older brother. I thank my supervisor, Eng. João Tasso Borges de Sousa, for the opportunity, support and guidance and shared knowledge during the development of this work, as well as the LSTS people, who helped me through the technical difficulties, especially José Pinto and João Fortuna. I want to give a special thanks to Rita for listening, encouraging and giving me motivation words when I most needed. She was very important in my success and in the future I hope to continue to achieve it and share it with her. I would like to acknowledge my fellow students for all the friendship, stories and good disposition during these years. Thanks to all my family, each one of you has inspired me in its own way. For last, but not least, I want to thank my best friends for all the moments we have passed together. Hopefully we are young enough to write more histories together. xii Figure 20 – STN with two variables and a single constraint; Resulting DG ........................ 19 Figure 21 - A general architectural block diagram for an AI based Planner [38] ................. 21 Figure 22 - The Tire-World Domain - an example of a sequential operator plan. States contain fluents that are true (white) or false (greyed-out). Actions effect plan state. [29] ...................................................................................................... 21 Figure 23 – Possible token temporal relations [29] .................................................... 22 Figure 24 - A Timeline for a tire. Located is a state and moving an action [29] ................. 22 Figure 25 – Physical entity characterization architecture ............................................ 27 Figure 26 – Toy example mission overview ............................................................. 27 Figure 27 – Four states of the toy example mission ................................................... 29 Figure 28 – Physical entity concept architecture ...................................................... 34 Figure 29 – Composed operations concept architecture .............................................. 34 Figure 30 - A general architectural block diagram for an AI based Planner [38] ................. 35 Figure 31 – Conceptual class diagram for vehicles model approach ................................ 37 Figure 32 – Conceptual class diagram for control stations model approach ...................... 38 Figure 33 – Conceptual diagram for a service model .................................................. 39 Figure 34 – Sampling service conceptual diagram ..................................................... 39 Figure 35 – System model concept ....................................................................... 41 Figure 36 – Composed Service and Service conceptual model applied to Control Station and Vehicle conceptual model ..................................................................... 42 Figure 37 – Initial timelines and predicates ............................................................ 44 Figure 38 - Timelines and predicates with transitions between them – Composed Service request, executing and completion constraints ................................................. 47 Figure 39 – Timelines and predicates with transitions between them – Vehicle model constraint .............................................................................................. 47 Figure 40 - Timelines and predicates with transitions between them: Payload assignment and actions ............................................................................................. 48 Figure 41 – Timelines and predicates with transitions between them: constraints for a Gather Step, one possible step of a Service Steps execution sequence .................... 48 Figure 42 – CS1 model and attributes .................................................................... 63 Figure 43 - UAV1 model and attributes .................................................................. 63 Figure 44 – UAV2 model and attributes .................................................................. 63 Figure 45 – AUV1 model and attributes .................................................................. 64 xiii Figure 46 – AUV2 model and attributes .................................................................. 64 Figure 47 – AUV3 model and attributes .................................................................. 64 Figure 48 – Solver for Operational Scenario 1........................................................... 68 Figure 49 - Solver for Operational Scenario 2........................................................... 68 Figure 50 - Solver for Operational Scenario 3........................................................... 68 Figure 51 - EUROPA UI showing a domain solution for operational scenario 1 .................... 69 Figure 52 - Details of the vehicles Executing state .................................................... 70 Figure 53 – Details of the coordinated services steps ................................................. 70 Figure 54 - Details of the Gather Step GatherSample ................................................. 71 Figure 55 - EUROPA UI showing a domain solution for operational scenario 2 .................... 71 Figure 56 - EUROPA UI showing a domain solution for operational scenario 3 .................... 72 Figure 57 - Solver for Operational Scenario 3 with no solution ...................................... 73 xiv xv List of Tables Table 1 – Entities and components state ................................................................ 28 Table 2 - Entities and components state at four different states ................................... 30 Table 3 – Entities state with values properties ......................................................... 31 xvi xvii Acronyms UAV — Unmanned Aerial Vehicle AUV — Autonomous Underwater Vehicle ROV — Remotly Operated Vehicle ASV — Autonomous Surface Vehicle FEUP — Faculdade de Engenharia da Universidade do Porto (Faculty of Engineering University of Porto) LSTS — Laboratório de Sistemas e Tecnologia Subaquática (Underwater Systems and Technology laboratory) IMC — Inter Module Communication XML — Extensible Markup Language UAS — Unmanned Aerial System 1 Chapter 1 Introduction Over the last decades, and due to robotics technology evolution, several unmanned vehicles have been developed for military, search and rescue operations. By definition a military operation is the coordinated military actions in response to a developing situation and these actions are designed as a military plan. This is, a formal plan for military armed forces, their military organizations and units to conduct operations, as drawn up by their commanders in order to achieve the objectives. These plans are generally produced in accordance with the military doctrine of the troops involved. It helps standardize operations, facilitating readiness by establishing common ways of accomplishing military tasks. Just as purely human operations need to be planned following standardized procedures, so combined operations between human, manned and unmanned vehicles need. It is known that a successful planning is a crucial step to achieve desired goals. 1.1 Objectives This project will be developed with the help of “Laboratório de Sistemas e Tecnologia Subaquática” - Underwater Systems and Technology Laboratory (LSTS) as it falls within its development motivation: the development of tools and technologies for the deployment of networked vehicle systems. There is an on-going trend towards the creation and development of multi-vehicle systems. These systems are characterized by being composed by heterogeneous groups of vehicles, manned and unmanned, sensors and operators. One of the biggest challenges concerning these systems is that the network, all the components described before, is a dynamic network and being able to understand the networks that are formed, i.e. the network topologies, and their behaviours is a great motivation. This project will focus on developing a model specification to be implemented as an advanced mission planning system with the objectives: 2 Introduction  Standardize mission plans to facilitate the inter-operability between different unmanned vehicles as UAV’s, AUV’s, ROV’s and ASV’s in advanced cooperative operations  Provide a new approach on defining a system state, at any time, and with it being able to understand the networks that are created 1.2 Thesis structure The present document integrates all developed work, as well as the results and the conclusions obtained. In Chapter 2, some technical and theoretical background is given about LSTS, its hardware, software tool chain, objective and achievements. In Chapter 3Chapter 3, a bibliographic review and the State of the Art for multi-vehicle systems and planning paradigms is presented. In Chapter 4, the problem is described and defined formally. The formalization of the problem is the starting point to the development of the work. In Chapter 5, the problem is approached through a design work involving multiple iterations from an initial concept model to an actual model encoding. In Chapter 6, the global results for the model application are discussed. The model is also evaluated and analyzed along with multi-vehicle important issues. Finally in 0, the conclusion and discussion about further developments is presented. 3 Chapter 2 Background This chapter provides background material on vehicles, on the PITVANT project and on the LSTS software tool chain. 2.1 Introduction The Projecto de Investigação e Tecnologia em Veículos Aéreos Não-Tripulados (Research and Tecnology in UAV’s Project) arises from a joint operation between Faculdade de Engenharia da Universidade do Porto (Faculty of Engineering University of Porto) and Academia da Força Aérea (Portuguese Air Force Academy), being the third stage of a greater project that began in 1996 in AFA. This stage began due to the achieved results in the early stages, started January 2009 and has a scheduled end to December 2015. Some of the specific PITVANT objectives are to develop several technologies as:  Cooperative control for multiple UAVs with mixed initiative  Data fusion systems  Navigation systems  Vehicle-interoperability and the standardization of interactions And to train personnel with the ability to define requirements, to operate and maintain UAV’s [1]. The Laboratório de Sistemas e Tecnologia Subaquática (Underwater Systems and Technology Laboratory) have been developing, designing and building several autonomous and remotely operated vehicles as well as several tools with the goal of deploying networked vehicle systems for oceanographic and environmental applications [2][3]: 10 Literature and State of Art This thesis will focus primarily on task allocation, world modeling and networks topologies problems. A more detailed and comparative evaluating approach will be done, in the next sections, to works of interest. 3.1.2 Task Allocation Task allocation is the process that results in engaging specific tasks to specific vehicles, with the restriction that each task requirements should be satisfied, by the assigned vehicle, in order to be possible to achieve the task goal. In a simple mission configuration, with few vehicles, it is easy to a human planner to achieve optimal tasks assignments. However with the recent interest in deploying large multi-vehicle missions, this capability becomes too hard and time consuming. The transfer of responsibility from human planners to the vehicles themselves will improve the task allocation performance and reduce the manpower requirements [14]. As said in section 3.1.1, several methods, that empower vehicles with the ability to distribute tasks among themselves, have been developed. In [19] an early problem formulation using mixed-integer linear programming is described where a solution to a multitask assignment problem is to be found. The attention-grabbing of this work is that the tasks are coupled by timing, precedence, and task order constraints. This allows variation of the vehicle path time to guarantee that the timing constraints are satisfied and directly incorporates the varying task completion times into the optimization. This formulation resulted in a large optimization problem with too many constraints to be applied to a realtime problem. At [16] the same problem formulation is used but with the inclusion of continuous timing variables that allowed solutions with any feasible task completion times to be calculated. The results presented were for practical problem sizes, but with larger problems, further work has to be done in order to simplify the problem structure and reduce complexity. This reference [18] describes a kind of metaheuristic, the ant colony algorithm, that simulates the behavior of ants searching for food resources in nature. Optimizations to this algorithm, as the one that is presented in the work, are widely employed to solve optimization problems on task allocation. The model presented, as the ones presented above, also restricts the task allocation thought time, precedence and task order constraints. Additionally to this, the model also incorporates a performance requirement, given by the ratio of task covering, the cumulative distances travelled, the task completion time and the gaining maximal value. The optimization provided to the ant colony algorithm proved to find good solutions, especially with dynamic environments where tasks appear, largely due to the positive feedback the algorithm has. Multi-vehicle Networks 11 Figure 11 – Ant colony algorithm logic: a) Ants follow a path between points A and E. b) An obstacle is interposed; ants can choose to go around it following one of the two different paths with equal probability. c) On the shorter path more pheromone is laid down. [23] Until here, the approaches described have one common feature: a centralized cooperative task allocation. In [15] a fully decentralized cooperative task allocation approach is proposed and it is based on a dynamic task ranking (DTR) procedure. It has two key concepts: agent-task benefit and task-task benefit. Each agent is assumed to be able to calculate the cost it takes to accomplish a certain task, so that if it is not capable, the cost is infinite. The benefit agent-task is the multiplicative inverse of the task cost, and the tasktask benefit is the benefit that an agent has to accomplish the tth task after the completion of the jth task, defined in analogy with the agent-task benefit. So, in simple words, the benefit of accomplishing a task depends not only on its accomplishment, but also on the already accomplished tasks. For example, if there are nearby tasks, and an agent accomplishes one of those, it will be favored to accomplish the others. The approach presented does not define formally the tasks, it is only known that there are tasks to be executed and that each agent is able to calculate the costs. Another decentralized task allocation method is presented at [17]. A simple model where vehicles choose tasks autonomously in real-time, using a central cognitive map, is described. This model was used considering a heterogeneous group of vehicles drawn from distinct classes. The idea behind the central cognitive map is to provide instantaneous and accurate information of the current mission situation to the vehicles team. The model defines the vehicles state, tasks state and the task assignment state through state vectors. A Lx×Ly cellular environment is considered, where each cell state is given by the target occupancy probability (TOP) value, which defines the estimated probability that cell contains a target. At every time, t, every cell (x,y) in the environment has an associated task, and each cell 12 Literature and State of Art Figure 12 – Task Dynamics. ps=suspicion threshold; pc=certainty threshold; pe=exit threshold; pr=resolution threshold [17] state defines the task action that needs to be done. Every time a vehicle performs a task action in a cell, the TOP value is updated through defined probabilistic functions, and according to the task dynamics thresholds (Figure 12) the cell state will change. At each step the vehicles report their actions to a centralized information base (IB) and update their knowledge off the environment by reading the IB. Interesting contributions are found in this work, more precisely, the fact that vehicles states, tasks states and tasks assignment states are defined by state vectors, which proves to be an easy approach on sharing states information among information structures. Although, a limitation to this approach could be pointed out: all vehicles have to continuously maintain communication links to the IB in order to update and read it. 3.1.3 World Modeling Efficient operational autonomous systems require a comprehensive overview on their environment [24]. This statement portraits the importance of the world modeling issue. With the recent grow of multi-vehicle systems it becomes clear that having a formal representation and understanding of the relevant surrounding world is a key element for achieving successful missions. Obviously, this representation has to be common to all system agents and they should be able to maintain and share a real-time world model. Multi-vehicle Networks 13 Reference [20] describes a world modeling approach for cooperative intelligent vehicles. The proposed approach uses Local Dynamic Map (LDM) as the element responsible for representing and maintaining a real-time world model. LDM is an object oriented representation that contains both real life and conceptual objects, being all characterized by attributes, uncertainties and some relevant relationships between them (see Figure 13). The model is shared by all onboard control functionalities, denominated as “Applications”, and works as an abstract layer between them and the data interpretation (see Figure 14). The proposed architecture is described as having a number of advantageous features, being some of them, in this work point of view, considered important contributions:  Sensory and control aspects are isolated by an abstract layer  The vehicles can, through dedicated applications, share local world models among them Another contribution, which should be pointed out, is, as said earlier, that everything considered important from the real world is modeled as an object. Object types are defined in an inheritance hierarchy which not only allows an easier categorization management, as well as an easier extendibility, without disturbing the existing ones. Figure 13– LDM object model 14 Literature and State of Art Figure 14 – LDM proposed architecture 3.1.4 Networks In multi-vehicle systems, a network topology should describe, logically or physically, the arrangement of the network, by describing its nodes and connecting lines. As these systems are growing and becoming large scale systems, it becomes imperative to develop new methods that will provide additional support on vehicles’ cooperation and coordination. In [22] a service network model is described with the objective to find an organizational paradigm that will fit to multi-vehicle and multi-task systems. The model consists of two basic entities: services and service providers. Service providers deploy and make theirs services available to others, being, typically, the deployment of a service dependent on other providers’ services. So, it can be claimed that this service network consists of a set of service providers that use each other services. Service providers can be physical entities as control stations, vehicles, among other or logical resources as complex algorithms. This model was applied to a simple multi-vehicle search mission, where a mission control requests a search service, with coordinates and object description as service constraints. The search service provider then divides the territory and requests sweep services to multiple vehicles. There is a reliable data storage provider to share information among all vehicles. Figure 15 – Example of simple knowledge base [22] Multi-vehicle Networks 15 Figure 16 – solution generated by the algorithm [22] A service network can be represented as a directed rooted graph. The addressed problem consists on finding a graph G, which includes the initial graph G0, being consistent, complete, and connected, as well as the minimal solution to the problem. The initial graph G0 represents the service requirement and associated with it has the requester constraints. Each service provider has some constraints associated with each service it deploys. The main contributions to learn and keep from this work are: network topologies can simplify the achievement of cooperative multi-vehicle configurations, distributing objectives and at the same time sharing knowledge; networks topologies defined through abstract capabilities, as the sweep and the search service, can be applied to various types of vehicles; and although the model is not referred to as a task allocation model, it in fact distributes tasks according to the requester restrictions, maybe not achieving the best solution, in terms of for example cost, but satisfying the requester objectives. Figure 17 – SN developed to the multi-vehicle search; the “?” correspond to the unknown service providers that the solve primitive is supposed to fill in [22] 16 Literature and State of Art 3.1.5 Multi-vehicle Systems Issues Multi-vehicle systems, at some point, become coupled distributed networks of semiautonomous problem solving agents. For example, if a problem can be solved more effectively through cooperation, the vehicles should work together by dividing the problem into sub problems each should solve. Depending on the problem, sub problems can be dependent and sequential, and, in that situation, agents must coordinate their local problem solving actions. The main problem solution will, in any circumstance, arise from the combination of the sub problems results [25]. What will be presented in this section are the main issues concerning this type of multi-vehicle cooperating systems. Four main issues were identified: System model; System domain an environment assumptions; Fault tolerance; and Communication importance. A more detailed work on evaluating and comparing cooperative distributed problem solving researches is done in [25]. The issues presented will work as guidelines when evaluating and classifying the work developed (0, section 7.2):  System model: this issue focuses on describing and representing the system. The following questions will help understanding each problem solving model: o Is there a defined control hierarchy? How is it defined? o Does cooperation exists? Is it crucial in achieving system goals? o Does cooperation between agents forms an agent composed model? What benefit comes from achieving the composed model? Who knows when a model is composed? o What and where are the communicating structures? What connections are needed? Do they need to be permanent? o Problem-solving Strategy: How are system goals distributed and broken down to sub goals? Are all goals defined in the planning phase?  System domain and environment assumptions: this issue focuses on describing the assumptions that the problem solving model makes about the problem domain. It is important to state that the less assumptions, the more generally applicable the system is to problem solving [25]. o How is the system domain characterized? o What a priori knowledge do agents have about other agents? o How is problem solving knowledge shared among agents? o Is the system domain dynamic? What features may vary along time?  Fault tolerance: this issue focuses on describing how the system deals with multiple kinds of failures and if it includes mechanisms for problem solving in real-time domains. o What possible failures are assumed to be possible? o How does the system deals with faults? Planning Paradigms 17 o Is predictive timing information available? o Are there tasks deadlines?  Communication importance: this issue focuses on describing how communications are made in the system and how agents know when to communicate and to whom. o How are the communication paths specified? o How are messages addressed? o What information do agents use to determine the when, whom, and what of communication? 3.2 Planning Paradigms 3.2.1 Planning, Scheduling and Automated Planning Traditional planning often views planning systems as simple isolated components that accept a set of goals, initial conditions, and a description of the possible actions that can be executed and generate an output, as seen in Figure 18. This output is called a plan, a sequence of actions, that after executed makes the system to achieve the goals [26]. This idea gives the simple definition of planning: finding a sequence of actions that achieves a desired goal. Scheduling can be thought of as determining whether the needed resources are available to complete the plan. It concerns with the allocation of resources to activities with the objective of optimizing some performance measures. Resources, depending on the situation, can be viewed as a variety of things as machines, humans, fuel, battery, etc. and the scheduling objectives could be minimization of the plan length, maximization of resource utilization, among other [27]. Automated planning is the area of artificial intelligence (AI) that studies the deliberation process described above computationally. In automated planning, the problems states correspond to instantaneous descriptions of the world and the actions that an agent can perform to change the state of the world [28]. The state is usually represented as a set of Figure 18 - The traditional view of planning as an independent component [26]. 18 Literature and State of Art Figure 19 – The state space for the vacuum world. Links denote actions: L=Left, R=Right, S=Suck. logical formulas and the state transitions implies the change in formulas. How the world changes through actions is described in the domain model. In Figure 19 it is possible to see the state space for a vacuum world toy example where:  State – determined by the agent location and if the locations are clean/dirty, being 8 possible states. The agent is in one of two locations, each of which might be clean or dirt  Actions – Move Right, Move Left, Suck  Transition Model: actions have their expected effects, except that moving Left in the leftmost square, moving Right in the rightmost square, and Sucking in a clean square have no effect.  Goal – Clean everything 3.2.2 Constraint-Based Planning Constraint programming was born as a multi-disciplinary research area that uses techniques and notions from many other areas as artificial intelligence, computer science, databases, and programming languages, among other. It is applied with success to variety of domains, including scheduling, planning, networks and vehicle routing [27]. Constraint programming is a programming paradigm where the relations between variables are stated in the form of constraints and a constraint satisfaction problem states which relations should hold among the given decision variables [27]. A simple example is provided next, adapted from [29]. Having the following variables: Planning Paradigms 19  Speed = [1 10] i.e. the variable speed has a value in the range from 1 to 10.  Distance = [40 100] i.e. the variable distance has a value in the range from 1 40 to 100.  Time = [0 inf] i.e. the variable time has a value in the range from 0 to infinity.  Location1 = [20 25] i.e. the variable location1 has a value in the range 20 to 25.  Location2 = [80 200] i.e. the variable location2 has a value in the range 80 200. And the set of constraints:  C0: speed == distance/ time  C1: location1 + distance == location2 The solution for this problem is given each variable a value such that all constraints are satisfied. A possible solution would be:  speed=10; distance=70; time=700; location1=25; location2=95. 3.2.3 Simple Temporal Problems (Networks) A simple temporal problem is a problem where all the constraints specify a single interval. In [30] it is proposed that constraints among time points can be grouped together to form a Single Temporal Network (STN). This network can then be transformed into a Distance Graph (DG) where the external arc from a node to a target node represents the maximum distance. In Figure 20 it is possible to see a STN with 2 variables and a single constraint, and the resulting DG (adapted from [29]). Figure 20 – STN with two variables and a single constraint; Resulting DG 26 The Problem 4.2 System Specification 4.2.1 System State In order to solve the system state specification issue, firstly it is important to identify the key elements to define a system state at any time. A system state should be described by all the system components, either being:  Physical entities (PE)  Computational Entities (CE)  Abstracts Entities (AE) and each of these elements, should have a state representation that combined together with all the existing elements state representation, define the system state. Consequently, along with identifying the key elements in a system state, it is imperative to define how to characterize each one, in order to represent its state over time. Physical entities by definition are entities with physical existence. In heterogeneous multi-tasking systems these entities are mainly control stations, vehicles and their payload. As payload is associated with bigger entities, as vehicles, its characterization becomes part of the main entity characterization. Computational entities, as the name suggests, are computer programs that act for a user or other program in order to solve problems. In the studied systems, these are controllers and planners, which run on physical entities and therefore will be included in their characterization. Abstract entities are defined by not existing as physical or computational entities, but rather as an idea, type of thing, that have been condensed from concrete realities. In this work, interactions between physical entities, computational agents and the environment can be abstracted as being from a specific type. These abstract entities have to be associated with physical entities, in order to provide them with the knowledge of what they are doing in a high-level mission perspective. In other words, in these heterogeneous, large-scale, multitasking systems, it becomes significantly important to know not only what a single actor is providing, but what a cooperative group of actors is providing, by being in some composed operation over time. At this point it comes clear that having a well-defined characterization for physical entities and thereby their components, either being computational agents or other physical entities, is crucial for having a well-defined system state at any time. Figure 25 illustrates the characterization architecture for main physical entities. System Specification 27 Figure 25 – Physical entity characterization architecture It can be claimed that gathering and merging the states of all existing physical entities on a system, at any given time, provides a consistent system state for that time. 4.2.1.1 Physical Entities Characterization Requirements Each of the main physical entities that have been identified, vehicles and control stations, should be defined by a specific characterization that focuses on describing the entity main properties and its state properties in the world. The main properties, although not being related to the entity state, because they should be unchanged over time, are an important component of the entity characterization, because they should express the entity configuration. The state properties considered to be crucial, when capturing the entity state, should be identified based on the needs of experienced operators. Figure 26 – Toy example mission overview Physical Entity Computational Agents Abstract Concepts Physical Entity 28 The Problem To better understand what this concept is and how it could be applied to an operational scenario, consider a “toy example” in which a system is composed by the main physical entities: UAV, AUV and a Control Station (Figure 26). The following configurations are assumed:  UAV – simple manoeuvre controller (CA) and Wi-Fi communication system (PE)  AUV – simple manoeuvre controller (CA), Wi-Fi communication (PE) and water sample system (PE)  Control Station – Wi-Fi communication system (PE) For this system, it would be easy to define a possible state characterization for each entity based on theirs configurations. As an example, some possible states for each of the entities, and their components, are presented in Table 1Table 2. These states representations are simplified, as it would be possible to have a more detailed state if at each possible state value, some details were added. For example, if the “Goto” value for the manoeuvre executing state could have two sub-values: “from” and “to”, that would specify from and to where the vehicle is travelling. UAV and AUV entities have a very similar characterization. Both could be idling or executing an operation, communicating with another entity or idling and executing a “Loiter” or a “Goto” manoeuvre. AUV has also another component, the water sample system that could be sampling or idling. The control station could, either, be idling or requesting tasks and communicating with other entities or idling. Assuming an operational mission, at the toy example scenario, where an operator at the control station wants a water sample of a specific area, a possible executing approach would be:  a command would be sent to the AUV with waypoints where to sample and after that, a communication waypoint where it should go and send the information gathered to the UAV  the UAV would be commanded to go to the communication waypoint, wait there until it receives the information from the AUV and then go back to the control station. Table 1 – Entities and components state Entity Entity State Comms State Manoeuvre Executing Sensor State UAV AUV Control Station {Idle, Executing} {Idle, Executing} {Idle, Requests} {Idle, Communicate} {Idle, Communicate} {Idle, Communicate} {Goto, Loiter} {Goto, Loiter} - - {Idle, Sample} - System Specification 29 Give this mission, at some point the four states shown in Figure 27 would occur. As presented in Table 2, at each of that states, it is possible to see what is happening in the world by gathering the entities state, as well as theirs components state. Although this representation would provide a system state based on each entity state, it would not illustrate what really is happening, in terms of a composed operation. As said before, the composed operations problem arises from this point, and it will be presented in the next section. Figure 27 – Four states of the toy example mission 1 2 3 4 30 The Problem Table 2 - Entities and components state at four different states State Entity Entity State Comms State Manoeuvre Executing Sensor State S1 UAV AUV CS Executing Executing Request Idle Idle Idle Goto Loiter - - Sample - S2 UAV AUV CS Executing Executing Request Idle Idle Idle Goto Goto - - Idle - S3 UAV AUV CS Executing Executing Request Communicate Communicate Idle Loiter Loiter - - Idle - S4 UAV AUV CS Executing Idle Request Idle Idle Idle Goto Loiter - - Idle - 4.2.2 Composed Operations Specification As said earlier, a new model to define composed operations is to be developed, that in addition to give advantage on large-scale systems state capture, it provides specific system entities with the planning knowledge to achieve them. This model should be defined as a network of service providers [22] that together offer the possibility to establish composed operations, and provide additional features to a system. It should arise from the coordination and combination of system resources in particular situations. The ability to specific system entities identify what composed operations the system can offer, should derive from the composed operations specification, which should follow a design specification. This design specification should be enough detailed, not to compromise the achievement of a composed operation and as a result, provide new features to the system, but at the same time not too restrictive, in order to simplify its formation at any time. 4.2.2.1 Composed Operations Design Specification Requirements Along this work a composed operation refers to the combination of single operations in order to provide additional features and capacities to a heterogeneous multi-tasking system. A single operation is defined by being a sequence of specific pre-defined actions in order to achieve the operation goal. Again considering the example mission, described in the previous section, a composed operation could be specified as being a “Sampling” operation. The composed operation would have two different operations, “Relay” and “Gather”, to be executed by different entities. As said before, an abstract concept is an idea, type of thing, that have been condensed from System Specification 31 concrete realities, and so in a composed operation, the “Sampling” operation and its suboperations can be modelled as abstract entities. In a simple way, if these abstract entities were associated with the entities models and, somehow, transformed into details of the entity states values, it would add more description to the system state. For example while in the four states of Figure 27, the entities states would be as in Table 3. Although at this point the composed operations model would be just an approach to solve the cooperative operations problem in the system state capture, it would be also desired that it provided systems with the capabilities to trigger, achieve and output plans for them, when possible and requested. This would be possible if, as in [22], each system entity had the knowledge of how to execute the operations, it could provide, and some of these entities had the knowledge of how to achieve the composed operations. Formally, a composed operation requester would be a system entity with the specification knowledge and that would have control over other entities, so that it could send plans, or objectives, and supervise their execution. From the design specification it would be possible to restrict the entities likely to be assigned to a single operation, as each entity would have an identifier (the abstract concept associated to the characterization) that confirmed the ability to perform it or not. Table 3 – Entities state with values properties Entity Entity State UAV AUV Control Station Executing(Sampling(Relay)) Executing(Sampling(Gather)) Requests(Sampling(Relay(UAV)),Sampling(Gather(AUV)) 32 The Problem 33 Chapter 5 Approach In the previous chapter, the problem was defined and two main sub-problems emerged:  to identify and develop a model to the system entities  to specify and develop a model to define composed operations in a system It was described that having a well-defined characterization for a system main physical entities and their components is a crucial stage. After that, the composed operations model concept and the main features it should provide were also described. After specifying the models to the system entities, and to the composed operations, it is desirable to somehow assemble the models. With a model for the whole system, the next goal is to implement it with a framework capable of building planners with a modelling approach. 5.1 Overview Recapping the problem, there were two main issues to solve: the specification and development of a model to define composed operations and the specification of a model for the system entities. It was also desired to provide a planning method that would take advantages from knowing the system state and what composed operations it could provide. The first step, on this approach, was to specify the models to the system entities and to the composed operations. After, it was desirable to formalize a model that would combine both, in order to be possible to develop a planner capable of implementing it. To solve the implementation problem, an appropriate platform should be chosen, so that it can output some kind of planning. From what was learnt in section 3.1.3, it was decided to develop generic structures to model the system entities and the composed operations. The structures are object oriented, 34 Approach being each object characterized by attributes, actions and some possible relationships with other objects. At Figure 28, the physical entities concept architecture is presented, following the characterization architecture from Figure 25. The composed operations concept architecture, as is shown in Figure 29, is only composed by abstract entities objects. This was done because, as it was pointed out in section 3.1.4, networks topologies defined through abstract capabilities can be applied to various types of vehicles, even though the way of implementing it is different. Figure 28 – Physical entity concept architecture Figure 29 – Composed operations concept architecture -Properties Physical Entity +Actions() -Properties Physical Entity +Actions() -Properties Computational Agent +Actions() -Properties Abstract Concept 1 0..* Has4 1 0..* Has4 1 0..* Has4 11 Has4 11 Has4 +Actions() -Properties Abstract Concept 1 0..* Has4 Relationship System Specification 35 Figure 30 - A general architectural block diagram for an AI based Planner [38] For the model implementation, it was proposed by LSTS, to use EUROPA (see section 3.3) because it would satisfy most of the problem requirements. One of EUROPA’s key development goals is to streamline the process of integrating advanced planning, scheduling and constraint reasoning into an end-user application [33]. As seen in Figure 30, EUROPA uses a domain model, together with initial conditions and goals in order to output plans [38]. This means that a single planner can be applied to different systems and problems if different models and goals are provided [29]. Briefly, if a system model for the whole problem is formed, it can be applied together with initial conditions, which ideally would be the system state at the planning desired time, and goals in order to achieve composed operations and output plans for it. 5.2 System Specification 5.2.1 Physical Entities Model As said in the problem chapter (Chapter 4), the properties considered to be crucial, when capturing the entity state, were to be identified based on the needs of experienced operators. After some meetings and discussions on the problem, the following properties were identified, as fundamental, on each main physical entity and its components. Firstly, the vehicles properties are going to be presented and, afterwards, the control stations properties. 5.2.1.1 Vehicles Model Following Figure 28, the vehicles architecture is as presented in Figure 31. The objects will be explained bellow:  Vehicle (Physical Entity): 42 Approach Figure 36 – Composed Service and Service conceptual model applied to Control Station and Vehicle conceptual model This does not have to be done, necessarily, by means of a nested controller, on the Service component, but by sending objectives to the components that are in charge of controlling the desired component. For example, at Figure 34, in the “GoingToComsLoc” step from the “Relay” Service, it has to send the objective “Goto(Relay Location)” to the navigator component that will drive the vehicle through a “Goto” manoeuvre to the location “Relay Location”. The step is considered complete as soon as the navigator indicates that the actual location is the one sent as objective, “Relay Location”, and this would trigger the following step, “ReceivingFromGather”.  When a Service Step has a dependency on another Service Step, it means the “master” Service Step triggers the end of the “slave” Service Step Once the vehicle, executing the “Relay” Service, starts the “ReceivingFromGather” step, it waits for a communication link from the vehicle executing the “SendingtoRelayer” step. This vehicle establishes the link and, after transmitting the data, the step is over. At this point, the “ReceivingFromGather” step ends. -Goals Specification -State(Agent ID) Composed Service -Goals Specification -Assignment Attributes -State(Agent ID) Service 2 11..* Has4 -Goals Specification -Assignment Attributes -State(Agent ID) Service 1 11..* Has4 -Goals Specification -Assignment Attributes -Service(ID) Service 1 -Goals Specification -Assignment Attributes -Service(ID) Service 2 Control Station Vehicle 1 Vehicle 2 1 1..* Has4 1 1 Has4 1 1Has4 1 1 Has4 Service 1 Execution Steps 1 1 Has4 Service 2 Execution Steps assigns triggers Notation: Control Station Composed Service model Vehicle Service model Vehicle Service model Composed Service model Europa Application 43 5.4 Europa Application Developing EUROPA applications is a design job that involves multiple iterations from an initial concept model to an actual NDDL encoding. A good approach is to gradually build up a domain description adding more detail methodically [29]. This approach was inspired by the approach provided at [29], where a simple planetary rover application is provided. 5.4.1 Application Domain Analysis The first stage was to draw a concept map of the entities in the application domain and their relationships. This has been done in section 5.3, where a concept map for the system application domain was presented (Figure 35). The concept map focused on modelling the main entities, control stations, services and vehicles, and their interactions. The next step was to identify the entities called timelines in the model application concept diagram that describe changes in the state of the system:  Composed Service – manages the assigning, execution and conclusion of the Composed Service  Service (Control Station) – manages the assigning, execution and conclusion of the Service  Service (Vehicle) – manages the execution sequence  Service Steps – manages the vehicle execution of the Service Steps  Vehicle – controls the assignment of a vehicle to a Service and a Composed Service  Navigator – controls the vehicle’s movements  Navigator State – manages the state of the vehicle navigation  Communications – controls the communication’s actions  Payload – controls the payload’s actions  Payload State – manages the assignment of a vehicle payload to a service The next step is to identify the states, predicates, which each timeline can be in. Some of these have already been approached in the previous sections. Figure 37 shows the set of predicates identified for each timeline, as described below:  Composed Service – a Composed Service can be Available, Requested, Executing or Completed 44 Approach Figure 37 – Initial timelines and predicates  Service (Control Station)– a Service, on the Control Station model, can be Unassigned, Assigning, Assigned, Executing or Completed  Vehicle State – a vehicle can be Unassigned, Assigned or Executing a Service  Service (Vehicle) – a Service, on the Vehicle model, can be Unassigned, Assigned, Executing or Completed  Service Steps – the steps sequence the vehicle will perform when assigned and executing a Service. Each predicate matches a step  Navigator – a vehicle either is going to a location or maintaining at a position (loitering) Composed Service Available Requested Executing Completed Service (Control Station) Unassigned Assigning Assigned Executing Completed ServiceV (Vehicle) Unassigned Assigned Executing Completed ServiceV Steps Action 1 Action 2 ... Action n Navigator Going Loitering Navigator State Underwater Abovewater Payload Unassigned Assigned PayloadActs Acting 1 Acting 2 ... Idle Comms Acting 1 Acting 2 ... Idle Vehicle Unassigned Assigned Executing Europa Application 45  Navigator State – a vehicle can be underwater or above water (abovewater)  Communications – a vehicle or a control station can be communicating with other vehicles or idling. Each predicate matches a different communication action  PayloadActions – a vehicle payload can be either at use or idling. Each predicate matches a different payload action  Payload – a vehicle payload can be assigned to a service or unassigned(free to be assigned in a Service)1 1This will become important if vehicles execute different Services at once, where no payload restrictions conflicts can occur, and so a payload can only be assigned to one Service. The next and final step is to detail the properties of the predicates and the constraints between them. The use of constraints between the predicates has the function to define acceptable behaviour for the system and to disallow the unacceptable one, as it will be seen next. The predicates properties are going to be detailed carefully in section (5.4.2), but they are no more than the attributes already defined in the models (sections 5.2.1,5.2.2 and 5.3). Figure 38 shows the constraints for a Composed Service request, executing and completion. The temporal relations between the timelines map the service model specification and properties, sections 5.2.2 and 5.3:  For a Composed Service to be Executing all the Services have to be Assigned  A Service has to be Assigned to a Vehicle Unassigned to a Service  The assignment of the Vehicle to a Service, in the Control Station model, will trigger the state of the Service, in the Vehicle model, to Assigned as well, and it is required that the Service is Unassigned  When all Services are Assigned, the Composed Service can start Executing and this triggers the Services state, in the Control Station model, to be Executing, and consequently this triggers the Vehicle state and the Services state, in the Vehicle model, to Executing as well  As soon as the Service state goes Executing, the Service Steps sequence will start  When the last step is performed, the Service Executing state will end and this triggers the Vehicle state to Unassigned, and consequently this triggers the Service state, in the Control Station model, to Completed 46 Approach  When all Services are Completed, the Composed Service becomes Completed as well The Vehicle model also has some constraints among their components, as shown in Figure 39:  The Communications Actions have to occur not only while the Vehicle is Executing a Service, but also while the Vehicle is Abovewater. This is important to underwater vehicles because while submerged they cannot communicate.  Actions succeed and precede the Idle state In what concerns the Navigator:  The Going manoeuvre also has to occur when the Vehicle is Executing a Service, since the orders to move come from the Service Steps.  A Going manoeuvre is preceded by a Loitering manoeuvre, that represents the act of being at a fixed location, and meets another Loitering, but in a different location.  The Navigator state derives from the Vehicle position. When being at a position (only for underwater vehicles), if the depth becomes below zero, the state becomes Underwater. The opposite triggers the Abovewater state. Each state follows the other. The Vehicle Payload constraints are shown in Figure 40:  When a Vehicle is Assigned to a Service, as explained before, specific Payload, derived from the Service specification, can be required to be Assigned as well. In this circumstance the Service, in the Vehicle model, will trigger the assignment of the specified Payload. In this circumstance the specified Payload should become Assigned as soon as the Service becomes Assigned.  The Payload has to be Unassigned before becoming Assigned  Every PayloadAction predicate has to occur while the Payload is Assigned, and therefore the Vehicle, to a Service and every action succeeds and precedes the Idle state Europa Application 47 Figure 38 - Timelines and predicates with transitions between them – Composed Service request, executing and completion constraints Figure 39 – Timelines and predicates with transitions between them – Vehicle model constraint Vehicle Composed Service Available Requested Executing Completed Service Unassigned Assigning Assigned Executing Completed ServiceV Unassigned Assigned Executing starts starts met by met by met by meets contains met by met by met by met by contains contains start Unassigned Assigned Executing met by met by contains contains meets met by meets met by meets met by ServiceV Steps Step 1 Step 2 ... Step n starts meets meets meets ends ends Navigator Loitering Going Navigator State Underwater Abovewater Comms Acting 1 Acting 2 ... Idle starts starts contained bycontained by meets met by Vehicle Unassigned Assigned Executing met by met by met by met by met by contained by contained bycontained by met by met by meets meets 48 Approach Figure 40 - Timelines and predicates with transitions between them: Payload assignment and actions Figure 41 – Timelines and predicates with transitions between them: constraints for a Gather Step, one possible step of a Service Steps execution sequence Figure 41 shows an example of the constraints between a Service Steps timeline predicate (step Gather) and other timelines predicates that are related to the step. The contained by constraint specifies that the Vehicle must be Loitering, at a specific Location, for the duration of the step in order to be able to Sample at the specified Location. The constraint with the Payload timeline shows that when the step starts the Payload action must begin and when the action ends the step also ends, being the Gather step duration equal to the action of Sample. Payload Assigned Unassigned Payload Actions Acting 1 Acting 2 ... Idle starts ends contained bycontained by met by met by meets meets met by met by ServiceV Unassigned Assigned Executing met by met by meets ServiceV Steps Gather Navigator Going Loitering Payload contained by equals met by met by Sample Idle met by met by Step before Step after meets meets Europa Application 49 5.4.2 NDDL Encoding At this section, each model file will be stepped thought and explained how it derived from the analysis made. The encoding presented is the generic approach made on the models and a real application may need some changes. In Chapter 6, an example application is presented. 5.4.2.1 Defining the Vehicle Model Timelines Encoding the components of the vehicle, first the Navigator is presented. It manages the Vehicle navigation and has a NavigatorState attribute. This class contains the two predicates identified earlier. The Loitering predicate models the concept of the vehicle being at a particular Location Loitering. The Going predicate models the concept of moving between Locations. The neq construct is a constraint that ensures the vehicle does not attempt to go to the actual position. 1 class Navigator extends Timeline 2 { 3 Vehicle vehicle; 4 NavigatorState state; 5 6 Navigator(Vehicle v) { 7 vehicle = v; 8 state = new NavigatorState(this); 9 } 10 11 predicate Loitering {Location at;} 12 13 predicate Going { // Vehicle may be going between two locations 14 Location from; 15 Location to; 16 neq(from, to); // prevents vehicle from going from a location straight back to that location 17 } 18 } List 1 – class Navigator The NavigatorState timeline has two predicates declared but have no accompanying logic. The only constraint is that they occur on a single timeline, so cannot overlap. 1 class NavigatorState extends Timeline 2 { 3 Navigator nav; 4 5 NavigatorState(Navigator n) { 6 nav = n; 7 } 8 9 predicate Underwater {} 10 predicate Abovewater {} 11 } List 2 – class NagivatorState Payload timeline itself details the assignment of the Vehicle Payload to Services. It has three attributes: the Vehicle the Payload belongs to, the type of Payload it is (pType) and 50 Approach contains the PayloadActs timeline. The Assigned predicate has the parameter pType that specifies the Service the payload is assigned to. 1 class Payload extends Timeline 2 { 1 Vehicle vehicle; 2 pType ptype; 3 PayloadActs actions; 4 5 Payload(Vehicle v, pType st) { 6 vehicle = v; 7 ptype = st; 8 actions = new PayloadState(this); 9 } 10 11 predicate Unassigned {} 12 predicate Assigned { tType ttype;} 13 } List 3 – class Payload The PayloadActs timeline details the management of the vehicle’s Payload actions. It has an attribute that maps the Payload to which the actions refer to. The predicates map the possible Payload actions the vehicle has, being a specific Location a parameter. The predicate Idle maps the state when the Payload is not acting. 1 class PayloadActs extends Timeline 2 { 3 Payload payload; 4 5 PayloadActs(Payload p) { 6 payload = p; 7 } 8 9 predicate Idle {} 10 predicate Action 1 { Location at;} List 4 – class PayloadActs The Communications timeline is very similar to the PayloadActs. The difference is that the attribute maps the Vehicle to which the Communications system belongs to and the actions parameters are a Vehicle and a Location specification. 1 class Comms extends Timeline 2 { 3 Vehicle vehicle; 4 5 Comms(Vehicle v) { 6 vehicle = v; 7 } 8 9 predicate Idle{} 10 predicate Action 1 { 11 Location location; 12 Vehicle vehicle_to; 13 } 14 } List 5 – Class Comms Europa Application 51 Finally, the Vehicle class puts together all the components defined in this section and manages the assignment (Assigned) and execution (Executing) to Services. It has several attributes, among them the Payload, Navigator and Communications classes, and the Vehicle Services specification (svType). The Assigned and Executing predicates have the the parameter svType that specifies the Service the Vehicle is Assigned to and Executing. 1 class Vehicle extends Timeline //class vehicle 2 { 3 string id; //vehicle identification 4 vType type; //vehicle type 5 float maxVel; //vehicle max velocity 6 Payload payload; //vehicle payload system 7 Navigator navigator; // Keeps track of vehicle's position 8 Comms comms; //vehicle communications system 9 svType svtype; //vehicle service types 10 11 Vehicle(string i, vType t, float mv, svType svt) { 12 id = i; 13 svtype = svt; 14 maxVel = mv; 15 navigator = new Navigator(this); 16 comms = new Comms(this); 17 payload = new Payload(this); 18 ttype = tt; 19 } 20 21 predicate Unassigned {} 22 predicate Assigned { svType svtype;} 23 predicate Executing { svType svtype; } 24 } List 6 – class Vehicle Going through the Vehicle predicates, it is simple to understand that they are declared but have no accompanying logic. The only constraints are that they cannot occur at the same time and they have a defined order through which they must happen. The parameter tType that the Assigned and Executing predicates have is defined when the Task is Assigned (see List 21). 1 Vehicle::Unassigned 1 { 2 met_by(Executing); 3 } 4 5 6 Vehicle::Assigned 7 { 8 met_by(Unassigned); 9 } 10 11 Vehicle::Executing 12 { 13 met_by(Assigned); 14 meets(Unassigned); 15 } List 7 – Predicates from Vehicle class The Navigator predicates, as said before, are Loitering and Going. The first has just the precedent condition that it must be met by a Going manoeuvre, which means that for being at a Location the Vehicle had to go there. This predicate also manages the NavigatorState 58 Approach 1 class ServiceVSteps extends Timeline 2 { 3 ServiceV servicev; 4 5 ServiceVSteps(ServiceV sv) 6 { 7 servicev = sv; 8 } 9 10 predicate Action1 11 { 12 Manoeuvre manoeuvre; 13 CommsAct commsact; 14 PayloadAct payloadact; 15 Goals goals; 16 } 17 18 } List 25 – ServiceVSteps class Next, the definitions of the ServiceV predicates are introduced. They will be very familiar from the previous predicates. The Assigned predicate has the Unassigned state as precedent condition and a parameter (svType) that maps the ComposedService to which it was Assigned. If the Service has a Payload requirement, which means the Vehicle Assigned to the ServiceV has it. This predicate has an additional condition: it triggers the specified Payload predicate to Assigned. 1 ServiceV::Assigned 2 { 3 met_by(Unassigned); 4 any(object.vehicle.Assigned assigned) 5 assigned.ptype == ptype; 6 7 Payload payload; // If the Service has a payload requirement 8 payload.ptype == ptype; //identifies the payload 9 payload.vehicle == object.vehicle; //identifies the vehicle the payload belongs to 10 starts(payload.Assigned); 11 12 } List 26 – Assigned predicate from ServiceV class The Executing predicate is preceded by the Assigned one. The execution of the Service has, as said before, an action sequence, and so, in the Executing predicate, the first action is triggered. It can be seen that Action1 starts along with the predicate and that Action3 ends the Service execution. This triggers not only the ServiceV predicate Unassigned, but also ends the Vehicle assignment. In this predicate the Goals of the first action are also specified, and they derive from the Goals parameter or the identification of the Vehicles Assigned to the other ComposedService Services. Again, if the ServiceV has a Payload requirement, which means the Vehicle Assigned to the Service has it. This predicate has an additional condition: it triggers the Payload predicate to Unassigned. Europa Application 59 1 ServiceV::Executing 2 { 3 met_by(Assigned assigned) 4 assigned.ptype == ptype; 5 starts(object.steps.Action1 a1); //starts the first action 6 a1.actgoal == goal1; 7 8 any(object.steps.Action3 a3); //last action 9 10 this.end == a3.end; 11 any(object.vehicle.Assigned a); 12 a.end == this.end; 13 meets(Unassigned); 14 15 Payload payload; // If the Service has a payload requirement 16 payload.ptype == ptype; 17 payload.vehicle == object.vehicle; 18 starts(payload.Assigned); 19 } List 27 – Executing predicate from ServiceV class The ServiceVSteps predicates follow the same logic of the predicates presented, but their conditions vary depending on its specification. The encoding presented here maps the Gather action shown in Figure 41. The contained by constraint ensures the vehicle is Loitering at the Goal, being this goal a Location, and the equals constraint ensures that the Payload indeed takes the Sample (being Sample a PayloadActions), and that it is taking a sample at the correct Location. 1 ServiceVSteps::Gather 2 { 3 contained_by(vehicle.navigator.Loiter loiter); 4 loiter.at == actgoal; 5 6 equals(vehicle.payload.actions.Sample sample); 7 sample.goal == actgoal; 8 } List 28 – Possible action from ServiceVSteps class 60 Approach 61 Chapter 6 Results In this chapter, the global results for the model application are discussed. The model was applied following the specifications presented in Chapter 5. 6.1 Simulation Examples The model, as said in Chapter 4, was developed with the objective to define composed operations capable of providing specific system entities with the planning knowledge to establish them, and to provide support on system state capture for advanced missions. To get a better understanding on how the model is supposed to work on a real world multi-vehicle system, the model was applied to some operational scenarios examples. 6.1.1 Operational Scenario 1 A ground team (Team 1) wants to conduct a water temperature measure operation in specific locations. Team 1 fleet, a heterogeneous fleet, is composed by two UAV and three AUV’s. Each one of these vehicles has a specific configuration. The team has some tight timing constraints that complicate their planning job:  They need the water temperature information to be at their location before time T=85 And due to the AUV’s velocity it is not possible to send them to all locations, get the samples, and have them at their location to transmit the data on time. Their solution is to use a fast relay vehicle, as the UAVs. But:  The UAV1 is only available after time T=20 and UAV2 is unavailable to relay 62 Results 6.1.2 Operational Scenario 2 This scenario is similar to the presented earlier, but in this case Team 1 wants to conduct both the water temperature measure operation and turbidity level measure operation in different locations. This time Team 1 has just the timing constraint to get all the data before time t=100. As in the scenario before the UAV is going to be used as a relay vehicle and the two AUV’s are going to conduct the gather operations, being each assigned to one operation depending on its specification. 6.1.3 Operational Scenario 3 This last scenario assumes Team 1 wants again a water temperature measure and a bathymetry operation, but there is a need to get the bathymetry data in a different time then the temperature data:  They need the bathymetry data to be at their location before time T=200  They need the temperature data to be at their location before time T=200 Again, as in the scenarios before UAVs are going to be used as relay vehicles and AUVs as gather vehicles. 6.1.4 World Description The world is assumed to be a Euclidean space grid, where the concept location was encoded in the Location class. The class has three attributes. The name is a symbolic name for the location and the id is an identification to distinguish between same name locations. The x, y and z attributes are coordinates. A vehicle can just move on one axis at each step. 1 class Location // A point on the planet's surface 2 { 3 string name; 4 int id; 5 int x; 6 int y; 7 int z; 8 9 Location(string _name, int _id, int _x, int _y, int _z) { 10 name = _name; 11 id = _id; 12 x = _x; 13 y = _y; 14 z = _z; 15 } 16 } List 29 – class Location Simulation Examples 63 Six agents populate the world, being each one of them defined following the proper model architecture (see section 5.2.1and 5.4.2.1):  CS1 Figure 42 – CS1 model and attributes  UAV1 Figure 43 - UAV1 model and attributes  UAV2 Figure 44 – UAV2 model and attributes -ID: cs01 -Composed Service: Sampling -Position: loc_CS01 Control Station 1 1 Has4 Sampling Communications 1 1 Has4 -ID: v01 -Type: UAV -Payload: - -Tasks: Relay -Movement Restrictions: 0,1 -Operational Autonomy: 100 UAV1 Navigator Communications Has4 Has4 Relay Has4 State Has4 -ID: v02 -Type: UAV -Payload: - -Tasks: Relay -Movement Restrictions: 0,05 -Operational Autonomy: 60 UAV2 Navigator Communications Has4 Has4 Relay Has4 State Has4 64 Results  AUV1 Figure 45 – AUV1 model and attributes  AUV2 Figure 46 – AUV2 model and attributes  AUV3 Figure 47 – AUV3 model and attributes -ID: v03 -Type: AUV -Payload: CTD -Tasks: Gather -Movement Restrictions: 1 -Operational Autonomy: 1000 AUV1 Navigator Communications Has4 Has4 Gather Has4 CTD Has4 State Has4 -ID: v04 -Type: AUV -Payload: Sonar -Tasks: Gather -Movement Restrictions: 0.5 -Operational Autonomy: 500 AUV2 Navigator Communications Has4 Has4 Gather Has4 Sonar Has4 State Has4 -ID: v05 -Type: AUV -Payload: Turbidity -Tasks: Gather -Movement Restrictions: 0.8 -Operational Autonomy: 800 AUV3 Navigator Communications Has4 Has4 Gather Has4 Turbidity Has4 State Has4 Simulation Examples 65 1 //Creating the world objects 2 ControlStation CS1 = new ControlStation ("cs01", cs_sampling,loc_CS1); //CS1 3 Sampling CS1_sampling = new Sampling (CS1); 4 Vehicle UAV1 = new Vehicle("v01",UAV,none,0.1,s_relay); //UAV1 5 RelayV UAV1_relay = new RelayV(UAV1); 6 Vehicle UAV2 = new Vehicle("v02",UAV,none,0.1,s_relay); //UAV2 7 RelayV UAV2_relay = new RelayV(UAV2); 8 Vehicle AUV1 = new Vehicle("v03",AUV,1,s_gather); //AUV1 9 Payload AUV1_CTD = new Payload(AUV1,CTD); 10 GatherV AUV1_gather = new GatherV(AUV1); 11 Vehicle AUV2 = new Vehicle("v04",AUV,0.5,s_gather); //AUV2 12 Payload AUV2_Sonar = new Payload(AUV2,Sonar); 13 GatherV AUV2_gather = new GatherV(AUV2); 14 Vehicle AUV3 = new Vehicle("v05",AUV,0.8,s_gather); //AUV3 15 Payload AUV3_ Turbidity = new Payload(AUV2, Turbidity); 16 GatherV AUV3_gather = new GatherV(AUV3); List 30 – Creating the world objects And the world was configured to have several different locations:  CS1 location: where the CS1 is (the same location as UAV1 and UAV2)  AUV’s location: where the AUV1, AUV2 and AUV3 are at initial time  Relay location: where the vehicles should meet to relay the data from one to another  CTD Gather locations: six locations to conduct the temperature measure  Sonar Gather locations: three locations to conduct the bathymetry measure  Turbidity Gather locations: three locations to conduct the turbidity measure 1 //Creating the world locations 1 Location loc_CS1 = new Location(“CS1L”, 0, 0, 0); 2 Location loc_relay = new Location(“RL”, 18, 19, 0); 3 Location loc_UAVS = new Location(“UAVL”, 16, 16, 0); 4 Location loc_CTDgather1 = new Location(“CTD”, 1, 18, 18, -5); 5 Location loc_CTDgather2 = new Location (“CTD”, 2, 19, 18, -5); 6 Location loc_CTDgather3 = new Location (“CTD”, 3, 20, 18, -5); 7 Location loc_CTDgather4 = new Location (“CTD”, 4, 20, 19, -5); 8 Location loc_CTDgather5 = new Location (“CTD”, 5, 19, 19, -5); 9 Location loc_CTDgather6 = new Location (“CTD”, 6, 18, 19, -5); 10 Location loc_Sonargather1 = new Location(“Sonar”, 1, 18, 20, -5); 11 Location loc_Sonargather2 = new Location (“Sonar”, 2, 19, 20, -5); 12 Location loc_Sonargather3 = new Location (“Sonar”, 3, 20, 20, -5); 13 Location loc_Sonargather3 = new Location (“Sonar”, 4, 19, 18, -5); 14 Location loc_Turbgather3 = new Location (“Turbidity”, 1, 21, 18, -5); 15 Location loc_Turbgather3 = new Location (“Turbidity”, 2, 21, 19, -5); 16 Location loc_Turbgather3 = new Location (“Turbidity”, 3, 21, 19, -5); List 31 – Creating the world locations 66 Results 6.1.5 Initial State 6.1.5.1 Operational Scenario 1 The initial system state is created by placing tokens on the objects created. It is assumed that at time zero:  Each Vehicle is at the positions referred before  Each Vehicle state is Unassigned (see List 7), although UAV1 has to be Unassigned until time T=20  Sampling ComposedService is Available (see List 16) 1 //ComposedService available at time 0 2 fact(CS1_SAMPLING1.Available sampling_available); 3 eq(CS1_SAMPLING1_available.start,0); 4 //UAV1 can only be assigned to a Service after time 20 and the other vehicles can be assigned after time 0 5 fact(UAV1.Unassigned UAV1_unassigned); 6 eq(UAV1_unassigned.start,0); 7 lt(20, UAV1_unassigned.end); 8 fact(UAV2.Unassigned UAV2_unassigned); 9 eq(UAV2_unassigned.start,0); 10 fact(AUV1.Unassigned AUV1_unassigned); 11 eq(AUV1_unassigned.start,0); 12 fact(AUV2.Unassigned AUV2_unassigned); 13 eq(AUV2_unassigned.start,0) 14 fact(AUV3.Unassigned AUV3_unassigned); 15 eq(AUV3_unassigned.start,0); 16 //Positioning the vehicles at initial position at time 0 17 fact(UAV1.navigator.Loiter UAV1IniPosition); //UAV1 18 eq(UAV1IniPosition.start, 0); 19 eq(UAV1IniPosition.location, loc_delivery); 20 fact(UAV2.navigator.Loiter UAV2IniPosition); //UAV1 21 eq(UAV2IniPosition.start, 0); 22 eq(UAV2IniPosition.location, loc_delivery); 23 fact(AUV1.navigator.Loiter AUV1IniPosition) ; //AUV1 24 eq(AUV1IniPosition.start, 0); 25 eq(AUV1IniPosition.location, loc_UAVS); 26 fact(AUV2.navigator.Loiter AUV2IniPosition); //AUV2 27 eq(AUV2IniPosition.start, 0); 28 eq(AUV2IniPosition.location, loc_UAVS); 29 fact(AUV3.navigator.Loiter AUV3IniPosition); //AUV3 30 eq(AUV3IniPosition.start, 0); 31 eq(AUV3IniPosition.location, loc_UAVS); List 32 – Defining the initial state, operational scenario 1 And the goal is defined as having the Sampling ComposedService Completed between time 0 and 70. The ComposedService parameters are also defined. 1 //Defining the goals 2 goal(CS1_SAMPLING1.Completed goal1); 3 goal1.ptype == CTD; //Defining the gather payload 4 lt(0,goal1.start); 5 lt(goal1.start,85); List 33 – Defining the goals – Operational Scenario 1 Solver Results 67 6.1.5.2 Operational Scenario 2 The same initial state as the scenario before but with a different composed service, it has two gather services and one relay service, and the UAV1 has no restrictions. The goals are: 1 goal(CS1_DOUBLESAMPLING.Completed goal3); 2 goal3.gather1_stype == Turbidity; 3 goal3.gather2_stype == Sonar; 4 lt(0,goal3.start); 5 lt(goal3.start,100); List 34 – Defining the goals – Operational Scenario 2 6.1.5.3 Operational Scenario 3 The same initial state as the scenario before but with two composed services equal to the composed service at scenario 1. The goals ares: 1 goal(CS1_SAMPLING1.Completed goal1); 2 goal1.ptype == CTD; //Defining the gather payload 3 lt(0,goal1.start); 4 lt(goal1.start,200); 5 6 goal(CS1_SAMPLING2.Completed goal2); 7 goal1.ptype == Turbidity; //Defining the gather payload 8 lt(0,goal2.start); 9 lt(goal2.start,200); List 35 – Defining the goals – Operational Scenario 3 6.2 Solver Results The scenarios were solved using the standard EUROPA solver. It assumes a chronologicalbacktracking, heuristically guided, refinement search. The solver window shoes the number of step decisions made (Step Count) as well as the deliberative time to output the plan (Run time). The tree consecutive window inside the solver window show the deliberative time at each step (Time (secs) per Step), the decisions to be made to achieve the goal (Open Decision Count) and the decisions made to output the plan (Decisions in Plan). It is important to highlight that when a plan is successfully generated the Open Decision Count gets to zero. From the comparison of the solver decisions (Figure 48, Figure 49 and Figure 50) it is possible to observe that the solver takes more time to plan when the decisions to be made to output a plan are bigger. At these three scenarios it is possible to see that the solver gets to the solution without backtracking any solution (the decisions in plan always grow with the time). Figure 50 shows that in scenario 3 the solver has to backtrack some decisions and consequently increases the deliberative time for those decisions. It is possible to see that the 74 Results 75 Chapter 7 Conclusions and Future Work 7.1 Summary This thesis started with the objective to develop a new model for standardization of cooperative operations plans along with providing support on defining the system state for complex mission. In order to accomplish this proposes, the following steps were made:  Initial study of the background of multi-vehicles network, in order to understand the main motivations on deploying multi-vehicles systems  Analysis of vehicle cooperative missions to understand how these are currently deployed  State of the Art review, to comprehend and learn from what have been developed on past researches on multi-vehicle systems and planning paradigms  Understand the crucial requirements when capturing a system state  Build initial models for the system entities based on those requirements  Think of how cooperative configurations could be composed in a model  Build an initial cooperative concept model  Developing each model step by step, involving multiple iterations, until reaching a desired complete, combined model  After having the initial concept model, encode the model, also involving multiple iterations 76 Conclusions and Future Work  Finally, some simulations were made on the model to prove its consistency and the new introduced concepts 7.2 Model Evaluation The model is going to be evaluated and analyzed along with the multi-vehicle issues presented at section 3.1.5.  System model: o Is there a defined control hierarchy? How is it defined?  There is a control hierarchy defined thought the Composed Service model where the goals are sent top down the model and the low nodes results/achievements are sent to the upper nodes. o Does cooperation exists? Is it crucial in achieving system goals?  Cooperation is also defined thought the Composed Service model with the specification of where each Service interacts with another. This creates a Service dependency that is essential to the system to achieve the goals. o Does cooperation between agents forms an agent composed model? What benefit comes from achieving the composed model? Who knows when a model is composed?  As described in the last two points, agents’ cooperation is defined through the Composed Service model. When a Composed Service model is achieved, an additional feature becomes available in the system, being its achievement managed by the requesting agent. This agent has the Composed Service specification knowledge. o What and where are the communicating structures?  The communicating structures belong to any agent that implements a communicating system, as vehicles and control stations. o Problem-solving Strategy: How are system goals distributed and broken down to sub goals? Are all goals defined in the planning phase?  As said before the goals are distributed top down along the Composed Service model, being the goals distribution defined in the Composed Service specification. Some goals are defined in the planning phase while others arise while executing. Model Evaluation 77  System domain and environment assumptions: o How is the system domain characterized?  The system domain is composed by all the agents and their components, being physical entities, computational agents or abstract concepts o What a priori knowledge do agents have about other agents?  Service requesting agents need to know the other agents configuration o How is problem solving knowledge shared among agents?  The structure of knowledge differs between agents and algorithms or procedures may be entirely different. o Is the system domain dynamic? What features may vary along time?  The system domain may vary, although the problem solving always refer to the initial domain state used  Fault tolerance: o What possible failures are assumed to be possible?  No possible failures are assumed at the moment o How does the system deals with faults?  No fault tolerance system has been developed. o Is predictive timing information available?  Timings are known or computed at various levels of accuracy at the start of problem solving. o Are there tasks deadlines?  Task deadlines are introduced at the planning phase.  Communication importance: o How are the communication paths specified?  Agents know who they may communicate with beforehand, but the order and contents of that communication are not pre-specified. 78 Conclusions and Future Work o How are messages addressed?  A full range of methods is available to use depending on the situation (desirable). o What information do agents use to determine the when, whom, and what of communication?  A combination of long-term, fixed knowledge and local knowledge developed during problem solving. 7.3 Achieved Goals The proposed initial objective was successfully achieved. A model was developed that could provide a standardization for planning composed cooperative operations, providing system with the knowledge of how to achieve known composed operations, and improve the system state capture. The main contribution this work lays down on multi-vehicle systems is:  Standardized composed cooperative operations models, which specify how these are achieved and how its execution flows, provide systems with the planning capacities to successfully output complex plans Although the model proved to achieve good results on the scenarios described, there are some weaknesses on the implementation provided, as already seen on the previous section:  The scenarios are assumed to be unchanged over planning and execution time, what means no new objects can be created after the initial state is defined  It is not possible to implement a service to map complex cooperative networks, as for example flight formation controllers. Although, it would be possible to define a service that would request the execution of a flight formation controller with specific parameters and time restrictions  When the model objects increase and consequently the decisions to be made to output a plan, the computational effort along with the time consumed also increase  At the moment, there is no fault-tolerance, although the outputted plans have temporal windows where actions have to happen, which may solve some minor temporal issues as moving and actions executing delays Future Work 79 7.4 Future Work The multi-vehicle system is a growing research area with much improvements and developments to be done. This work presented a new approach on planning complex operations with some level of cooperation and even though the model provided a good answer for the simulated operational scenarios a lot of improvements and further developments have to be done, among them: 1. Continue to grow the model to fit more complex operations and develop a connection that could bring complex controllers, as flight formation, persistence surveillance, obstacle avoidance, into the planning loop 2. Along with the above point, it would be important to implement the model such that it could deal with dynamic environments, adding a re-planning feature 3. Deal more detailed with the communications issues that were not considered during this work, as already approached in the last section. How messages are addressed between the communication structures? How are the communication paths specified? How to deal with communication losses? Among other issues that certainly arise when operating real world scenarios 4. Shape the model to be implemented with the current onboard deliberative planning tool chain available at LSTS: the TREX teleo-reactor executive and the EUROPA planner [40] 5. Field-tested the model, from a simple to a more complex version to prove its effectiveness when planning real world scenarios 80 Conclusions and Future Work 81 References [1] P. D. E. Investiga, T. E. M. Ve, and R. Aut, “II Série Cadernos do IDN,” vol. 2008, pp. 9–24, 2009. [2] F. L. Pereira, P. F. Souto, and L. Madureira, “DISTRIBUTED SENSOR AND VEHICLE NETWORKED SYSTEMS FOR ENVIRONMENTAL APPLICATIONS,” no. May 2003, pp. 1–6, 2010. [3] J. Pinto, P. S. Dias, R. Gonçalves, E. Marques, G. Gonçalves, J. B. Sousa, and F. L. Pereira, “Neptus – A Framework to Support a Mission Life Cycle,” in 7th IFAC Conference on Manoeuvring and Control of Marine Craft, 2006. [4] “Laboratório de Sistemas e Tecnologia Subaquática.” [Online]. Available: http://whale.fe.up.pt/main/tech. [5] M. E. Angelopoulou, R. Martins, J. B. de Sousa, S. Chatzichristofis, L. Doitsidis, M. Kothari, M. G. Lagoudakis, L. Panagiotopoulou, M. Petrou, V. S. Prabhu, P. B. Sujit, and C. Tsiotsios, “NOPTILUS : System Specifications,” 2012. [6] P. S. Dias, R. M. F. Gomes, and F. L. Pereira, “Mission Planning and Specification in the Neptus Framework,” no. May, pp. 3220–3225, 2006. [7] M. Correia, P. Dias, S. Fraga, R. Gomes, R. Goncalves, L. Madureira, F. L. Pereira, R. Picas, J. Pinto, A. Santos, A. Sousa, and J. B. de Sousa, “OPERATIONS AND CONTROL OF UNMANNED UNDERWATER VEHICLES,” 2005. [8] R. Martins, P. S. Dias, E. R. B. Marques, J. Pinto, J. B. Sousa, and F. L. Pereira, “IMC: A communication protocol for networked vehicles and sensors,” Oceans 2009-Europe, pp. 1–6, May 2009. [9] S. A. Bortoffl, S. Lane, and E. C. T. Hartford, “Path Planning for UAVs,” no. June, 2000. [10] Y. E. H. Bang, “Cooperative Control of Multiple Unmanned Aerial Vehicles Using the Potential Field Theory.” 2006. [11] Y. E. H. Bang, “Cooperative Task AssignmentPath Planning of Multiple Unmanned Aerial Vehicles Using Genetic Algorithm.” 2009. [12] Z. Hu, M. Zhao, and M. Yao, “Cooperative Attack Path Planning for Unmanned Air Vehicles Swarm Based on Grid Model and Bi-level Programming Grid-based Space Division Coordinated Attack Model by Bi-level Programming,” vol. 4, no. 2009, pp. 671–679, 2011. 82 References [13] T. Schouwenaars, B. D. Moor, E. Feron, and J. How, “MIXED INTEGER PROGRAMMING FOR MULTI-VEHICLE PATH PLANNING.” [14] S. Leary, M. Deittert, and J. Bookless, “Constrained UAV Mission Planning : A Comparison of Approaches,” pp. 2002–2009, 2011. [15] A. B. M. I. L. Pollini, “Cooperative Task Assignment Using Dynamic Ranking,” pp. 5712– 5717, 2008. [16] W. A. I. R. F. Base, “UAV TASK ASSIGNMENT WITH MIXED-INTEGER LINEAR PROGRAMMING,” 2004. [17] Y. Jin, A. A. Minai, and M. M. Polycarpou, “Cooperative Real-Time Search and Task Allocation in UAV Teams.” [18] J. Tao and Y. Tian, “Cooperative Task Allocation for Unmanned Combat Aerial Vehicles Using Improved Ant Colony Algorithm,” pp. 1220–1225, 2008. [19] C. Schumacher, M. Pachter, and W. A. I. R. F. Base, “UAV TASK ASSIGNMENT WITH TIMING CONSTRAINTS,” 2003. [20] Z. Papp, C. Brown, and C. Bartels, “World modeling for cooperative intelligent vehicles,” Intelligent Vehicles Symposium, pp. 1050–1055, 2008. [21] H. Kawakami and T. Namerikawa, “Cooperative target-capturing strategy for multivehicle systems with dynamic network topology,” 2009 American Control Conference, pp. 635–640, 2009. [22] M. Zennaro, J. Ko, R. Sengupta, and S. Tripakis, “A service network architecture for a multi-vehicle search mission,” Proceedings of the 40th IEEE Conference on Decision and Control (Cat. No.01CH37228), vol. 2, pp. 1503–1508, 2001. [23] M. Dorigo, V. Maniezzo, and a Colorni, “Ant system: optimization by a colony of cooperating agents.,” IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society, vol. 26, no. 1, pp. 29–41, Jan. 1996. [24] J. B. Ioana Gheţa, Michael Heizmann, Andrey Belkin, “World Modeling for Autonomous Systems,” in KI 2010: Advances in Artificial Intelligence, 2010, pp. 176–183. [25] K. S. Decker, E. H. Durfee, and V. R. Lesser, “Evaluating Research in Cooperative Distributed Problem Solving,” no. August, 1988. [26] D. E. Smith, “Planning as an Iterative Process †.” [27] R. Bart, M. A. Salido, and F. Rossi, New Trends in Constraint Satisfaction , Planning , and Scheduling : A Survey, vol. 00. 2004, pp. 1–24. [28] T. Dean, “Automated planning,” ACM Computing Surveys, vol. 28, no. 1, pp. 85–87, Mar. 1996. [29] “EUROPA.” [Online]. Available: https://code.google.com/p/europa-pso. [30] R. Dechter, I. Meiri, and J. Pearl, “Temporal constraint networks,” Artificial intelligence, 1991. References 83 [31] J. Frank and J. Ari, “Constraint-based Attribute and Interval Planning,” pp. 1–32, 2002. [32] N. Museettola, “HSTS : Integrating Planning and Scheduling,” 1993. [33] J. Barreiro, M. Boyce, M. Do, J. Frank, M. Iatauro, T. Kichkaylo, P. Morris, J. Ong, E. Remolina, T. Smith, and D. Smith, “EUROPA : A Platform for AI Planning , Scheduling , Constraint Programming , and Optimization,” 2004. [34] N. Muscettola, P. P. Nayak, B. Pell, and B. C. Williams, “Artificial Intelligence Remote Agent : to boldly go where no AI system has gone before *,” vol. 103, no. 98, 1998. [35] M. Ai-chang, J. Bresina, L. Charest, J. Hsu, K. J. Ari, B. Kanefsky, P. Maldague, P. Morris, K. Rajan, and J. Yglesias, “MAPGEN Planner : Mixed-initiative activity planning for the Mars Exploration Rover mission,” 2004. [36] D. Tran, S. Chien, R. Sherwood, R. Castano, B. Cichy, A. Davies, and G. Rabideau, “DEMO : The Autonomous Sciencecraft Experiment Onboard the EO-1 Spacecraft,” pp. 1–2, 2005. [37] C. Nicola Muscettola, Ben Smith and and D. Y. Fry, Steve Chien, Kanna Rajan, Gregg Rabideau, “On-board planning for new millenniumdeep space one autonomy,” in IEEE Aerospace Conference, 1997. [38] K. Rajan, “Towards Deliberative Control in Marine Robotics.” [39] J. F. Allen, “Maintaining knowledge about temporal intervals,” Communications of the ACM, vol. 26, no. 11, pp. 832–843, Nov. 1983. [40] P. S. Dias, R. Martins, and E. Marques, “The LSTS Toolchain for Networked Vehicle Systems *.”