Master’s Thesis

Towards Description Logic ReasoningSupport for ALICA

At Distributed Systems Research Group

Stephan Opfer

16th September 2012

Reviewer: Prof. Dr. Kurt Geihs

Advisor: Dr. Hendrik Skubch

For this look in your eyes.

Eidesstattliche Erklarung:Ich versichere, dass ich die Arbeit selbststandig und ohne Benutzung anderer als der angegebenenQuellen und Hilfsmittel angefertigt habe und alle Ausfuhrungen, die wortlich oder sinngemaßubernommen wurden, als solche gekennzeichnet sind, sowie dass die Arbeit in gleicher oderahnlicher Form noch keiner anderen Prufungsbehorde vorgelegt wurde.

Affidavit:I hereby declare that I wrote this thesis on my own and without the use of any other than thecited sources and tools and all explanations that I copied directly or in their sense are markedas such, as well as that the thesis has not yet been handed in neither in this nor in equal format any other official commission.

Kassel, 16th September 2012

Abstract

Providing reasoning support during the modelling of ALICA programs improves the quality ofthe results and the efficiency of the modelling process. Therefore, the applicability of a de-scription logic reasoning support for ALICA is investigated. With SROIQ, one of the mostexpressive description logics is chosen. For a proper judgement of the applicability, three reason-ing tasks of different complexity are implemented. Problems encountered during the ontologyengineering and implementation are highlighted and discussed in detail. Finally, the describedproblems give rise to a choice between two options: Either the provided approach is further im-proved, or another reasoning approach is chosen. Starting points for both options are presented.

III

Contents

Abstract III

1 Introduction and Purpose of the Thesis 1

2 Foundations 52.1 RoboCup Middle Size League . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 A Language for Interactive Cooperative Agents . . . . . . . . . . . . . . . . . . . 62.3 Plan Designer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.4 Description Logics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.4.1 Attributive Language with Complements . . . . . . . . . . . . . . . . . . 122.4.2 The Description Logic SROIQ . . . . . . . . . . . . . . . . . . . . . . . . 132.4.3 SROIQ Cannot Play Domino . . . . . . . . . . . . . . . . . . . . . . . . 15

2.5 Semantic Web Rule Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 Related Work 193.1 Description Logic Supported Planning . . . . . . . . . . . . . . . . . . . . . . . . 19

3.1.1 Taxonomy Supported Planning . . . . . . . . . . . . . . . . . . . . . . . . 193.1.2 AgentSpeak-DL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.1.3 HTN-DL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.2 Football Related Ontologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203.2.1 Region Connection Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . 213.2.2 FootbOWL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.2.3 Tactic Ontology Generation . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4 Implementation 234.1 The ALICA Ontology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.1.1 Well-Formed ALICA Programs . . . . . . . . . . . . . . . . . . . . . . . . 234.1.2 Participation of Agents in ALICA Programs . . . . . . . . . . . . . . . . . 27

4.2 The MSL Ontology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.3 Creation of the ABox Ontology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.4 Reasoning Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.4.1 Cyclic Plans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.4.2 Locality of In Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.4.3 Sound Recursive Task Assignments . . . . . . . . . . . . . . . . . . . . . . 38

4.5 Integration into the Plan Designer . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5 Discussion 435.1 Five Roles for Knowledge Representations . . . . . . . . . . . . . . . . . . . . . . 435.2 Limits of Expressiveness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.3 Open World versus Closed World Assumption . . . . . . . . . . . . . . . . . . . . 455.4 Ontological Overcommitment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

V

Contents

5.5 Domain Specific Reasoning Capabilities . . . . . . . . . . . . . . . . . . . . . . . 47

6 Summary 496.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6.2.1 Improvements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506.2.2 Alternatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

Bibliography 53

List of Figures 63

VI

1 Introduction and Purpose of the Thesis

Multi-Robot Systems are one of the larger research areas in the field of artificial intelligence,because they includes several topics like computer vision, sensor fusion, localisation, mapping,learning, planning, cooperation, communication, coordination, knowledge representation, rea-soning, and a lot more. Focusing on knowledge representation and reasoning, this thesis coversonly a small part of the Multi-Robot Systems research area. Although, listed topics like plan-ning, cooperation, and coordination intersect with this thesis. The context of this thesis ismotivated by some examples of these topics as follows.

Based on the assumption, that each robot wants to achieve a certain goal, the robots often haveto coordinate their actions. For example, robots pursuing the same goal could build teams, inorder to parallelise their work and thereby achieve their goal faster. In such cases, the robotshave to assign tasks to themselves, so that each robot is capable of fulfilling its task and eachrobot beliefs in the same task assignment. Otherwise, some tasks would be done multiple timesand other tasks would not be done at all. Another case, which require cooperation, is a task,which demands for several robots to help each other. For example, surveilling an area, whichis larger than the sensor range of a single robot, demands for a team of robots to cover thecomplete area. In general, it is expected that goals need several tasks to be fulfilled, in orderto be achieved. Furthermore, the number of tasks is considered to be larger than the numberof robots, which aim to achieve the goal. As a consequence, each time a task is finished by asingle robot or a group of robots, all robots have to agree on a new task assignment. They alsopotentially start a new cooperation with a newly formed group of robots, in order to achieve thegoal most efficiently. The dynamic of the real world also makes it necessary to reconsider taskassignments and other decisions. Sticking with the former example, a person could enter theguarded area, which makes it necessary to take a photo of their face, in order to decide whetherthe person is allowed inside the guarded area. Controlling the area and taking a photo at thesame time is hardly possible. So either an additional robot is necessary, or one robot pausesthe surveillance to take the photo. No matter how complex the goal is, a formalism is necessaryto describe this goal, its associated tasks and how they are achieved and fulfilled, respectively.In the context of this thesis this formalism is ALICA – A Language for Interactive CooperativeAgents. The details of the language are described in Section 2.2.

ALICA is domain independent, although it allows to integrate domain specific knowledge. Theapplication domain in this thesis is robotic football. The robotic football team Carpe Noctem1

is part of the Distributed Systems Research Group at the University of Kassel. The team isparticipating at least once a year at a national or international RoboCup2 event and is therebycomparing its research results with other teams around the world. Figure 1.1c shows one ofthe football robots. ALICA was also used to describe strategies for RmasBench [29]. RescueMulti-Agent System Benchmarking is simulator for rescue scenarios. In Figure 1.1a the topview of a simulated burning city is shown. The red dots are fire brigades, each controlled

1www.das-lab.net2www.robocup.org

1

1 Introduction and Purpose of the Thesis

(a) Rescue Multi-Agent System

(b) Lunar Test Bed (c) Carpe Noctem Football Robot

Figure 1.1: Application Domains for ALICA

by one ALICA agent. Burning buildings are coloured according to the intensity of their fire.Another application domain is given by the research project Impera [30]. In Impera strategiesfor distributed mission and task planning for lunar missions are investigated.

The purpose of this thesis is to investigate the applicability of a description logic based reasoningsupport for ALICA. The description logic SROIQ, together with a corresponding descriptionlogic reasoner, should be used to represent domain specific knowledge and to reason about thisknowledge in the context of the structure given by ALICA programs. The motivation for thisinvestigation is to obtain a standardised domain specific knowledge representation. As a resultof this standardisation, the reasoning techniques are domain independent and exchanging orexpanding the domain specific knowledge is much easier. Furthermore, the same techniques canbe utilised to guarantee a certain well-formedness of ALICA programs by reasoning about theirstructure and concurrently considering the integrated domain specific knowledge. The long termmotivation for this thesis is to pave the way for an appropriate reasoning support for ALICA.The reasoning should be capable of supporting the user during the modelling process of complexALICA programs. Identifying violations of certain conditions for well-formed ALICA programsand more abstract modelling flaws during the modelling process, is believed to accelerate themodelling process and to produce ALICA programs of better quality. For the accomplishmentof this task, the following steps are necessary:

Model Adaptation The modelling tool for ALICA programs, called Plan Designer, is basedon a cumbersome model representing the elements of ALICA and their relations. Themodel of the Plan Designer has to be aligned to the theoretic foundations of ALICA, inorder to make it concise and simultaneously consistent with the knowledge representationfor ALICA programs.

2

ALICA Ontology An ontology, representing the knowledge about well-formed ALICA pro-grams and corresponding predicates, has to be modelled.

Domain Ontology An ontology, representing the knowledge about the application domain,e.g., robotic football, has to be modelled.

ABox Ontology Based on the ALICA and the domain ontology, a process has to be developed,which creates the ABox ontology. The ABox ontology includes assertions about individualsof a given ALICA program.

Integration An interface to the created reasoning capabilities should be integrated into thePlan Designers user interface.

For the valuation of the knowledge representation and reasoning capabilities of SROIQ espe-cially the following three reasoning tasks should be considered:

Cyclic Plans ALICA programs consists of a tree-like plan hierarchy, and therefore are notallowed to include cycles in this hierarchy. The violating cyclic plans need to be classified.

Locality of In Relations An In Relation, like In(a,p,t,s), states, that agent a is participatingin plan p, where it is executing task t and currently occupies state s. For the designprinciples of ALICA it is important, that such an In Relation, which is part of a planspre- or runtime condition, only talks about the plan itself. Otherwise, the computation oftask assignments, for example, would be unfeasible under real-time requirements.

Sound Plans Similar to the locality of In Relations, it is important for plans to be sound. Aplan is sound, if and only if, every valid task assignment for this plan implies the existenceof a valid task assignment for all direct child plans in the plan hierarchy. Furthermore,the direct child plans have to be sound, too. A plan hierarchy of sound plans is free ofruntime conflicts between team members, with respect to a recursive task assignment.

The three reasoning tasks are meant to be examples of increasingly complex reasoning tasks.Other properties, like the satisfiability of conditions and the well-formedness of plans, are coveredby the three reasoning tasks, too. Any violation should be reported to the user, to give him thechance to improve his ALICA program accordingly.

The subsequent part of this thesis is structured by the following chapters. In Chapter 2 thefoundations are prepared for the explanation of the implementation in Chapter 4. In betweenan overview of related work is given in Chapter 3. After Chapter 4 the results are discussed inChapter 5. At the end the drawn conclusions are summed up, and an outlook for future workis given in Chapter 6.

3

2 Foundations

The content of this chapter includes a general introduction the foundations of this thesis. Atfirst the RoboCup Middle Size League is introduced in Section 2.1 as the application domain.Section 2.2 describes the parts of ALICA which are relevant for the reasoning support of thisthesis. The Plan Designer, presented in Section 2.3, is the modelling software being subject tothe extension through this reasoning support. Section 2.4 and 2.5 define the used descriptionlogic SROIQ and SWRL, respectively. A thorough understanding of the highlighted parts ofALICA and the decidability limits of SROIQ and SWRL are necessary, in order to under standthe implementation in Chapter 4 and the following discussion in Chapter 5.

2.1 RoboCup Middle Size League

The RoboCup foundation is a research initiative, which tries to promote robotics and artificialintelligence research [49]. Since 1997, the RoboCup World Championship is hosted once a year,including a lot of different domains, leagues and challenges. The senior categories are RoboCupSoccer, RoboCup Rescue and RoboCup @Home. RoboCup Junior is a category especially foryoung researchers, from pupils of the primary school to undergraduate students, which do nothave enough resources to get involved in the senior categories. The application domain for thisthesis is given by the Middle Size League (MSL) of the RoboCup Soccer category. In the MSLtwo teams, each consisting of five soccer robots, play against each other. A match is dividedinto two halves, each lasts 15 minutes. The football field has a size of 12 × 18 m and an originalhuman football is used. The football robots are not allowed to be larger than 52 × 52 cm andtaller than 80 cm. Only the keeper is allowed to extend its size by 10 cm for one second, in orderto catch the ball. Furthermore, the members of a team are allowed to communicate with eachother over W-LAN. Despite of these limitations, the MSL rules [2] are only a slightly changedversion of the original football rules [8].

The average MSL robots are able to drive and simultaneously dribble the ball at a top speedof 5 m/s. The kick distance reaches up to 16 m, whereby the ball is accelerated to velocitiesabove 12 m/s. During the last years, the robots dramatically improved their general cooperationand pass playing, making strategies like man-to-man marking mandatory for every successfulteam. From an agent researchers’ point of view [74], the football robots fit into the typical agentenvironment relation schema (see Figure 2.1) and match several well known agent properties:

Rational Rational agents always choose the optimal actions, according to their knowledge andbeliefs, to achieve a certain goal.

Autonomous Autonomous agents are always acting independently, sovereign, and uncontrolled.

Proactive Agents are proactive, if they act self-initiated to achieve a certain goal.

Reactive Reactive agents handle changes of their environment by adapting their behaviouraccordingly.

5

2 Foundations

Communicative In order to cooperate, communicative agents exchange their knowledge andbeliefs with each other.

For the rest of the thesis, the words agent and robot will be used interchangeably.

Sensory Input

Reasoning

Execute Actions

Environment

AgentPercepts

Actions

Figure 2.1: Agent Environment Relation

2.2 A Language for Interactive Cooperative Agents

The elements and structure of ALICA programs are explained in this section in a bottom-upfashion. Starting with finite state machines, the complexity is increased until all relevant partsare made completely clear. For a complete and thorough understanding of ALICA, we recom-mend to read the dissertation of Skubch [60] and the corresponding publications of Skubch etal. [61–65].

Z0 Z1

Z2

Z3

Z4

Find Ball Get Ball

Dribble

Score Goal

Post: scored

found

caught ∧ near goal

miss

caught

near goal

losthit

(a) Single FSM (b) Multiple FSMs

Figure 2.2: Agents Controlled by FSMs

At the lowest level of ALICA, finite state machines describe an agent’s sequence of actions.These finite state machines always have one initial state and an arbitrary number (includingzero) of terminal states. Terminal states are always annotated with a postcondition, which holdswhen an agent reaches the state. Furthermore, terminal states are distinguished into successand failure states, indicating a successful or unsuccessful execution of the finite state machine,

6

2.2 A Language for Interactive Cooperative Agents

respectively. Agents inhabiting a terminal state are doing nothing. Initial and normal statesinclude a set of behaviours. An agent inhabiting such a state must execute all behaviours inside.From ALICA’s point of view, a behaviour is an atomic and domain specific element. In roboticfootball typical behaviours are, e.g., drive to a point, stand still, and kick. The transitionsbetween states are guarded by a condition. An agent is allowed to pass a transition, if, andonly if, the condition holds according to its knowledge and beliefs. The finite state machine inFigure 2.2a describes how a football robot can score a goal. The agent, represented by the redball, is in state Z1, where it is executing a behaviour to get the ball. There are two options toleave that state, either it catches the ball and enters state Z2 or it catches the ball near the goaland enters state Z3.

Golden Goal Pre: >, Run: >

AttackReq:

1..1Z0 Z1

Z2

Z3

Z4

Find Ball Get Ball

Dribble

Score Goal

Post: scored

found

caught ∧ near goal

miss

caught

near goal

losthit

Goalkeeping1..1

Z4 Z5Position Save Ball

approaches

saved

Defend0..∞

Z6 Z7 Z8Interfere Catch Pass

approaches caught

lost

Figure 2.3: Simple Golden Goal Plan

Not all robots in a team should to do the same. Therefore, ALICA allows different robots toexecute different finite state machines. Figure 2.2b shows a compact example for three finitestate machines, whereof two do not have a terminal state. For the assignment of finite statemachines to robots, finite state machines, which contribute to the same goal, are organised inplans. A plan is the central ALICA element and introduces several new annotations. Most ofthese annotations are part of the Golden Goal plan in Figure 2.3. Each finite state machine isannotated with a cardinality restriction and a task. For example, the finite state machine inFigure 2.3, which is annotated with the task Defend, may be executed by zero to infinite agents.According to the cardinalities of all three tasks, at least two agents are necessary to execute thewhole plan. A possible configuration, as shown in Figure 2.3, is one agent for the Attack task,one agent for the Goalkeeping task, and two agents for the Defend task. If an agent does notbelief that there is at least one other agent, which can be assigned to the Golden Goal plan with

7

2 Foundations

it, it does not execute the plan at all.

Additionally to the tasks and cardinalities a plan may have a precondition and a runtime condi-tion. The precondition must hold before the execution of a plan begins, otherwise the executionis not allowed. The runtime condition must hold before and during the execution of a plan,otherwise the execution is stopped or not started at all. Altogether, there are four kinds ofconditions in ALICA: the precondition and the runtime conditions of plans, the transition con-ditions, and the postconditions of terminal states. All conditions are considered to be domainspecific and because ALICA is domain independent, the conditions can be realised with an ar-bitrary formalism. Therefore, the conditions represent the interface between ALICA and thedomain specific knowledge, which is added by the approach of this thesis.

Before we add more complexity to plans by introducing the tree-like plan hierarchy of ALICA,the introduced elements are reconsidered from a point of view which focuses on the executiontime of plans. A plan can only be executed if the assigned number of agents matches thecardinalities, the precondition holds, and the runtime condition is met. During the executionof a plan, the runtime condition must hold and the transition conditions are relevant for theprogress in the finite state machines. The execution of a plan by an agent is terminated, when itbelieves that the runtime condition does not hold anymore, the number of agents executing theplan fall below the minimum cardinality restriction, or it reaches a terminal state. The successfulexecution of a plan requires a particular number of agents to reach success states in particularfinite state machines. The finite state machines in which agents have to reach a success state areannotated with a required task. Which tasks of a plan are required, is defined by the plan itself.The number of agents which have to reach a success state is given by the minimum cardinalityrestriction of the corresponding finite state machine. This number is increased to one, in case theminimum cardinality is zero. Finally, it should be noted, that plans which have required tasksannotated to finite state machines, and do not comprise success states, can never be finishedsuccessful. Furthermore, the execution of a plan which does not have required tasks is alwayssuccessful. The Golden Goal plan in Figure 2.3, has only one success state and the Attack task,annotated at the success state’s finite state machine, is the only required task. Therefore, thered agent simply has to score a goal to end this plan successful.

A set of plans that all have the same goal can be seen as a set of alternatives. In ALICA,such alternative plan sets are called plantypes. They are inserted into the states of the finitestate machines, in order to build the aforementioned tree-like plan hierarchy. If there is onlyone plan inside a set of alternatives, the difference between the plan and the trivial set is onlysyntactical. The plan hierarchy, described more precisely, is a directed acyclic graph with asingle root node. This root node, as shown in Figure 2.4, is a single plan. All agents of the sameteam need to participate in this root plan. A particular plantype can be part of different plans,e.g., Plantype 4 is inside State Z6 and Z10 of Plan Alternative 2 and Alternative 3, respectively.A real tree is necessary during runtime, because agents should only synchronise their actions ifthey execute the same branch of the tree. Therefore, the two references of Plantype 4 generatetwo distinguishable instances of the same plantype at runtime. A complete plan hierarchy, asdescribed in the last paragraphs, is denoted as an ALICA program.

The role assignment of ALICA assigns roles to robots, according to the robots’ capabilities.The Attacker role, for example, is assigned to robots which are fast and have a strong shot,while the Defender role is assigned to robots, which are rather large and massive. The roles

8

2.2 A Language for Interactive Cooperative Agents

Root

Z0DefaultRoot Plantype

Alternative 1

Z1

Z2

Z3

Z4

Task1

Task2

Behaviour1Plantype2

Behaviour2 Plantype3

Alternative 2

Z5

Z6

Z7

Z8

Task1

Task3

Behaviour3 Behaviour4

Behaviour5Plantype4

Alternative 3

Z9

Z10

Z11

Z12

Z13

Z14

Task1

Task2

Task3

Behaviour1 Behaviour4

Behaviour5Plantype4

Behaviour3

Behaviour6Behaviour2

Behaviour1

Figure 2.4: Abstract Part of an ALICA Program

are necessary to obtain an abstraction from robots to capabilities and properties. For eachrole-task-pair a certain valuation is given, which helps the task allocation algorithm to find thebest task assignment. The initial task allocation procedure of an agent assigns itself, togetherwith all teammates, to the root plan. It is assumed, that all agents assigned to a task areexecuting the behaviours and plantypes of the corresponding initial state. Therefore, the taskassignment problem has to be solved recursively descending the initial states of the given ALICAprogram. On the next level, the allocating agent only considers teammates, which it allocatedon the previous level to the same task as it allocated itself. The recursion stops at an initialstate, which only includes behaviours. The allocating agent also has to ensure the executabilityof the chosen plan of each plantype, considering the allocated agents, the precondition, and theruntime condition. Beyond that, the situation, which allows the execution of a plan, must becompatible with the situations required by plans on the path up to the root plan. There area lot of reasons, which could prevent an agent from finding a complete task assignment for anALICA program, or at least narrow down the choices. For example, the cardinalities of theroot plan might not allow for enough agents according to some sub-plan. Another more domainspecific example could be given by two different plans, which both require an allocated agent toposses the ball. If both plans are part of two different finite state machines of the same plan,then there exists no valid task assignment for this plan at all. Three co-occuring facts causethis issue: (a) in the RoboCup Middle Size League only one robot of each team is allowed tostruggle for the ball; (b) in ALICA robots cannot be assigned to two different tasks of the sameplan; and (c) two different finite state machines of the same plan must be annotated with twodifferent tasks.

9

2 Foundations

2.3 Plan Designer

The Plan Designer is the tool, which accommodates ALICA with a graphical editing interfacefor ALICA programs. Figure 2.5 shows a screenshot of the current Plan Designer user interface.

Figure 2.5: The Graphical User Interface of the Plan Designer

The Plan Designer is based on Eclipse’s Rich Client Platform architecture [5, 32] and utilisesthe Eclipse Modeling Framework [67] to represent and serialise the data structures of ALICAprograms. In order to present ALICA programs to the user and make them editable, an intuitivegraphical user interface was developed with the help of the Graphical Editing Framework [69].The architecture stack is shown in Figure 2.6. The initial code base of the Plan Designer is theresult of Andreas Scharf’s bachelor thesis [55] and since 2008 a lot of additional features andbug fixes were added. One additional feature is the description logic reasoning support given bythis thesis. Considering the architecture of the Plan Designer, the reasoning support belongs tothe group of tools and plugins of the highest level.

Currently, the work flow for creating and running an ALICA program roughly involves foursteps. At first the program structure is graphically designed with the Plan Designer. Thereby,conditions are added in form of placeholders. The placeholders are necessary, because thePlan Designer provides no modelling support for domain specific elements. During the nextstep the program is saved and the code generation is triggered. Saving the program inducesthe EMF data structure, which was created during the first step, to be stored in the XMLMetadata Interchange format [66]. The code generation creates platform-specific code stubs foreach condition. The third step requires to fill the generated stubs by hand. The last step involvesthe ALICA engine to create a runtime representation of the serialised program structure. Thehand coded conditions are integrated into this runtime representation and therefore allows theALICA program to run as intended.

10

2.4 Description Logics

Plan Editor Roleset Editor Tools, PluginsPlan Designer

Eclipse ModelingFramework (EMF)

Graphical EditingFramework (GEF)

Eclipse Rich Client Platform (RCP)Equinox (OSGi Implementation)

OSGi Specfication

Figure 2.6: ALICA Plan Designer Architecture

2.4 Description Logics

The roots of description logics are twofold. On the one hand there were semantic networks basedon the work of Quillian [45]. On the other hand there were frames, invented by Minsky [33].Figure 2.7a shows an example of a semantic network, representing some knowledge about an-imals. Semantic networks represent relations between entities as annotated edges, like the “isa” edge. Frames, according to Minsky, describe entities as lists of slots. Each slot has at leasttwo facets, a name facet and a value facet (see Figure 2.7b). Frames also allow procedures, withdifferent trigger semantics. The area of the rectangle frame is calculated on demand by multi-plying side1 with side2. The side2 of the square frame is set, when side1 is set. The superclassslot intuitively has the same semantics of the “is a” edge of the semantic network, but bothrepresentations lack precise semantics. In practice the semantics of relations and especially thesemantics of their negations depend on the used implementation [3].

(a) Semantic Network about Animals

Frames:Slots:Facets:

[rectangle side1 type: real side2 type: real area type: real proc: (side1 x side2) exec: if-needed]

[square superclass: rectangle side2 type: real proc: side1 exec: if-added]

Legend:

(b) Frames about Geometric Shapes

Figure 2.7: Knowledge Representation by Semantic Networks and Frames

The semantics of description logics is based on first-order logic semantics. To be more precise,most description logics are decidable fragments of first-order logic. There are a lot of differentdescription logics, which all differ from each other, e. g., by offering another set of language

11

2 Foundations

constructors. An in-depth treatment of description logics, corresponding reasoning algorithms,complexity analysis and possible applications can be found in the “Description Logic Handbook”,written by Baader et al. [3]. The scope of this thesis restricts to the basic description logic“Attributive Language with Complements” (ALC) [57] and its extension SROIQ [25].

2.4.1 Attributive Language with Complements

Very similar to their predecessors, description logics include entities and their relations, whichare interpreted as unary and binary first-order predicates, respectively. The unary predicatesare called concepts, while the binary predicates are called roles. The syntax and semantics ofALC [57] are given in Definition 1 and 2, respectively.

Definition 1. Based on a set of concept names NC ∪{>,⊥}, each denoting an atomic concept,and a set of role names NR, each denoting a unique role, the description language ALC constructsother concepts with its language constructors {t,u,¬,∃,∀}, such that if C and D are conceptsand R is a role, (C tD), (C uD), (¬C), (∀R.C) and (∃R.C) are concepts, too.

Definition 2. An interpretation I = (∆I , · I) consists of a non-empty set ∆I , which is thedomain of I, and a function · I . The function · I maps every concept C to a set CI ⊆ ∆I andevery role to a binary relation RI ⊆ ∆I × ∆I . The special concepts > and ⊥ are mapped to>I = ∆I and ⊥I = ∅, respectively. The language constructors are interpreted, such that

(C tD)I = CI ∩DI

(C uD)I = CI ∪DI

(¬C)I = ∆I \ CI

(∃R.C)I = {d ∈ ∆I | There exists some e ∈ ∆I with 〈d, e〉 ∈ RI and e ∈ CI}(∀R.C)I = {d ∈ ∆I | For all e ∈ ∆I , if 〈d, e〉 ∈ RI , then e ∈ CI}

Considering the context of a certain application, Definition 1 and 2 are used to describe theapplication’s terminology. A terminology is a set of terminological axioms of the form C v D(R v S) or C ≡ D (R ≡ S), where C and D are arbitrary concepts (and R, S are roles). Inthe context of knowledge representations a terminology is also denoted as TBox. An ABox onthe other hand is a set of class and role assertions about individuals. A concept assertion C(a)states that the individual a belongs to the concept C. A role assertion R(a, b) states that theindividual b is a filler for role R of individual b. In order to define the semantics of TBoxes andABoxes, the interpretation function · I is extended to map the individuals’ name a to an elementaI ∈ ∆I . Furthermore, an interpretation I satisfies the terminological axioms and assertions

12

2.4 Description Logics

under the following conditions:

I satisfies C v D if CI ⊆ DI

I satisfies C ≡ D if CI = DI

I satisfies C(a) if aI ∈ CI

I satisfies R(a, b) if 〈aI , bI〉 ∈ RI

2.4.2 The Description Logic SROIQ

The description logic SROIQ1 [25], introduced as an extension of ALC, is not a direct extensionof ALC. It rather is the most current description logic, resulting from an ever-expanding researchon expressivity, while maintaining decidability. Therefore, the syntax and semantics of severalextensions are explained in this section. The set of concept names NC ∪ {>,⊥} is expanded bya set of nominals N . Nominals themselves are sets of individuals. Each nominal is a conceptcharacterised by its members, instead of properties, which an individual has to fulfil to be amember. The set of role names NR is extended by the universal role U and an inverse role R−for each R ∈ NR ∪ {U}. Considering role inclusion axioms like R v S, U is the super role of allother roles. The possibilities to describe complex concepts are expanded by the three languageconstructors ∃S.Self , ≥ nS.C and ≤ nS.C. The semantics of the mentioned extensions is givenin Defintion 3.

Definition 3. Given an interpretation I = (∆I , · I), concept C, role S, non-negative integers nand #M representing the cardinality of the set M , the new language constructors are interpreted,such that

(∃S.Self)I = {x | 〈x, x〉 ∈ SI}(≥ nS.C)I = {x | #{y | 〈x, y〉 ∈ SI and y ∈ CI} ≥ n}(≤ nS.C)I = {x | #{y | 〈x, y〉 ∈ SI and y ∈ CI} ≤ n}

The universal and inverse roles are interpreted, such that

(U)I = ∆I ×∆I

(U−)I = (U)I

(R−)I = {〈y, x〉 | 〈x, y〉 ∈ RI}

Beside the T- and ABox ofALC, SROIQ introduces the RBox, including a regular role hierarchyRh and a finite set of role assertionsRa. ALC only allows role inclusion axioms (RIA) like R v S.

1It is noteworthy, that the semantics of the “Web Ontology Language 2 (OWL 2)” relies on the semantics of thedescription logic SROIQ.

13

2 Foundations

SROIQ also allows finite role chains to form the left part of a RIA (R1R2 . . . Rn v S | n ∈ N>0).Maintaining the decidability, the RIAs are summarised and restricted to a regular role hierarchy,as stated in Definition 4.

Definition 4. A regular role hierarchy Rh is a finite set of role inclusion axioms of the formw v R, where R is a single role and w is a finite chain of roles, matching one of the followingforms:

1. w = RR

2. w = R−

3. w = S1 . . . Sn and Si ≺ R, for all 1 ≤ i ≤ n

4. w = RS1 . . . Sn and Si ≺ R, for all 1 ≤ i ≤ n

5. w = S1 . . . SnR and Si ≺ R, for all 1 ≤ i ≤ n

The operator ≺ is an irreflexive and transitive relation on all roles, which additionally satisfiesS ≺ R⇐⇒ S− ≺ R.

As a result of the restrictions on RIAs, regular role hierarchies do not contain cycles like R vS v T v R and therefore maintain decidability [26]. Role assertions, which are the other partof the RBox, are completely new, compared with the scope of ALC. In SROIQ roles can beasserted to be reflexive (Ref(R)), irreflexive (Irr(R)) and disjoint (Dis(R,S)). Transitive andsymmetric roles can already be expressed with the RIAs RR v R and R− v R, respectively.The semantics of the new RBox is given in Definition 5.

Definition 5. Given an interpretation I = (∆I , · I), roles S1,. . . ,Sn and R and domain ele-ments x, y, z ∈ ∆I , I satisfies a regular role hierarchy Rh, if, and only if, it satisfies every RIA∈ Rh. I satisfies a RIA S1 . . . Sn v R if, and only if, SI1 ◦ . . . ◦ SIn ⊆ RI , where ◦ representsa composition of binary relations. Furthermore, I satisfies role assertions under the followingconditions:

Ref(R) if DiagI ⊆ RI

Irr(R) if DiagI ∩RI = ∅Dis(R,S) if SI ∩RI = ∅

With DiagI defined as {〈x, x〉 | x ∈ ∆I}.

In order to maintain decidability, some constructors and assertions in the RBox are restrictedto simple roles. The contextual meaning of simple is given in Definition 6.

Definition 6. A role R is simple if . . .

• . . . it does not occur on the right hand side of a RIA in Rh.

14

2.4 Description Logics

• . . . it occurs on the right hand side of a RIA in Rh and for each w v R ∈ Rh, w is a singleand simple role S.

• . . . an inverse simple role R− exists.

According to Definition 6, R is not a simple role if S1 . . . Sn v R | n > 1 or if S1 . . . Sn vR− | n > 1 are part of the RBox. The elements of the RBox, which are restricted to simpleroles, includes the language constructors (≥ nS.C), (≤ nS.C), and (∃S.Self), as well as therole assertions for disjoint and irreflexive roles, Dis(R,S) and Irr(R). The necessity for therestriction of (≥ nS.C) and (≤ nS.C) has been proved by Horrocks, Sattler, and Tobies [27].All other restrictions were done with the following remark:

For SROIQ and the remaining restrictions to simple roles in concept expressionsas well as role assertions, it is part of future work to determine which of theserestrictions to simple roles is strictly necessary in order to preserve decidability orpracticability. This restriction, however, allows a rather smooth integration of thenew constructs into existing algorithms. [25]

After the introduction of all extensions to the TBox and the new RBox and its restrictions tosimple roles, there is only the ABox left. In SROIQ, the ABox is only slightly extended withnegated roles, such that I satisfies ¬R(a, b) if, and only if, 〈aI , bI〉 /∈ RI .

2.4.3 SROIQ Cannot Play Domino

Additional to its syntax and semantics, SROIQ states several restrictions, in order to maintaindecidability. Among other restrictions, the RBox has to be regular and the language constructorsfor qualitative number restrictions are restricted to simple roles. Horrocks, Kutz, and Sattler [25]cite [26] and [27] to give a prove for the necessity of the restriction of qualitative numberrestrictions and RBoxes, respectively. Without the corresponding restrictions, both sourcesprove their description logics to be undecidable, by describing the Domino Problem. The DominoProblem is a well-known undecidable problem.

The basic question of the Domino Problem is whether a set of dominoes can tile an infinite plane.The dominoes, as shown in Figure 2.8, have four edges, each with an assigned colour. In orderto tile the plane, it is not allowed to mirror or rotate the given dominoes and adjacent dominoesmust have the same colour on the adjacent edges. Apart from these restrictions, each givendomino can be used infinitely often. These special kind of dominoes are called Wang dominoes,proposed by Hao Wang 1961. He found a way to encode any Turing Machine into a set of Wangdominoes and conjectured that there is no aperiodic set of Wang dominoes. An aperiodic setof Wang dominoes tiles the plane without a repetitive pattern, such as a large square of severaldominoes. 1966 Robert Berger, one of Wang’s students, constructed an aperiodic set of 20,426dominoes and showed how to translate any Turing machine into a set of dominoes, which tilethe plane, if, and only if, the Turing machine does not halt [6]. Figure 2.8 shows an aperiodicset of 13 Wang dominoes and a fragment of its tiling.

The general idea to prove undecidability of a description logic with the help of the DominoProblem, is to describe it with the description logic itself. The typical formal definition of the

15

2 Foundations

Figure 2.8: An Aperiodic Set of 13 Wang Dominoes

Domino Problem, as given in Definition 7, replaces colours with natural numbers. Apart fromslight variations, this definition can be found in any of the aforementioned description logicpublications.

Definition 7. A domino system D = (D,H, V ) consists of a non-empty set of domino typesD = D1, . . . , Dd, and of sets of horizontally and vertically matching pairs H ⊆ D × D andV ⊆ D × D. The domino problem is to determine if, for a given D, there exists a tilingof an N × N grid such that each point of the grid is covered with a domino type in D andall horizontally and vertically adjacent pairs of domino types are in H and V respectively, i.e., a mapping t : N × N → D such that for all m,n ∈ N, 〈t(m,n), t(m + 1, n)〉 ∈ H and〈t(m,n), t(m,n+ 1)〉 ∈ V .

Typically, there are four constraints needed to describe the domino problem [54]. The first threeconstraints can be formulated in ALC. At first, the only existing concepts are the given dominotypes Di and every individual is the instance of exactly one domino type:

> v D1 t · · · tDd

D1 v ¬D2 u · · · u ¬Dd

D2 v ¬D3 u · · · u ¬Dd

......

Dd−1 v ¬Dd

16

2.5 Semantic Web Rule Language

Afterwards, all individuals have a horizontal (X-) successor and a vertical (Y -) successor:

> v ∃X.> u ∃Y.>

The third ALC expressible constraint states, that every individual has to satisfy the horizontaland vertical matching conditions of the domino system D:

D1 v⊔

(D1,D)∈H

∀X.D u⊔

(D1,D)∈V

∀Y.D

D2 v⊔

(D2,D)∈H

∀X.D u⊔

(D2,D)∈V

∀Y.D

......

Dd v⊔

(Dd,D)∈H

∀X.D u⊔

(Dd,D)∈V

∀Y.D

So far, all constraints were stated in ALC, which is a decidable description logic. Therefore,the fourth constraint is described by an axiom, which creates the undecidability. The fourthconstraint states that the horizontal-vertical-successor and the vertical-horizontal-successor co-incide for any individual. In case of complex role inclusion axioms this constraint is describedby X ◦ Y v Y ◦ X and Y ◦ X v X ◦ Y . An example is given in Figure 2.9a. In order toelaborate the precise boundary between decidability and undecidability, the description of thefourth constraint in [27] and [26] is much more complex and lengthy. Therefore, the descriptionis not part of this thesis. Nevertheless, the result of these restrictions is, that it is impossible todescribe a generic commutative square in SROIQ, as shown in Figure 2.9b.

X

YY

X

(a) Fourth Constraint of theDomino Problem

A B

C D

P

QK

L

(b) Generic CommutativeSquare

Figure 2.9: Structures Inexpressible in SROIQ

2.5 Semantic Web Rule Language

In order to combine the Web Ontology Language (OWL) with function free horn-clauses, alsoknown as Rule Markup Language(RuleML), the Semantic Web Rule Language (SWRL) was

17

2 Foundations

created [28]. An unrestricted combination of OWL and RuleML, induces the undecidabilityof the underlying description logic of OWL. In case of OWL 2, also known as OWL 1.1, thedescription logic is SROIQ. The syntax of SWRL rules are given in Definition 8.

Definition 8. A rule r has the form

B1, . . . , Bn → H

where H denotes the head of the rule and B1, . . . , Bn is the rule’s body. H and Bi are atomicparts, which either are concepts (C(x)) or roles (R(x, y)), given by a description logic’s TBoxor RBox, respectively. x and y denote concrete individuals, given by a description logic’s ABoxor variables, which can be bound to concrete individuals.

The semantics of SWRL rules is given by Definition 9.

Definition 9. The semantics of a rule B1, . . . , Bn → H is given by its corresponding descriptionlogic interpretation of the subclass axiom B1 u · · · uBn v H. Given the interpretation function· I of Definition 2 the subclass axiom is interpreted as BI1 ∩ · · · ∩BIn ⊆ HI .

In order to retain decidability, rules are only applicable to concrete individuals of the descriptionlogic’s ABox. In other words, the variables of a SWRL rule are universal quantified and cannotbe bound to unknown individuals. This restriction induces DL-Safe rules as defined in [37]. Thisis a serious restriction, because the rule’s body only matches explicitly stated individuals and therule’s head is not allowed to include individuals, which are not mentioned in the body. Therefore,SWRL rules can only introduce new role and concept assertions for existing individuals. Anextension of SWRL’s expressiveness are the so called build-ins. Build-ins are special relations fortopics like value comparison, mathematics, strings, times, and dates. For this thesis, only twobuild-ins were utilised: DifferentFrom(?x, ?y) and SameAs(?x, ?y). The prefixed question markdistinguishes variables from concrete individuals. Individuals, mapped to the given variables, areconsidered to be different or the same individuals, respectively. The extended expressive powerof a combination of SROIQ and SWRL can be described by an example. Although it is notpossible to describe an infinite tiling of a plane, as it would be necessary for the Domino Problem,it is possible to enforce a generic commutative square on the individuals level. ReconsideringFigure 2.9b, the following definition is possible:

ABox :A(a), B(b), C(c), D(d),K(a, c), P (a, b), L(c, d), Q(b, d)Rule :P (?a, ?b),K(?a, ?c), L(?c, ?d1), Q(?b, ?d1)→ SameAs(?d1, ?d2)

As a consequence of the rule, individuals of C and B, which are connected to the same individualof A, must be connected to the same individual of D, too.

18

3 Related Work

A lot of research is done on applications for description logics, especially on topics related to thesemantic web. However, this chapter focuses on related research in a closer sense. Therefore,this chapter is structured by two specialised topics: description logic supported planning systemsand football related ontologies.

3.1 Description Logic Supported Planning

Section 3.1 focuses on approaches, which combine planning algorithms and description logics.While Section 3.1.1 gives an overview of description logic supported planning, Section 3.1.2 and3.1.3 are concerned with two concrete description logic extended systems. Although the systemsmay differ, the benefit of a description logic based extensions are similar to the benefit intendedby this thesis.

3.1.1 Taxonomy Supported Planning

Gil [17] gives a survey on the combination of planning and description logics. Four taxonomies,relevant for planning problems, are identified: object, action, plan and goal taxonomies. Thegeneral idea is to create these taxonomies with description logics, in order to benefit from thedescription logics aptitude for reasoning. Object taxonomies describe the current state of theworld and the planning state and thereby support precondition matching through descriptionlogic reasoners. Action taxonomies describe actions on different levels of abstraction and provide,for example, a better scalability for problems with large numbers of actions. If the propertiesand constraints of actions are described with description logics, the action taxonomies’ hierar-chies can be created automatically by a description logic reasoners. This automatic constructionsaves time and is less error prone. Plan taxonomies provide similar benefits as action taxonomies,but due to the complex internal structures of plans, reasoning about plan taxonomies is oftendone by extended description logic reasoning mechanisms [17]. This statement complies with theexperience of describing ALICA programs with SROIQ, as explained in Chapter 4 and 5. Ac-cording to Gil, goal taxonomies play an important role for distributed approaches, with differentformulations of the same goal. Goals can be decomposed into a set of goals, which induce thefulfilment of the former single goal. This simplifies the achievement of the possibly unachievablesingle goal. Especially three planning architectures are given as examples for the integration ofsuch taxonomies: CLASP [13], SUDO-PLANNER [73], and EXPECT [68]. CLASP is a systemdeveloped to reason about action taxonomies and action networks. Its application is in thetelephony domain. SUDO-PLANNER exploits plan subsumption to control the search duringplan generation. EXPECT is an architecture for problem solving and reasoning that supportsinteractive acquisition of knowledge. Among other things, it exploits structured representationof goals and capabilities in order to support sophisticated matching during problem solving.

19

3 Related Work

3.1.2 AgentSpeak-DL

Moreira et al. extend the agent-oriented programming language AgentSpeak [48] with a descrip-tion logic based knowledge base [35]. Agents, described within AgentSpeak, react to triggeringevents. Their knowledge base includes a set of plans, which are annotated with triggering events,too. One reasoning step of the agent’s reasoning cycle is to determine the relevant plans fora given triggering event. The next step filters the determined set of plans, in order to get aset of applicable plans. The filtering is done with the help of the agent’s knowledge base andthe contexts of the given plans. A context is a conjunction of belief literals. The context of anapplicable plan must be a logical consequence of the agent’s knowledge base. Both reasoningsteps are seriously improved through the description logic based knowledge base. Instead of asimple matching of triggering events and contexts, plans can also be relevant and applicable, ifthey subsume the given triggering event and their context is deduced from the agents knowl-edge base, respectively. Several more reasoning steps in the agent’s reasoning cycle benefit fromthe description logic extension. Nevertheless, it is not possible to describe plans for a team ofagents with AgentSpeak. Moreover, instead of complex hierarchical plan structures, only planannotations are described by description logic formulae.

3.1.3 HTN-DL

Hierarchical Task Networks (HTN) [52] are used in many planning algorithms. The generalidea of dividing tasks into smaller tasks, until a network of atomic parts is created, is similarto the idea behind the structure of ALICA programs. In the context of HTN, tasks can beimplemented by so called methods. A method includes a directed acyclic task graph, denoted astask network. In order to create a complete plan, each task has to be implemented by a method oran operator. The operators are the counterpart of behaviours in ALICA. In his dissertation [59],Sirin proposes an extension of HTN with description logics, by representing preconditions ofmethods and operators with description logic queries. Furthermore, the planner includes a statewhich is represented by a description logic knowledge base. This allows the planner to queryits own knowledge base with the precondition queries of methods and operators in order todetermine if the corresponding method or operator is a suitable implementation of the currenttask. While this thesis tries to represent the structure of ALICA programs, the structure ofthe hierarchical task networks is not represented with a description logic. Sirin rather uses thedescription logic to categorise the given tasks, preconditions, and effects, in order to provide apowerful matching mechanism.

3.2 Football Related Ontologies

Section 3.2 focuses on football ontologies in a broader sense. The approaches and ontologiespresented in this section, are not only suitable for football. They represent general spatialreasoning or natural language processing (NLP) techniques applied to the football domain.However, the approaches using NLP are cited because the resulting football ontologies couldhave been applied in this thesis. Unfortunately, the ontologies are either not published orinclude no useful knowledge to reason about in the context of the RoboCup Middle Size League.

20

3.2 Football Related Ontologies

3.2.1 Region Connection Calculus

Descriptions of game situations in the RoboCup Middle Size League should include the positionsof the robots and the ball. In order to reason about relations between these positions a properformalism is necessary. The region connection calculus [46] could be a suitable formalism. Themost common variant of the region connection calculus (RCC8) includes eight basic relations:disconnected, external connected, tangent proper part (inverse), non-tangent proper part (in-verse), part of, and equal. These relations, as shown in Figure 3.1a, could be applied to regionsof the football field or regions introduced by an egocentric qualitative distance measurement, asshown in Figure 3.1b. Research on this topic was done by Schiffer, Ferrein, and Lakemeyer [56].Instead of description logic reasoners, the situation calculus based ReadyLog [15] is utilised.

X Y

X DC Y

X Y

X EC Y

X

Y

X TPP Y

X

Y

X NTPP Y

X Y

X PO Y

X

Y

X EQ Y

Y

X

X TPPi Y

Y

X

X NTPPi Y

(a) Relations of RCC8

near

middle

far

front

back

left right

(b) Egocentric Qualitative Distances

Figure 3.1: Qualitative Spatial Relations

Hogenboom et al. [20] investigated several approaches to represent the region connection calculusincluding 8 relations (RCC8) with a description logic. Unfortunately, none of these approachesare based on description logics only. According to Hogenboom et al., no decidable descrip-tion logic capable of representing RCC8 exists. The identified missing features in SROIQ arecomplex role inclusion axioms and boolean role constructors. Retaining decidability, the lat-ter feature was added to SROIQ by Rudolph, Krotzsch, and Hitzler [50]. A more pragmaticapproach was done by Batsakis and Petrakis [4]. Although they conclude similar results asHogenboom et al., they simply accept that only a part of RCC8 is covered and utilise this partfor some well-defined spatial reasoning.

3.2.2 FootbOWL

Bouayad-Agha et al. created an ontology with two levels. The upper level is used for naturallanguage generation and the basis level is especially concerned with the football domain. Theidea is to support the automatic generation of match summaries. The basis level ontology is notavailable, in order to avoid right infringements. However, several other football ontologies werereferenced: the SWAN Soccer Ontology, the sports fragment of the OpenCyc Ontology [11], andthe sports fragments in the DAML repository [47]. The most detailed ontology is the SWAN

21

3 Related Work

Soccer Ontology, created by Knud Moller [34]. Nevertheless, all given ontologies are not appro-priate for reasoning on positions or strategies in football. Their focus is on the organisation offootball leagues and teams, match scheduling, scores, and cards.

3.2.3 Tactic Ontology Generation

Gspandl et al. [18] describe an approach for automatic ontology creation. The input consistsof texts from human football strategy books. Utilising natural language processing techniques,subject-predicate-object triples are extracted from the texts. Based on these triples, a footballontology with strategies and tactical moves is created. The approach was implemented andevaluated by KickOffTUG during the RoboCup World Championship 2010. The name of theRoboCup 2D Simulation team of Graz’s University of Technology is KickOffTUG1. The teamachieved the 11th place of 19 teams. According to Gspandl et al. [18], 71% of the describedactions were parsed correctly and 86% of the generated actions were executed correctly. Unfor-tunately, the created ontologies are not published.

1http://kickofftug.tugraz.at (visited on 07/16/2012)

22

4 Implementation

According to the steps described in Chapter 1, this chapter is structured into several sections.The first section includes a description of the ALICA ontology. A rough overview about theclasses is given and some important details, relevant for the reasoning tasks, are examined.Afterwards Section 4.2 presents the domain specific ontology about the RoboCup Middle SizeLeague (MSL). With both ontologies in mind, the queries and adjustments for the reasoningtasks are explained in Section 4.4. Finally, the integration of all parts into the Plan Designeris described in Section 4.5. This enables users of the Plan Designer to execute the reasoningtasks, based on the given knowledge representation. The description logic axioms, given in thischapter, are written in Manchester OWL 2 Syntax [24]. The Manchester Syntax is a compactand user-friendly OWL 2 syntax. Concepts start with a capital letter, roles start with a smallletter. The keywords some, only, min, max, and exactly are used for existential, universal, andnumber restrictions of roles, respectively. The value keyword means that the filler of a role is aspecific individual.

4.1 The ALICA Ontology

The ontology for ALICA, as well as the MSL ontology, has been created with the ontology editorProtege [41]. The ALICA ontology is too complex to show all concepts, roles, and assertionsin one figure. However, the concept hierarchy, as shown in Figure 4.1, provides an overviewof the ALICA ontology. The intermediate root concept, denoted as ALICAThing, introduces aseparation between the domain independent ALICA concepts and domain specific concepts ofother ontologies. The introduction of such artificial concepts is an efficient way to retain a clearontology structure, when the domain specific ontology imports the ALICA ontology.

4.1.1 Well-Formed ALICA Programs

The dissertation of Skubch [60] is the most comprehensive publication on ALICA, and thereforerepresents the reference document for the ALICA ontology. Besides the general relations betweenthe concepts, depicted in Figure 4.1, Skubch notes several conditions ([60], p. 38) in order todefine well-formed ALICA programs:

• The top-level plan contains precisely one state and one task. (4.1)• States belong to at most one plan. (4.2)• No transition connects states in different plans. (4.3)• Synchronisations only happen within a plan. (4.4)• The failure and success states of a plan are disjoint subsets of its states. (4.5)

23

4 Implementation

Thing

ALICAThing

NaryRelation

SucceedRel InRel

subsumes

Agent Capability Role World PlanElement

AbstractPlan

Behaviour Plan

RootPlan CyclicPlan

subsumes

PlanType

subsumes

EntryPoint Condition

PreC. RunC. PostC.

subsumes

Synch. Task Transition State

InitState TerminalState

SuccessState FailureState

subsumes

LooseState

subsumes

subsumes

subsumes

subsumes

Figure 4.1: The Concept Hierarchy of the ALICA Ontology

• Terminal states do not include sub-plans or behaviours. (4.6)• There is a postcondition associated with each success and failure state. (4.7)• A task associated with a plan identifies an initial state within that plan. (4.8)• All plan-task pairs have a valid cardinality interval associated. (4.9)• The top-level plan is transitively connected to all plans. (4.10)• Every plan has at most one parent. (4.11)• The transitive closure of the parent-child relationship is asymmetric. (4.12)

RootPlan denotes the concept for top-level plans and is, as shown in Figure 4.1, subsumed by themore general Plan concept. It is not necessary to model the requirement, stated in Condition 4.1,due to several reasons. The purpose of this condition is to facilitate synchronisation of agents inan ALICA program. Therefore, it is possible to meet this condition with an artificial top-levelplan, which is created by the executing ALICA engine at runtime. The user of the Plan Designeris allowed to model top-level plans with several states and tasks. At runtime, the engine of allagents set the artificial top-level plan on top of the users actual top-level plan. Considering thepurpose of this thesis, the uppermost plan for the reasoning tasks is seldom the real top-levelplan of the ALICA program. Instead, arbitrary plans within the hierarchy are tested with thehelp of the provided reasoning capabilities.

Conditions 4.2–4.6 are already enforced by the Plan Designer’s user interface. Nevertheless,it is necessary to include these conditions the ALICA ontology, in order to detect failures inprograms, which were created or altered by planning algorithms or users editing the XML filesdirectly. The version of Condition 4.2, integrated into the ALICA ontology, is a little bit stricter:State ≡ isStateOf exactly 1 Plan. As a consequence, states are not allowed to exist outside thescope of a plan. This restriction helps to ensure the semantics of other ALICA elements. It is

24

4.1 The ALICA Ontology

not possible to enforce Condition 4.3 within SROIQ, because of the limitations described inSection 2.4.3. On the other hand, SWRL Rule 4.13

inState(?t,?s), outState(?t,?r), isStateOf(?s,?p), isStateOf(?r,?q)→ SameAs(?p,?q) (4.13)

enforces, that states which are connected by a transition, have to be part of the same plan. Theroles inState and outState, point from a transition ?t to its source state ?s and target state ?r,respectively. In strict accordance with SWRL Rule 4.13, a reasoner deduces two different plansto be actual the same, because it is not stated otherwise. It is not guaranteed, that such aunification of plans results in an inconsistency. Therefore, it is necessary to render the ontologyinconsistent by stating that all plan individuals are distinct (see Section 5.3 for Unique NameAssumption). Condition 4.4 is similar to Condition 4.3 and integrated into the ALICA ontologywith SWRL Rule 4.14. The role hasSynchedTransition is pointing from a synchronisation toany of its transitions.

hasSynchedTransition(?sy, ?t1), hasSynchedTransition(?sy, ?t2), inState(?s1, ?t1),inState(?s2, ?t2), isStateOf(?s1, ?p1), isStateOf(?s2, ?p2)→ SameAs (?p1, ?p2) (4.14)

The fact that success and failure states of a plan are disjoint subsets of the plan’s total states,as required by Condition 4.5, is partially encoded into the concept hierarchy, shown in Fig-ure 4.1. Furthermore, it is stated in the ALICA ontology, that the TerminalState concept is adisjoint union of the FailureState and SuccessState concepts. Ensuring that terminal states metConditon 4.6, the property restriction hasAbstractPlan exactly 0 Thing is part of the concept def-inition for terminal states. Another part of the definition, hasCondition exactly 1 PostCondition,guarantees the compliance with Condition 4.7.

The accomplishment of Conditon 4.8 and 4.9 is bounded to the EntryPoint concept. An entrypoint represents a plan-task pair and is therefore defined by the following concept description:

EntryPoint ≡ PlanElement (4.15)and (hasTask exactly 1 Task) (4.16)and (isEntryPointOf exactly 1 Plan) (4.17)and (hasInitState exactly 1 State) (4.18)and (minCardinality exactly 1 integer) (4.19)and (maxCardinality exactly 1 integer) (4.20)and (successRequired exactly 1 boolean)) (4.21)

Role restriction 4.16 and 4.17 ensuring the EntryPoint concept to be a representation of aplan-task pair. The fulfilment of Condition 4.8 is guaranteed by role restriction 4.18 and thefollowing SWRL rule:

isEntryPointOf(?ep1, ?p1), isEntryPointOf(?ep2, ?p2), isTaskOf(?t, ?ep1),isTaskOf(?t, ?ep2), DifferentFrom (?ep1, ?ep2)→ DifferentFrom (?p1, ?p2) (4.22)

If two different entry points are annotated with the same task SWRL Rule 4.22 enforces thatthe two plans of the entry points are different, too. Otherwise a plan’s entry points could be

25

4 Implementation

annotated several times with the same task, which would make the mapping from plan-taskpairs to initial states ambiguous. Role restrictions 4.20–4.21 utilise data properties. Dataproperties are roles pointing to data types, typical for common programming languages. Rolerestriction 4.21 is not mentioned in any of the well-formedness conditions, but, as described inSection 2.2, it is crucial for determining the successful execution of a plan. Role restriction 4.19and 4.20 only guarantee, that an entry point has a minimum and maximum cardinality, butCondition 4.9 also requires both values to be consistent. The minimum and maximum cardinalityof an entry point are consistent, if, and only if, the minimum cardinality is less than or equalto the maximum cardinality. Such a restriction demands for a comparison of data properties,as suggested by the W3C1 draft of Parsia and Sattler [44]. Unfortunately, this draft did notmake it into the final version of OWL 2 and therefore, the features presented in the draft arenot supported by any description logic reasoner. In order to support Condition 4.9, a SWRLrule including the build-in lessThan(?x,?y) would help. The description logic reasoner Pelletsupports reasoning about SROIQ and such SWRL build-ins, but it was not able classify theABox ontology for some unknown reason. A detailed description on the ABox ontology is givenin Section 4.3.

The last three conditions (4.10–4.12) can be rephrased by only one condition: The plan hierar-chy of an ALICA program has a tree-shaped structure. The role hasChildPlan, respectively itsinverse role isChildPlanOf, is the key element in order to enforce a tree structure. According toCondition 4.10 the top-level plan, represented by the RootPlan concept, is transitively connectedto every plan of the ALICA program. Therefore, the role hasChildPlan must be declared transi-tive, which means that it is a non-simple role (see Section 2.4.2). The hasChildPlan role is alsocomposed of several roles. It is either composed of the role chain axiom hasState o hasPlan vhasChildPlan or hasState o hasPlanType o hasRealisation v hasChildPlan. Both reasons for thehasChildPlan role to be non-simple are not allowed at the same time. Either it is composed ofother roles or it is transitive. The following two SWRL rules provide a solution for this problemby handling the composition of the hasChildPlan role:

hasState(?p0, ?s), hasPlan(?s, ?p1)→ hasChildPlan(?p0, ?p1) (4.23)hasState(?p0, ?s), hasPlanType(?s, ?pt),

hasRealisation(?pt, ?p1)→ hasChildPlan(?p0, ?p1) (4.24)

Condition 4.11 formulates a number restriction for the role isChildPlanOf, which is the inverserole of hasChildPlan. Number restrictions, as described in Section 2.4.2, are restricted to simpleroles. This is a problem, since a role is not allowed to be transitive (non-simple) and used innumber restrictions at the same time. In addition, Condition 4.12 directly requires, that thetransitive closure of the hasChildPlan role is asymmetric. Following common mathematic defi-nitions of asymmetric relations, it can be deduced that the role hasChildPlan must be irreflexivein order to be asymmetric. Just as roles are not allowed to be transitive and used in numberrestrictions, they are also not allowed to be transitive and irreflexive or asymmetric. Therefore,it is not possible to guarantee a tree-shaped structure for ALICA programs, following the giventhree conditions. Still a good approximation, based on a post by Ulrike Sattler on the PublicOWL Developer mailing list [53], is modelled as part of the ALICA ontology.

1The World Wide Web Consortium (W3C) is an international community, which develops Web standards likeOWL 2.

26

4.1 The ALICA Ontology

Plan

RootPlanCyclicPlanisOffspringPlanOf

some

isChildPlanOfmin 2

isChildPlanOfexactly 0

(a) Plan Concepts and Role Restrictions

hasChildPlan v hasOffspringPlanisChildPlanOf v isOffspringPlanOfhasChildPlan ≡ Inverse(isChildPlanOf)

hasOffspringPlan ≡ Inverse(isOffspringPlanOf)Transitive(hasOffspringPlan)Transitive(isOffspringPlanOf)

(b) Role Hierarchy and Assertions

Figure 4.2: Concept Graph and Axioms for Tree-Shaped ALICA Programs

The key for an admissible description of tree-shaped ALICA programs is the role hasOffspring-Plan. It is a transitive super role of hasChildPlan and allows hasChildPlan to be modelledas simple (non-transitive) role. The corresponding role hierarchy and assertions are listed inFigure 4.2b. Figure 4.2a describes the concept graph, which allows a description logic reasonerto classify plan individuals as members of the CyclicPlan or RootPlan concept. Cyclic plans areconnected to some root plan by the isOffspringPlanOf role and have at least two connectionsto plans through the isChildPlanOf role. A root plan simply has no connections through theisChildPlanOf role. The exact condition, constructed by the given axioms, is that the planhierarchy connected to a root plan by chains of hasChildPlan roles is a tree. However, if somepart of the plan hierarchy is connected only through a hasOffspringPlan role and not througha chain of hasChildPlan roles, the tree-shape of this part is not guaranteed. Therefore, thehasOffspringPlan role is never set directly by parsing an ALICA program. Only the descrip-tion logic reasoner may set a hasOffspringPlan connection, induced by a chain of hasChildPlanconnections.

4.1.2 Participation of Agents in ALICA Programs

Section 4.1.1 focuses on the conditions for well-formed ALICA programs and how these condi-tions can be expressed within SROIQ and SWRL rules. For convenience, the yet unhandledconcepts of the ALICA ontology are repeated in Figure 4.3. Omitting the condition conceptsand the world concept, the focus of the remaining concepts is on the participation of agents inwell-formed ALICA programs. The omitted concepts are further investigated in Section 4.3.

The Role concept is not to be confused with description logic roles. In the context of ALICA arole is defined by the capabilities an agent must posses in order to take on the role. One rolein the MSL domain is the role of an attacker. An agent has to be fast, is a versatile dribbler,and is precise at shooting in order to take on the attacker role. Each agent is allowed to fulfilonly one role at a time. Figure 4.4 depicts a concept graph about the concepts essential for theparticipation of agents in ALICA programs. Beside the relation between the Agent and Roleconcept, the details of the two n-ary relation concepts are given. N-ary relations in the ALICAontology have at least three arguments. In this particular case the Succeeded relation has threeand the In relation has four arguments. As description logics are restricted to binary relations,represented by roles, it is not possible to express n-ary relations directly. Instead a common

27

4 Implementation

Thing

ALICAThing

NaryRelation

SucceedRel InRel

subsumes

Agent Capability Role PlanElement

Condition

PreC. RunC. PostC.

subsumes

subsumes

subsumes

World

subsumes

Figure 4.3: The Concept Hierarchy Part for Agents’ Plan Participation

design pattern for n-ary relations (see [42]) helps to express the In and Succeeded relation inthis case. The design pattern suggests to introduce an extra concept for the corresponding n-aryrelation and connect the arguments with normal roles.

AgentRole

Capability

SucceededRel

Plan

Task

InRel

State

hasRolemin 1 hasCapability

somehasInRel.hasSucceedRel.

succeedRelPlanexactly 1

succeedRelTaskexactly 1

inRelStateexactly 1

inRelPlanexactly 1

inRelTaskexactly 1

Figure 4.4: Concepts and Roles for Agents’ Plan Participation

The extra concept of the In relation is denoted as InRel and the four arguments must beindividuals of the concepts Agent, Plan, Task, and State. The In relation In(a, p, t, s) means,that agent a is participating in plan p and is assigned to task t. Furthermore, agent a occupiesstate s of the finite state machine determined by task t of plan p. The given semantics of theIn relation obviously requires certain conditions for the arguments to be met. Task and statemust be part of the same plan and the state must be part of the finite state machine, which isannotated with the task. In order to model these requirements into the ALICA ontology, againSWRL rules are necessary, because the InRel, Plan, Task, and State concept build an instanceof the generic commutative square, as shown in Figure 2.9b of Section 2.4.3.

hasReachableState(?ep, ?s), inRelPlan(?r, ?p), inRelState(?r, ?s),inRelTask(?r, ?t)→ hasTask(?ep, ?t), isEntryPointOf(?ep, ?p), isStateOf(?s, ?p) (4.25)

28

4.1 The ALICA Ontology

The body of SWRL Rule 4.25 matches to individuals, which are connected as shown in Figure 4.5.The orange part of the graph represents the asserted head of the SWRL rule. While most rolesof this graph are already introduced and simple in nature, the hasReachableState role is morecomplex and similar to the hasOffspringPlan role. Like the hasOffspringPlan role, it is alsotransitive and subsumes a chain of simple roles. This chain always starts with the hasInitStaterole, pointing from an entry point to its initial state. The subsequent part of the role chainconsists of an arbitrary number of transition-state pairs. The structure of this role chain isdefined by the two subsumption axioms hasInitState v hasReachableState and outTransition ooutState v hasReachableState, and the defined source and target concepts of the involved roles.

EntryPoint: ep

Plan: p

Task: t InRel: r

State: shasReachableState

inRelState

inRelPlan

inRelTask

hasTaskisEntryPointOf

isStateOf

Figure 4.5: Graph Matched by SWRL Rule 4.25

There are two prerequisites for SWRL Rule 4.25 in order to match the exact semantics of the Inrelation: (a) At most one entry point per plan-task pair; (b) and at least one connection fromeach state to an entry point exists. The first prerequisite is guaranteed by SWRL Rule 4.22.The second prerequisite cannot be guaranteed, because DL-Safe SWRL rules (see Section 2.5)only allow to reason about explicitly created individuals. A connection between a state andan entry point would be represented by the non-simple role isReachableStateOf. If it is notexplicitly stated that such a connection exists or does not exist, SWRL rules do not classify thecorresponding states as connected or unconnected, respectively. Furthermore, the axiom State≡ isReachableStateOf some EntryPoint would enforce the description logic reasoner to assumethe existence of a connection between each state and an entry point. The reasoner would notcreate such a connection itself and if the assumption does not contradict with any other axiomsor assertions, no error would be reported. The described semantics are denoted as open worldsemantics and is further discussed in Chapter 5. Nevertheless, if the state of an In relation isproperly connected with an entry point, the SWRL rules 4.22 and 4.25, as well as the mentioneddescription logic axioms and assertions, enforce the intended semantics of the In relation.

The Succeeded relation has three arguments and the concepts of these arguments are the Agent,Plan, and Task concept. Succeeded(a, p, t) has the straight forward meaning, that agent a hasreached a success state of the finite state machine, determined by the plan-task pair p and t, atsome point in the past. Unfortunately, it is impossible to enforce that task t has to be annotatedat some entry point of plan p. Modelling the semantics of the Succeeded relation within SROIQis not possible for the same reasons as for the In relation. Therefore, one of the following SWRL

29

4 Implementation

rules would be necessary:

succeededRelPlan(?s,?p), succeededRelTask(?s,?t), hasTask(?ep,?t)→ hasEntryPoint(?p, ?ep) (4.26)

succeededRelPlan(?s,?p), succeededRelTask(?s,?t), hasEntryPoint(?p,?ep)→ hasTask(?ep, ?t) (4.27)

Both SWRL rules encounter some semantic problems. On the one hand, SWRL Rule 4.26 alsomatches entry points of different plans, because the task could be annotated at entry pointsof other plans, too. On the other hand, SWRL Rule 4.27 would unify all entry points ofthe considered plan. SWRL Rule 4.25 is not confronted with the same problem, because theadditional state identifies the right entry point and avoids wrong matches for the body of therule. Another issue related to the Succeded relation is, that consequences of a stated Succeededrelation are primarily concerned with the successful execution of plans at runtime. More detailson the successful execution of plans are described in Section 2.2. Furthermore, Skubch [60]states, that a certain Succeeded relation is only relevant, as long as another agent is still withinthe state that contains the corresponding plan. Effectively a Succeeded relation will be deletedfrom the agents belief base, if no agent is in the state that contains the plan. Both aspectscreate a time-referenced semantics of the Succeeded relation. However, the concept of time andits utilisation is not part of this thesis, although a promising and official time ontology [19] ofthe W3C exists. The first step, which is done by this thesis, in order to provide ALICA with adescription logic reasoning support, is focused on support during modelling of ALICA programswithin the Plan Designer. Considerations, necessary for the execution of ALICA programs atruntime, are postponed to simplify this first step.

4.2 The MSL Ontology

This chapter is about the concepts and roles of the MSL ontology. Following the approachof Section 2.2, Figure 4.6 shows the concept hierarchy of the MSL ontology, in order to givean overview of the included concepts. The concept MSLThing is, similar to the concept AL-ICAThing, an artificial root concept. The MSL ontology imports the ALICA ontology, whichmeans, that the ALICA ontology with all its concepts is part of the MSL ontology. Both con-cepts, MSLThing and ALICAThing, avoid a confusing mix of MSL and ALICA concepts duringthe modelling in Protege. Nevertheless, the MSLThing concept and ALICAThing concept arenot disjoint. Two concepts of the MSL ontology are related to concepts of the ALICA ontology.Firstly, the World concept of the ALICA ontology subsumes the DomainWorld concept of theMSL ontology. Further concepts and roles related to the World and DomainWorld concepts areexplained in Section 4.3. The second relation between the MSL and ALICA ontology is theequivalence of the Agent concept of the ALICA ontology and the TeamMember concept of theMSL ontology.

On a more abstract level of the concept hierarchy, the MSL ontology is separated into fourconcepts. Omitting the DomainWorld concept, the other three concepts represent real MSLentities. The RefboxSituation concept subsumes all existing game situations of a MSL footballmatch. These game situations are defined by the MSL rules [2], so that the game is either

30

4.2 The MSL Ontology

Thing

MSLThing

RefboxSituation

OwnStandard

Own. . .

subsumes

OppStandard

OppCornerKick OppFreeKick OppGoalKick OppKickOff OppPenalty OppThrowIn

subsumes

DropBall GamePlay Stop

subsumes

DomainWorld MSLArea

Field OppGoalArea OppHalf OppPenaltyArea Own. . .

subsumes

MSLPhysical

Ball MSLRobot

Opponent TeamMember

subsumes

subsumes

subsumes

subsumes

Figure 4.6: The Concept Hierarchy of the MSL Ontology

running, stopped, a standard situation for the own or the opponent team is given, or a drop ballis given. The latter situation is a standard situation, neither for the own nor for the opponentteam. Instead, it is a common way to restart the game after an unexpected break. The otherstandard situations are well-known from real football matches and do not need any furtherexplanations. The OwnStandard concept subsumes the Own. . . concept. The dots signals thatthere are the same standard situations for the own team as there are for the opponent team.Obviously, a game may have only one game situation at a time. The axiomatisation of this factis related with the DomainWorld concept and described in Section 4.3.

The football field of the MSL is divided into several areas, as shown in Figure 4.7. This divisionis captured by the concepts subsumed by the MSLArea concept. The Field concept and the sixincluded area concepts are defined as nominals, each with only one element. This is necessaryto guarantee that only one individual of each area exist. Furthermore, the Field concept issubsumed by a conjunction of six axioms, each of the form hasPart some <MSLArea>. Theplaceholder <MSLArea> is replaced by the six area concepts, which are part of the footballfield. The role hasPart and its inverse isPartOf are transitive and each of the six area conceptsare subsumed by an anonymous concept, which defines, that the area is part of its enclosingarea. For example, the OwnGoalArea concept is subsumed by the anonymous concept isPartOfsome OwnPenaltyArea. This construction makes it possible to deduce, that each area is part ofthe field, each penalty and goal area is part of the corresponding half, and that each goal areais part of its enclosing penalty area.

The third large part of the MSL ontology is subsumed by the MSLPhysical concept. It subsumesthe MSLRobot and the Ball concept. Similar to the Field and area concepts, the Ball conceptis defined as nominal with only one element. This is necessary, because in football only one ballexists. The hasBall role and its inverse isBallOf are functional. Functional roles are restrictedto connect an individual with at most one other individual. Essentially this means that only one

31

4 Implementation

Own Half

Opponent Half

OwnPenalty Area

OpponentPenalty Area

OwnGoal Area

OpponentGoal Area

Figure 4.7: The Areas of a MSL Football Field

individual can have the ball and that each individual can have at most one ball. A descriptionlogic reasoner deduces that these individuals are instances of the MSLRobot concept, becausethe source concept of the hasBall role and target concept of the isBallOf role are restricted tothe MSLRobot concept. The MSLRobot concept subsumes the TeamMember and the Opponentconcept. An individual of the MSLPhysical concept can be asserted to be inside an individual ofthe MSLArea concept. This is done by the isInside role, which is extended with the role chainisInside o isPartOf v isInside. This role chain axiom makes it possible to deduce that a ball ora robot, which is inside a certain area of the field, is also inside the enclosing areas. Finally, thegeneral class axiom isInside some OppHalf DisjointWith isInside some OwnHalf is added to theMSL ontology, in order to prohibit individuals of the MSLPhysical concept to be concurrentlyinside two non-overlapping areas of the field.

4.3 Creation of the ABox Ontology

The ALICA ontology (see Section 4.1) and the MSL ontology (see Section 4.2) comprise abstractknowledge about ALICA and the RoboCup Middle Size League (MSL), respectively. The ABoxontology, named after the ABox defined in Section 2.4.2, mainly comprises definitions of individ-uals and associated role assertions. The ALICA and the MSL Ontology provide the fundamentalknowledge for these ABox axioms, and are therefore imported by the ABox ontology.

The specific content of the ABox ontology is determined by the user, who is interacting withthe graphical user interface provided by this thesis. The details of this interaction and theintegration into the Plan Designer are described in Section 4.5. In general, it is admissible

32

4.3 Creation of the ABox Ontology

to assume that the input for the ABox ontology is a partial or complete ALICA program,determined by a certain plan. If this plan is not part of a cycle in the plan hierarchy, the planis the top-level plan of the input. Therefore, the algorithm, which creates the ABox ontology,traverses an assumed plan-tree and stops at branches which are involved in a cycle. During thistraversal an individual for each encountered ALICA element is created and the correspondingroles are asserted. Most violations of conditions for well-formed ALICA programs would notbe noticed by a description logic reasoner without the assertion that all declared individuals ofthe ABox ontology are disjoint. This assertion can be interpreted as a form of the unique nameassumption, required by the definition of an agents belief base in [60] on page 48.

The description of the World, DomainWorld, Condition, PreCondition, RunCondition, and Post-Condition is postponed from Section 4.1 and 4.2 to this section, because they are closely in-terrelated and are specially handled during the creation of the ABox ontology. As stated inSection 2.2, conditions of an ALICA program represent the interface between the domain inde-pendent ALICA elements and the application domain. In other words, domain specific assertionscan be formulated as conditions in ALICA programs. For example, one of the robots must havethe ball in order for the team to execute the plan. If the same condition is stated for anotherplan in another branch of the same ALICA program, loosely modelling of both conditions couldinduce, that both robots are the same, because only one robot is allowed to have the ball. There-fore, the assertions made by a condition and the restrictions of the domain have to be coupledto the structure of the ALICA program, in order to restrict their scope. This is where the Worldconcept and the DomainWorld concept come into play. One subconcept of the DomainWorldconcept, further denoted as (specific) world concept, is defined for each condition. These specificworld concepts describe the possible states of the world according to the assertions made by thecorresponding conditions. Therefore, the assertions are connected to the specific world concepts,by the hasWorldPart role (hWP), or its inverse, the isWorldPartOf role (iWP). In case of a planprecondition, restrictions due to the entry point cardinalities are connected, too. Following thestructure of the ALICA program, the different specific world concepts are set into appropriatesubconcept relations. For example, the robots mentioned in the precondition of a child planmust be part of the robots which are assigned to a certain task of the parent plan.

For a more thorough understanding, a comprehensive example is given. The example is based ona small ALICA program, depicted in Figure 4.8. The name of the root plan is Simple Strategy.The task assignment algorithm divides the robots in two groups, the attackers and the defenders,by assigning them to the corresponding tasks. Omitting the constraints introduced by the childplans, the root plan is executable with at least one attacking robot. This constraint is expressedby the following concept description:

hasWorldPart min 1 (hasInRelationsome ((inRelPlan value SimpleStrategy)and (inRelTask value Attack))

A graph, describing this concept description, is shown in Figure 4.9. The diamond symbolsrepresent individuals whereas the circle symbol represents the anonymous concept, which isdescribed by the attached graph. Another axiom, which is related to the assignment of robots

33

4 Implementation

Simple Strategy

Z0Attack1..∞ Attack Plantype

Z1Defend0..∞ Defend Plantype

Simple Attack

Z2Attack1..1 Score Goal

Simple Defend

Z3Defend1..∞ Block Goal

Clearance

Z4Defend1..1 Long Shot

Figure 4.8: The Example ALICA Program Simple Strategy

Agent InRel Attack

SimpleStrategy

hWPmin 1

hasInRelationsome

inRelPlanvalue

inRelTaskvalue

Figure 4.9: Graph Describing the Cardinality Restriction

34

4.3 Creation of the ABox Ontology

to tasks, is given by:

hasInRelation some ((inRelPlan value SimpleAttack)and (inRelTask value Attack)) DisjointWithhasInRelation some ((inRelPlan value SimpleAttack)and (inRelTask value Defend)) (4.28)

It states that the robots assigned to the Attack task are disjoint with the robots assignedto the Defend task. Axioms, which guarantee the minimum and maximum cardinalities andthe disjointness of robots, assigned to different tasks of the same plan, are connected to thecorresponding specific world concept of every plan. The next step is to connect these worldconcepts according to the plan hierarchy. The following subconcept axiom states that the robotsassigned to the Simple Attack plan are a subset of the robots assigned to the Attack task of theSimple Strategy plan:

hasInRelation some (inRelPlan value SimpleAttack) vhasInRelation some ((inRelPlan value SimpleStrategy)and (inRelTask value Attack)) (4.29)

A problem arises, due to the semantics of plantypes with more than one plan. Disjunctionsbetween subconcept axioms would be necessary to reflect the semantics, because either therobots in the Clearance plan or the robots in the Simple Defend plan are a subconcept of therobots assigned to the Defend task of the Simple Strategy plan. Without any further conditionson the robots, the following axiom would provide a good approximation:

hasInRelation some (inRelPlan value SimpleDefend) thasInRelation some (inRelPlan value Clearance) v

hasInRelation some ((inRelPlan value SimpleStrategy)and (inRelTask value Attack)) (4.30)

For the sake of simplicity, it is assumed, that the plans in the given example only have thefollowing preconditions annotated:

• Simple Strategy: No condition (>)

• Simple Attack: At least one robot, assigned to the Attack task, has the ball.

• Simple Defend: No condition (>)

• Clearance: At least one robot, assigned to the Defend task, has the ball.

The world concept descriptions for the preconditions of the Simple Attack and the Clearanceplan are similar to the world concept description shown in Figure 4.9. The hasBall role be-tween the Agent concept with the Ball concept is the only difference. The combination of thecardinality restrictions and preconditions is essential for the reasoning tasks described in Sec-tion 4.4. It allows to query or state subconcept relations between a plan and its child plans.This combination is achieved by restricting the specific world concept of each plan with axiomsas described by Figure 4.9. Figure 4.10 shows the graph, which describes the complete world

35

4 Implementation

concept for the Simple Attack plan. It requires that exactly one agent is participating in theSimple Attack plan, that this agent is assigned to the Attack task, and that it has the ball.It is allowed to use the Ball concept, instead of a ball individual, because the Ball concept isdefined as nominal with only one individual. The world concept of the Clearance plan is the

Simple AttackWorld Agent InRel Attack

SimpleAttackBall

hWPexactly 1

hasInRelationsome

hasBallsome

inRelPlanvalue

inRelTaskvalue

Figure 4.10: Graph Describing the Simple Attack World

same concept, except that the plan and task individuals are Clearance and Defend, instead ofSimple Attack and Attack, respectively. Therefore, it is impossible to execute both plans at thesame time. On the one hand both plans require a participating robot to posses the ball andon the other hand those agents have to be disjoint, due to the structure of the Simple Strategyplan. Reconsidering Axiom 4.30 in combination with the world concepts of the Simple Attackplan and the Clearance plan, the problem arises, that a description logic reasoner deduces theunsatisfiability of the Simple Strategy plan’s world concept. The reason for this conclusion in-cludes the axioms 4.28–4.30 and the world concepts of the Simple Attack plan and the Clearanceplan. Basically, two sub plans of the Simple Strategy plan require a robot to posses the ball.The ball can only be possessed by one robot and it is impossible that one robot is executingboth sub plans. The problem exists, because Axiom 4.30 is only an approximation of the realplantype semantics. The workaround for this limitation is described in Section 4.4.3.

The ALICA ontology introduces the World concept, which subsumes the DomainWorld conceptof the MSL ontology. The World concept allows for domain independent restrictions on theset of possible world states. The DomainWorld concept is the equivalent for domain specificrestrictions. Therefore, all plan specific world concepts should be subsumed by the DomainWorldconcept. In case of the MSL domain three restrictions are made:

DomainWorld vhasWorldPart exactly 1 Balland hasWorldPart exactly 1 Fieldand hasWorldPart exactly 1 RefboxSituation (4.31)

4.4 Reasoning Tasks

The reasoning tasks, covered by this thesis, are not exhaustive in any way. They are chosen toobtain a proper impression of the applicability of SROIQ in the context of ALICA programs.This section describes the details of the reasoning tasks and how they are implemented. As

36

4.4 Reasoning Tasks

there are three reasoning tasks, this section is divided into three subsections. Subsection 4.4.1describes the problem of cyclic plans. Subsection 4.4.2 explaines, why In relations should belocal in a certain sense. The most complex reasoning task, determining whether a plan is sound,is investigated in Subsection 4.4.3. The utilised description logic reasoner is called Hermit [39].It fully supports SROIQ, is compatible to version 3 of the OWL-API [22] and, except of somebuild-ins, it supports DL-Safe SWRL rules. Beside Hermit, these properties are only met bythe description logic reasoner Pellet, which, for some unknown reason, is unable to classify theABox ontology.

4.4.1 Cyclic Plans

ALICA programs are modelled as rooted directed acyclic graphs of plans and interpreted astrees of plans at runtime. The connections between plans are represented by their states, whichcontain plantypes. Plantypes are sets of plans, which are all modelled for the same purpose. Ifit is possible to traverse the directed graph along a chain of plans, which contains the same plantwice, the chain includes a cycle. Some interesting questions arise in the context of cooperationand cycles. Are robots allowed to cooperate, if they execute the same plan on a different level ofrecursion? What does it mean for robots executing a plan on level 3, if that plan was successfulexecuted by some robots on level 2? However, since the semantics of cycles is not defined withinALICA, cycles are strictly forbidden.

In Subsection 4.1.1 the axiomatic description of cyclic plans is given. In order to classify cyclicplans and create a set with all cyclic plans, the description logic reasoner is asked to classify theABox ontology and to extract all individuals, which are classified as cyclic plans. This procedureis straight forward, due to the interfaces defined by the OWL-API [22] and the compatibility ofHermit to these interfaces.

4.4.2 Locality of In Relations

One of the elementary principles of ALICA is locality. Robots, participating in an ALICAprogram, do not consider the state of the whole team. Instead, they only solve the problems, inwhich they are directly involved. The task allocation problem, for example, is only solved forthe plans, in which the solving robot is participating. This behaviour is very natural for humanbeings, too. An attacking human football player does not care about the positioning details of itsdefending team mate. Due to the locality principle of ALICA, the same goes for football playingrobots. The advantages of the locality principle is the reduction of the problem complexity fora single robot at runtime and that a human being, which is modelling an ALICA program, isable to focus on one plan, without considering conditions of other parts of the ALICA program.

Among other measures, the instances of the In relations have to be local, in order to achieve thedescribed locality. An In relation In(a, p, t, s) is local, if, and only if, the parameter p denotesthe same plan, the In relation’s condition is part of. In the ABox ontology, the conditions areencoded into subconcepts of the DomainWorld concept.

It is not possible to state the locality restriction of In relations within SROIQ or SWRL rules,because it is unknown how the inRelPlan role is integrated into the specific world concept

37

4 Implementation

descriptions. The integration depends on the user and how they uses in advance unknownconcepts and roles of the domain ontology in combination with the inRelPlan role. In case of aservice robot domain, for example, the condition could be described by the following axiom:

CoffeeWorld v hasWorldPart some (Kitchenand (Inverse(isInside) some (Agentand hasInRelation some (inRelPlan value getCoffee)))

The concept Kitchen and the role isInside are domain specific and cannot be encoded into theALICA ontology. So instead of utilising a description logic reasoner, the locality check of Inrelations is done by a simple algorithm. The algorithm utilises the OWL-API to determine theoccurrences of the inRelPlan role in each specific world concept description and compares theplan of the inRelPlan role with the plan, the specific world concept is part of. Missmatches arereported to the user interface of the Plan Designer.

4.4.3 Sound Recursive Task Assignments

The hierarchically soundness property of a plan, as defined by Skubch [60], is sufficient to avoidconflicting task assignments between team members. A small example for such a conflict isillustrated in Figure 4.12. The team of robots include robot a, b, and c. The ALICA program issimplified to the parts, which are essential to this example. The arrow pointing from plan P1 toplan P2, e.g., means that a robot needs to be assigned to task τ1 of plan P1, in order to executeplan P2.

P1

P2 P3

P4 P5

a, b, c

a, bc

τ1 τ2

τ3 τ4a b

⊥(a) Robot a detects a conflict

and tracks back.

P1

P2 P3

a, b, c

b, ca

τ1 τ2

(b) Robot a computes a conflictfree allocation.

P1

P2 P3

a: a, b, cb: a, b, cc: a, b, c

a: b, cb: a, cc: a, b

a: ab: bc: c

τ1 τ2

(c) Team members have conflicting al-locations.

Figure 4.12: Origin of Conflicting Task Assignments

In Figure 4.12a, robot a encounters a conflict during the computation of a task allocation andtracks back to plan P1, in order to find a conflict free allocation. The reason for the conflictcould be rooted in the precondition of plan P4. For example, the precondition demands thatthe executing robot posses the ball. Robot a avoids the conflict, with the alternative allocation,shown in Figure 4.12b. This is possible, because of the locality principle of ALICA. The principleallows, that robot a does not compute the details of the allocation of its teammates in plan P3.A global allocation problem arises, because no team member posses the ball. As a result, everyrobot computes an allocation, where itself is executing plan P2. The inconsistent task allocationsof all team members are shown in Figure 4.12c.

38

4.4 Reasoning Tasks

Unsatisfiable conditions are not the only reason for inconsistencies in the task allocations ofthe team. Imprecise sensor values and sensor noise lead to different belief bases for each teammember. If the differences between the belief bases are big enough, the task allocation resultsmay differ, too. However, ensuring the soundness property of plans avoids one of the majorreasons for inconsistent task allocations among team members. Plan p is sound, if, and only if,a valid task allocation for every child plan exists independently of the computed task allocationfor plan p. Reconsidering the example in Figure 4.12, plan P1 would be sound, if it requires allrobots assigned to task τ2 to posses the ball. In general, the soundness property can be achievedby loosing the conditions of child plans, tighten the condition of the plan itself, or lifting someconditions up the plan hierarchy.

In order to determine, whether a plan is sound, the specific world concept of this plan is examinedin comparison to the specific world concepts of its child plans. As described in Section 4.3, aspecific world concept describes the possible states of the world, in which a corresponding planis executable. Therefore, in order for a plan to be sound, the set of its possible world states hasto be a subset of all sets of possible world states of its child plans. Let World X denote theconcept of possible world states of the plan X. Then, it is necessary, that the following axiomshold, in order for plan P1 to be sound:

World P1 vWorld P2 uWorld P3 (4.32)World P3 vWorld P4 uWorld P5 (4.33)

Axioms 4.32 and 4.33 are necessary, but not sufficient for plan P1 to be sound. The fact, thatthe robots assigned to task τ1 of plan P1 are the only robots which can execute plan P2, is notincluded in the description of World P2. Descriptions of specific world concepts are restrictedto local conditions and cardinalities. The relation between the set of robots in plan P1 and P2 isonly given by the structure of the ALICA program. Plan P2 could be reused in another branchof the ALICA program, where it is not a child plan of plan P1. Therefore, it is necessary torequire the Axiom 4.34 independent from subconcept axioms like 4.32 and 4.33.

iWP some World P2 and hasInRelation some (inRelPlan value P2)v iWP some World P1 and hasInRelation some (inRelPlan value P1

and inRelTask value τ1) (4.34)

Axiom 4.34 only refers to the child plan relationship between P1 and P2. The necessary andsufficient set of axioms, which have to hold for P1 to be sound, includes axioms 4.32, 4.33 andan axiom like 4.34 for each child plan relationship in Figure 4.12a. The algorithm, which createsthe set of axioms, is traversing the plan tree hierarchy and adds two subconcept axioms foreach child plan relationship: one subconcept axiom between the specific world concepts andone subconcept axiom between the sets of robots. In order to check, whether P1 is sound, thedescription logic reasoner is asked, if the set of axioms is entailed by the ABox ontology.

At the end of Section 4.3, the impossibility of defining the semantics of plantypes within SROIQor SWRL is described. A consequence of this restriction is, that the algorithm, which createsthe necessary and sufficient axiom set for checking the soundness property of a plan, needsto handle the semantics of plantypes by creating alternative sets of axioms. Therefore, thealgorithm searches for a set of axioms, which is entailed by the ABox ontology, until it has

39

4 Implementation

found one, or all sets were tried. The corresponding pseudo-code is shown in Algorithm 1. Thealgorithm is based on a depth-first search. The search nodes are expanded as long as further childplantypes exist. Unexpandable search nodes include all axioms necessary and sufficient to testthe soundness property of the given plan. The set of axioms is extended in the Expand-Method,depicted in Algorithm 2.

Algorithm 1 Check-Soundness (plan, ontology)1: stack ← Push (Initial-Node (plan))2: while ¬Empty (stack) do3: node←Pop (stack)4: if Expandable (node) then5: stack ←Push-All (Expand (node))6: else7: if Goal-Test-[Exists|Entails] (node, ontology) then8: return true9: end if

10: end if11: end while12: return false

Algorithm 2 Expand (node)1: // Chooses the next combination of plans realising the plantypes.2: plans← Next-Combination (Plantypes (node))3: while ¬Empty (plans) do4: for each plan in plans do5: successor ← Plantypes (plan)6: successor ← World-Subconcept-Axiom (node, plan)7: successor ← Agent-Subconcept-Axiom (node, plan)8: successor ← Add-Axioms (node)9: successors← Insert (successor)

10: end for11: plans← Next-Combination (Plantypes (node))12: end while13: return successors

The question, whether a valid task allocation for a plan and all its child plans exists, is closelyrelated to the soundness property. Instead of asking the description logic reasoner, whether theset of axioms is entailed by the ABox ontology, the set of axioms is added to the ABox ontology.Thereby, the specific world concepts are potentially restricted by the introduced subconceptaxioms. Afterwards, the description logic reasoner is asked, if any of the specific world conceptsis unsatisfiable. If that is the case, there is no possible state of the world in which the executionof the corresponding plan is allowed. Both options are insinuated in Line 7 of Algorithm 1.The semantic difference between both options is that the soundness property requires a validand recursive task allocation for all possible world states of a plan and the existential variantrequires, that a valid and recursive task allocation for at least one possible world state exists.

40

4.5 Integration into the Plan Designer

4.5 Integration into the Plan Designer

In this section, the user interface part of this thesis and its integration into the Plan Designeris described. A preliminary step for the integration was the simplification of the EMF model ofthe Plan Designer. Originally, the EMF model included elements like connection points betweenstates and transitions, which increased the model size without any benefit. Furthermore, theconnection between entry points and their initial states were represented as transitions, whichwere allowed to be annotated with conditions. These and some other differences between thetheory of ALICA and the EMF model was removed and fixed within this thesis, in order tounify the EMF model with the ALICA ontology. As a result of the unification, the creation ofthe ABox ontology is reduced to a simple parsing process, with special handling of annotatedconditions. The file size reduction of the serialised EMF model is a welcome side effect. Thefiles are reduced to half the original file size, depending on the specific plan.

1.

2.

3.

Figure 4.13: User Interface of the Reasoning Support Plugin

The reasoning capabilities provided by this thesis are accessible through the user interface, shownin Figure 4.13. The interface is composed of three indicated parts. The first part is a simpletext field accompanied with a button, which triggers the reasoning process. Before it is possibleto press the button, it is necessary to type a plan name into the text field. The input of the planname is assisted by an auto-completion mechanism. The plan name determines the root planof the investigated ALICA program. The results of the reasoning process are presented by amaster-detail interface, which consists of the second and third interface part. If an inconsistencyor another problem is encountered during the reasoning process, a corresponding category islisted in the master part (2.). Clicking on a category will show a list of individuals or conceptsin the details part (3.). For example, choosing the category for unsatisfiable concepts providesa list of all unsatisfiable concepts. Each entry of the list is an expandable section. If a section isexpanded, it shows a list of axioms, which explains why the corresponding concept or individualis involved in a certain problem. Due to these explanations, the user is able to fix seriousmodelling failures of its ALICA program.

The Plan Designer represents the condition axioms through simple editable strings. The de-scription logic reasoning plugin of this thesis, is only one among many plugins and algorithms,which uses and processes these condition strings. As a consequence, all plugins and algorithmshave to agree on the same syntax. First-order logic provides the syntax of choice, because

41

4 Implementation

it provides enough expressivity for the most purposes and subsumes the more simple syntaxof propositional logic. In order to adapt this policy, a full-fledged ANTLR-based first-orderlogic grammar is utilised to parse the condition strings. ANTLR, ANother Tool for LanguageRecognition, is a framework capable of generating LL(*) recursive-descent parsers from a givengrammar [43]. The developed grammar is capable of understanding first-order and propositionallogic formulae. Unfortunately, parsing and converting first-order logic formulae into SROIQconcept descriptions is impossible for certain first-order logic formulae. In contrast to SROIQconcept descriptions, first-order logic formulae can be undecidable and are therefore not alwaysexpressible within SROIQ. The question is whether a given first-order logic formulae is decid-able and convertible to a SROIQ concept description. The author conjectures this decision tobe unfeasible without restricting to a certain subset of first-order logic formulae. Utilising pat-terns of first-order logic formulae, which origin from the first-order semantics of SROIQ, couldbe a feasible way to recognise a lot of convertible formulae. Related work was done by Tsarkovand Horrocks [70]. They compared the performance of first-order and description logic reasonersand therefore transformed benchmark ontologies into first-order logic syntax. However, provid-ing an appropriate solution for the stated decision problem is out of the scope of this thesis.Instead it is assumed, that the condition strings comply with the Manchester Syntax of OWL 2.The Manchester Syntax is chosen, because it is a good compromise between compactness andhuman readability.

The general mapping between the entities of the Plan Designer’s EMF model and the conceptsand individuals of the ontologies is realised by a simple dictionary mechanism. The mappingof the dictionaries is surjective. It allows to provide several names for the same concept orindividual and thereby makes it unnecessary to touch the ontologies in case of slight changeswithin the EMF model. Furthermore, it provides an interface for other parts of the Plan Designerto integrate their notations into the description logic reasoning plugin, without any dependencyto libraries like the OWL-API.

The MSL ontology and the ALICA ontology are defined separately, because it should be possibleto exchange the MSL ontology against another domain ontology. In order to exchange thedomain ontology, the new domain ontology has to be provided locally and some entries ofa configuration file have to be adjusted. Using other domain ontologies, which are providedthrough the web, as it is common for the research field of semantic web, is not supported yet.An interesting European research project pointing in this direction is RoboEarth [72]. The aimof this project is to provide a database for different kinds of knowledge about actions and objectsusable for connected autonomous robots. Through the service, provided by RoboEarth, robotscan exchange their knowledge about everyday manipulation tasks, such as opening a cupboard.

42

5 Discussion

Chapter 4 describes the ALICA ontology, the MSL ontology, the creation process of the ABoxontology, and the implementation of the reasoning tasks. The included explanations mentionseveral related difficulties and not all are solved by this thesis. In this chapter, some of theproblems are further investigated to address the question of the applicability of a descriptionlogic based reasoning support for ALICA. The investigation of the encountered problems isenriched with more general aspects of knowledge representation, which are inextricably linkedwith the capabilities of the applied reasoning techniques.

5.1 Five Roles for Knowledge Representations

An insightful article is given by Davis, Shrobe, and Szolovits [12]. They define five relevant rolesfor knowledge representations. The adequacy for fulfilling the different roles gives a knowledgerepresentation its own profile. The five roles are captioned by Davis, Shrobe, and Szolovits asfollows:

Surrogate Each knowledge representation surrogates things of the real world. In order tomeasure the adequacy of a knowledge representation as surrogate, questions related to thesurrogated real thing have to be answered. What should be surrogated? What aspectsand properties of the real thing are represented and which are omitted? How exact is therepresentation?

Ontological Commitment It is very important to control and to know which aspects of thereal thing are omitted by the corresponding knowledge representation, as it is impossibleto represent the real thing perfectly. Omitting aspects of the real thing guides humanbeings and machines to focus on aspects which are considered to be relevant. The set ofaspects represents a commitment to a certain point of view and is denoted as ontologicalcommitment of the corresponding knowledge representation.

Fragmentary Theory of Intelligent Reasoning In order to define the knowledge represen-tation’s role as fragmentary theory of intelligent reasoning, three main questions shouldbe answered. What is intelligent reasoning? What inferences are sanctioned? Which in-ferences are recommended? The answer to the first question cannot be given easily. Arephrased version of the question facilitates to give an answer: Which conclusions shouldbe drawn?

Medium for Efficient Computation Knowledge is useless if it is impossible to reason a-bout it. Therefore, the representation should facilitate a computational efficient reasoningprocess. The representation’s structure could be especially appropriate to be processed byreasoning machines or the recommendation of some inferences aim to favour conclusions,which are drawn more efficiently than others.

43

5 Discussion

Medium of Human Expression A knowledge representation defines the language we use inorder to communicate with machines and each other. It should be expressive enough tosay everything we want and it should be easily enough to speak and understand it withouttoo much effort.

Some of the roles are contrary. Efficient computational properties and exceptional expressiv-ity, for example, are hard to combine. According to Levesque and Brachman [31], a generaltrade-off between these two goals exists. As stated by Schreiber [58], ontologies emphasise thefirst, second, and fifth role. Additionally, the well-defined semantics of the common underlyingdescription logics provides precise answers to the questions concerning the fourth role. Comparedto other knowledge representation and reasoning techniques, only the computational efficiencyof description logic reasoning seems to be neglected.

During the modelling of ALICA programs usually no time limit exists. At a pinch, it wouldbe acceptable if the reasoning process takes days, but fortunately an ALICA program of ap-proximately 10 plans takes less than one minute. A crucial aspect is the maximum numberrestrictions used to represent the maximum cardinalities of entry points. Assuming a largemulti-agent scenario it is conceivable, that an entry point with a maximum cardinality of 1000agents exists. Hence, it would be necessary to reason about axioms like hasWorldPart max1000 ForagingAgent. The reasoning algorithm described by Horrocks, Kutz, and Sattler [25]transforms axioms into their negative normal form, which in this case is hasWorldPart min 1001ForagingAgent. In case of Hermit, an array of that length is created, in order to represent andreason about the anonymous concept. In practice, this induces two problems. A minor problemis that the reasoner crashes if it should handle number restrictions with a maximum number ofagents, equal to the largest representable integer. The transformation to the negative normalform induces an overflow and as a result, the attempt to create an array of negative size pro-duces a corresponding exception. Nevertheless, such a large number of agents is very unlikely,nowadays. Another problem is the vast amount of memory used to create the array. Eitherthe java virtual machine creates an Out-Of-Memory-Exception or the reasoning time increasestremendously, just because of one maximum number restriction. From a more pragmaticallypoint of view, the issue is less serious than it seems, because ALICA is only proven to scale upto a number of 100 agents so far. One maximum number restriction for 100 agents increasesthe reasoning time to several minutes. Therefore, completing the reasoning tasks for an ALICAprogram with several maximum number restrictions of a similar amount of agents should takeless than a day.

5.2 Limits of Expressiveness

SROIQ is currently one of the most expressive description logics, but as with all descriptionlogics, the focus is on decidability. As a result, undecidable logics, like the first-order logic,are more expressive than SROIQ. In Chapter 4, several problems with describing the modelof well-formed ALICA programs and the semantics of certain ALICA elements are described.Table 5.1 summarises the problems, whose reason is the limited expressiveness of SROIQ.Facing the listed issues, it is obvious that SROIQ’s expressiveness is insufficient in order toprovide a proper reasoning support for ALICA. Fortunately, most of the listed issues can be

44

5.3 Open World versus Closed World Assumption

handled with the complementary expressive power of SWRL rules. Altogether, only two issuesremain unsolved by the combination of SROIQ with SWRL rules. Firstly, it seems to beimpossible to restrict the SucceededRel concept in such a way, that the connected task has tobe annotated to an entry point of the connected plan. Secondly, reasoning with the correctsemantics of plantypes demands for disjunction over subconcept axioms.

Issue SWRLTransitions connect states only within a plan. !Synchronisations only happen within a plan. !A task is at most one time annotated at a plan. !Consistency of entry point cardinalities (min ≤ max). !Tree-shaped ALICA programs with complex isChildPlan role. !Relations between the parameters of the In relation. !Relation between task and plan of a Succeeded relation. %Plantype semantics needs disjunction over subconcept axioms. %

Table 5.1: Summary of the encountered limits expressing ALICA within SROIQ.

Up to this point the combination of SROIQ and SWRL rules are a pretty sustainable option toprovide ALICA with a description logic reasoning support, especially since the unsolved issuescan be tackled by some complementing algorithms, as implemented for the reasoning task aboutthe sound recursive task assignment. Two more general problems contradict the utilisation ofSROIQ. The open world assumption, made by SROIQ, is inappropriate in the context ofALICA and increases the risk of ontological overcommitment. Both problems are elucidated inthe next two sections.

5.3 Open World versus Closed World Assumption

In order to explain the open world and some other common assumptions, an example from Russelland Norvig [51] is given. On a black board at the campus four courses are listed: CS 101, CS 102,CS 106, and EE 101. Giving the reasoning task of determining the number of existing coursesto a description logic reasoner, the reasoner will consider the knowledge base, represented bythe black board, and answer that the number of courses is between one and infinity. Makingthe open world assumption, no evidence exists, that the four courses on the black board are notfour different names for a single course and no evidence exists, that an infinite number of othercourses exists, which are not noted on the black board. Therefore, the answer of the reasoner isright. The closed world assumption is complementary to the open world assumption. Giving thesame reasoning task to a data-base system, which is usually making the closed world assumption,the answer will be four. Under the closed world assumption, it is assumed that the knowledgebase is always complete, so the existence of more courses than noted on the black board is notadmissible. Additionally, data-base systems often make the unique name assumption. Accordingto the unique name assumption, different names are pointing to different entities. As a result,the four names cannot be the names of a single course. In general, following the open worldassumption means that nothing can be deduced as false or true without evidence. Under theclosed world assumption, everything unknown is considered to be false.

45

5 Discussion

In the context of reasoning about the structure of ALICA programs, the closed world assumptionis much more appropriate than the open world assumption. There is nothing unknown abouta given ALICA program. Every element is known and all connections between the elementsare given. Furthermore, because of the open world assumption and the missing unique nameassumption, a large effort is necessary, in order to render the ABox ontology inconsistent incase of a violation of the conditions for well-formed ALICA programs. An entry point withoutan annotated task, for example, would not create an inconsistency, because the reasoner hasno evidence to belief that the entry point is different from another entry point, which has atask annotated. In fact, the reasoner assumes to know, that no entry point without annotatedtask exists and therefore deduces the actual inconsistent entry point to be equivalent to anotherconsistent entry point. In order to forbid the reasoner to make such conclusions, the unique nameassumption is introduced for the ABox ontology by stating that all individuals are disjoint. Alot of additional axioms are necessary to close the open world appropriately. The list includescovering axioms, closure axioms, domain and target restrictions for roles, number restrictions,negative role assertions for individuals, and the definition of nominals. Especially the last twokinds of restrictions are coupled with a great deal of effort, since the assertions have to be statedfor a lot of individuals and cannot be included into the ALICA ontology. An extreme exampleis the classification of all states, which are not connected to an entry point, whether directly ortransitively. It would be necessary to define the EntryPoint concept as nominal, which includesall entry point individuals introduced by the given ALICA program. The same measure would benecessary for the State concept. Furthermore, for each pair of entry point and state individuals,whose connection through a hasReachableState role cannot be deduced, the connection needsto be negated. The definition of the nominals ensures that there are no unknown entry pointsor states, which could introduce an unknown connection to a certain state. The negation ofirreducible hasReachableState connections ensures, that all hasReachableState connections areknown. Making all these assertions and restrictions is a lot effort and should be done by areasoner.

5.4 Ontological Overcommitment

Another argument against the utilisation of SROIQ is the risk of ontological overcommitment.Ontological overcommitment is mentioned by Schreiber [58] and related to the second role ofknowledge representations. A knowledge representation is ontological overcommitted, if thepoint of view defined by the given axioms is more restrictive than necessary. If an ontologyabout people, for example, requires that everyone has exactly one first name, middle name, andsurname, it is probably overcommitted. A lot of people have several additional middle namesand some people do not have a middle name, so that it is more appropriate to drop any numberrestrictions on the middle names. Nevertheless, it would be impossible to deduce, that twodifferent people have the same name, because the reasoner has no evidence to belief that, giventwo people, all middle names are known. The needed evidence could be provided by introducinga nominal concept for middle names and negating every connection from the two people tomiddle names, which does not belong to their names. Similar to the example of unconnectedstates, it is a lot of effort and the middle name nominal must be extended for every new middlename encountered. Therefore, it is very seductive to accept the overcommitment of the ontology

46

5.5 Domain Specific Reasoning Capabilities

and require number restrictions for middle names. As a consequence, the reasoner has evidenceto deduce, that two people have the same name, because the maximum number of middle namesfor both people is reached and therefore all middle names are known. As described before, a lot ofrestrictions have to be made in order to close the open world in the context of ALICA programs.The abundance of restrictions increases the risk of ontological overcommitment, because it isseductive to save labour by using more general and restrictive axioms. Furthermore, the largenumber of restrictions increases the ontologies complexity, which again increases the number ofmodelling failure like unintended overcommitment.

5.5 Domain Specific Reasoning Capabilities

In the context of ALICA’s application domains, which often include autonomous mobile robots,the open world assumption is much more appropriate. The knowledge of robots about theirenvironment is always incomplete, due to limited sensor ranges and precision. In this case, theproblem is found elsewhere. Chapter 3 mentions that it is not possible to express the regionconnection calculus within SROIQ and SWRL rules. Although the focus of this thesis isnot on the specific needs for application domains of ALICA, it is alarming, that the literatureresearch did not provide an ontology based reasoning technique useful for the MSL domain.For the MSL domain, temporal-spatial reasoning probably matches the requirements best. Asfor human football strategies, timing is very important for robotic soccer. The robots of theMSL, for example, know how much time of a half time is left. Adjustments of the strategiesaccording to the goal differences and the remaining time could improve the overall performance.Adjusting the strategy to a more aggressive and risky attack plan, requires a negative goaldifference shortly before the end of the second half. Additionally to this simple example, morecomplex coordination between team mates could be enabled. In order to play a one-two, severaltiming conditions have to be met. Supported with temporal-spatial knowledge, a reasoner couldinvestigate such conditions and, for example, inference whether certain events may happensimultaneously.

At the end of this discussion it is appropriate to remind, that ontology engineering is notdeterministic. There are always different ways of saying the same thing and even more differentways to provide a reasoner with the necessary evidence to sanction certain inferences. In order tohelp ontology authors to avoid difficulties and mistakes, design patterns for ontology engineeringexist. They represent common ways and best practises to model complex knowledge. In thisthesis, for example, the design pattern for n-ary relations [42] is applied for the In and Succeededrelations. The importance of design patterns is commonly known from software engineering andemphasised by the fact that for the third time a workshop for ontology design patterns [16] willbe held during the International Semantic Web Conference [7] in November 2012. Althoughcommon design patterns are considered, it is not ruled out completely, that other ways ofmodelling the ALICA ontology may exist, so that some of the unsolved problems may be solved.

47

6 Summary

Within this thesis, the applicability of a description logic based reasoning support for ALICAis investigated. In order to implement such a reasoning support, the EMF model of the ALICAPlan Designer was adjusted, according to the theory of ALICA. The knowledge base for thereasoning about ALICA and the MSL application domain is represented by two correspondingontologies. Due to a lack of suitable paragons, both ontologies are engineered from scratch.With SROIQ one of the most expressive description logics is used to capture the complexityof ALICA programs. The description logic reasoner Hermit implements the state-of-the-arthyper-tableau algorithm [38] and is utilised to execute several reasoning tasks.

Especially three reasoning tasks of different complexity are investigated. The first is classifyingplans, which are involved in plan hierarchy cycles of a given ALICA program. Modelling thetree structure of ALICA programs turned out to be more difficult than expected. Thanks tothe complementary expressiveness of SWRL rules, it was possible to craft the knowledge base,accordingly. Equipped with the engineered ALICA ontology and the description logic reasonerHermit, the first reasoning task is done with ease.

The second reasoning task is to check whether all individuals of the In relation are locallyrestricted to their corresponding plan. No matter if the individual is named or anonymous, thelocality is met if and only if the plan individual connected to its inRelPlan role is the same planthe In relation individual is annotated to. The way the inRelPlan role is integrated into thecondition of a plan depends on the domain ontology. Therefore, it was not possible to encode thelocality restriction into the ALICA ontology. Instead, a simple algorithm utilised the OWL-APIto extract non-local instances of the In relation.

The third reasoning task is the most complex one. It includes the sub task to check, whethera plan is sound. This is necessary to avoid conflicting task allocations between team members.Unfortunately, the semantics of plantypes demands for disjunctions over subconcept axioms.This is beyond the expressiveness of SROIQ and SWRL rules. The provided solution includesan algorithm, which comprises the actual reasoning queries, which are handed to the descriptionlogic reasoner.

In order to create the corresponding ABox ontology for a given ALICA program, an algorithmis developed, which is able to create the ABox ontology independent of the given domain spe-cific ontology. The developed software is designed as plugin for the ALICA Plan Designer. Alight weight user interface facilitates the use of the provided reasoning capabilities and providesexplanations for found modelling mistakes in a given ALICA program.

6.1 Conclusion

Altogether, the three reasoning tasks are solved, but only with the help of SWRL rules and sev-eral workarounds. During the ontology engineering, further difficulties were located. The open

49

6 Summary

world assumption, made by description logic reasoners, is inappropriate for reasoning aboutALICA programs and increases the risk of ontological overcommitment. Considering the specialneeds of the MSL domain, no suitable temporal-spatial reasoning calculus, which is express-ible within SROIQ and SWRL rules, could be found. Another critical point is the requiredcompatibility to other reasoning mechanisms, induced by the integration into the ALICA PlanDesigner. The common syntax for condition strings is the syntax of the first-order logic. Inorder to create an accurate ABox ontology, it has to be decided, whether a given first-order logicformula is convertible into a description logic concept description. Without greater restrictionson the set of convertible formulae, it is conjectured that the stated decision problem is undecid-able. Finally, it is worth noting, that the time needed to run a complete test of a given ALICAprogram is acceptable, but far away from any real-time requirements of the MSL domain.

6.2 Future Work

As described before, several problems distributed over a wide spectrum of topics are identified.Some hints for starting points of further research are given in this section. The hints could leadto solutions for some of these problems and are separated into two categories: improving thedescription logic approach or switching to other reasoning mechanisms. From the perspectiveof the author, the latter option is preferable to answer the question whether other reasoningapproaches pose similar problems.

6.2.1 Improvements

Description Graphs Most problems, which require the complementary expressiveness of SWRLrules, can be reduced to the need to model things which are arranged in squares or trian-gles. A pair of states, for example, connected by a transition, always belongs to the sameplan. Similar needs exist in the field of medical ontologies. In order to describe a thumb,it is necessary to state that two bones, connected by a joint belong to the same thumb.An alternative way of describing such non-tree shaped models is provided by descriptiongraphs [40]. Description graphs extent the expressiveness of SROIQ by the possibility ofdescribing non-tree shaped models on concept level, instead of individuals level. From themodelling perspective, this capability makes description graphs easier to use than SWRLrules [36]. The utilised description logic reasoner Hermit is the only available reasoner, ca-pable of reasoning with description graphs. However, a certain role separation is necessaryto retain the decidability of the underlying reasoning. Whether such a role separation canbe accomplished for the ALICA ontology needs to be investigated.

Pellet Pellet is the only description logic reasoner, beside Hermit, which should be capable ofexecuting the described reasoning tasks for the created ABox ontologies. Furthermore, itimplements almost every SWRL build-in, which provides it with the potential capabilityof classifying entry points with inconsistent cardinalities. Unfortunately, the reasoner wasnot able to classify an ABox ontology in practise. Due to the implement SWRL build-ins,the problem may be worth a further investigation.

50

6.2 Future Work

Explanations Each modelling failure recognised by the reasoning process is presented to theuser, accompanied with a corresponding explanation of the reasoner. The explanationshould help the user to identify the reason of the encountered problem, so that theycan fix it. Most violations of conditions for well-formed ALICA programs result in aninconsistent ontology. Explaining the reason for inconsistent ontologies is a hard task fordescription logic reasoners [23]. Another option is to create specific concepts for each kindof violation, but that would be a lot of effort and it would be very hard to capture all formsof violations. So the currently chosen way is to hope that the reasoners explanations areunderstandable enough for the user. Cases in which this hope remained unfulfilled, alwayshad to do with nominals. The explanation for an inconsistency caused by an unconnectedstate is very opaque, because the only evidence the reasoner has is the fact that there areno more transitions, which could be connected to that state. The only explaining axiom,the reasoner presented, was the nominal concept of the transitions.

The beta version of Protege 4.2 includes a plugin for more sophisticated explanations,which is based on the PhD thesis of Horridge [21]. Explanations normally work on the gran-ularity level of axioms. Therefore, it is possible, that axioms included in an explanationcontain superfluous parts or mask additional explanations within other parts. Horridgedeveloped a mechanism which creates laconic and precise explanations. Laconic explana-tions do not contain superfluous parts and precise explanations are minimal, so that noadditional explanations are masked. Tests for the case of unconnected states created muchmore understandable explanations, than the current approach does. Although no docu-mented API is available for the plugin and therefore the integration includes additionaleffort, the benefit for the reasoning support of this thesis would be worth it.

Performance The time needed to reason about a given ALICA program is acceptable forthe modelling case. In case of the runtime execution during a match of the MSL, thetime is not even near the domains real-time requirements. Nevertheless, it is desirable toexploit the reasoning capabilities at runtime. On the one hand, it is possible to furtherdecrease the reasoning time by adjusting the queries and utilisation of the reasoner. On theother hand, an appropriate scheduling algorithm could exploit unused CPU capacity bytriggering the reasoner on demand. Usually, description logic reasoner can be suspendedand resumed during the reasoning process. This enables the implementation of an anytimereasoning algorithm. In the MSL domain, for example, the goal keeper has comparativelyfew calculations to perform. The currently wasted computing capacity could be used by ananytime planning algorithm, which utilises the reasoning capabilities of a description logicreasoner. Afterwards, the created plans can be distributed among the team members.

6.2.2 Alternatives

Autoepistemic Logic In Chapter 6 it is argued, that the open world assumption is inappro-priate to reason about ALICA programs. The closed world assumption, as the opposite ofthe open world assumption, is too rigorous for application domains like the MSL domain.An alternative solution might be the use of an autoepistemic logic. It is a modal logicwith belief as modal operator. Brachman and Levesque introduce the autoepistemic logicas a way to express default reasoning [10]. Default reasoning sanctions inferences, if the

51

6 Summary

inference is believed to be true and no evidence is given, that contradicts this inference.Instead of denying everything, that is unknown, it allows to draw some conclusions withoutproper evidence. A common example gives the following knowledge base:

Bird(chilly), Bird(tweety)tweety 6= chilly, ¬Flies(chilly)∀x[Bird(x) ∧ ¬B¬Flies(x)→ Flies(x)]

It includes the belief, that every bird, which is not believed to be flightless, can fly. As aconsequence it is deduced, that tweety can fly. The same does not hold for chilly, becauseit is known that it cannot fly. Similar to the given example, a solution to the problem ofclassifying unconnected states could be formulated. In general it is believed, that statesare unconnected and only if a connection from an entry point to a state is known, thestate is classified as connected state. Some research has been done to join description andautoepistemic logics [14], so that autoepistemic logics do not have to be an alternative todescription logics.

First-Order Logic Tsarkov and Horrocks analysed the performance of Vampire [71], a first-or-der theorem prover, in the context of description logic reasoning [70]. Investigating theoption of utilising a first-order theorem prover in the context of ALICA programs couldexpose interesting results and is maybe an alternative to the current approach. Althoughfirst-order logic formulae can be undecidable, most formulae, necessary to reason aboutALICA programs as shown by this thesis, are decidable. Tsarkov and Horrocks also arguethat theorem proving can solve reasoning tasks, which description logic reasoners cannot.Additionally, a more expressive possibility to describe knowledge is given by the underlyingfirst-order logic. The problem of converting first-order logic formulae into description logicconcepts could be spared, too.

Domain Specific Logics Decoupling the reasoning mechanism for ALICA programs and theirapplication domains provides a variety of additional reasoning approaches for the applica-tion domain. In case of the MSL domain, a lot of spatial logics could be investigated fortheir applicability. The Handbook of Spatial Logics is probably a good starting point fora broad literature research [1]. Another argument for a decoupled approach is the possi-bility of using closed world reasoning for ALICA programs. Considering the performanceof common database systems, it is conjectured that this is much more efficient than de-scription logic reasoning. The same applies to the domain specific reasoning. Specialisedreasoning is potentially more efficient than a more general reasoning approach, because ofthe possibility to exploit domain specific knowledge during the reasoning process.

52

Bibliography

[1] Marco Aiello, Ian Pratt-Hartmann, and Johan van Benthem, eds.Handbook of Spatial Logics.1st ed. Springer, July 2007.isbn: 978-1-4020-5586-7.

[2] Minoru Asada et al.Middle Size Robot League Rules and Regulations for 2012.16th ed.RoboCup MSL Technical Committee. Dec. 2011.url: https://docs.google.com/open?id=0B6cdZrEa8IsWZWU2M2M3YzctYjAxMy00ZGRj

LTk0MjctMTJmOGY1ZDA0ZmVh (visited on 08/06/2012).

[3] Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F.Patel-Schneider, eds.

The Description Logic Handbook: Theory, Implementation, and Applications.Cambridge University Press, 2003.isbn: 0-521-78176-0.

[4] Sotiris Batsakis and Euripides G. M. Petrakis.“SOWL: spatio-temporal representation, reasoning and querying over the semantic web”.In: Proceedings of the 6th International Conference on Semantic Systems.Graz, Austria: ACM, 2010, 15:1–15:9.isbn: 978-1-4503-0014-8.doi: 10.1145/1839707.1839726.

[5] Wayne Beaton and Jim de Rivieres.Eclipse Platform Technical Overview.Tech. rep.The Eclipse Foundation, 2006.

[6] Robert Berger.“The undecidability of the Domino Problem”.In: Memoirs of the American Mathematical Society 66 (1966), p. 72.

[7] Abraham Bernstein, Lalana Kagal, Philippe Cudre-Mauroux, and Jeff Heflin.The 11th International Semantic Web Conference.Nov. 2012.url: http://iswc2012.semanticweb.org (visited on 09/02/2012).

53

Bibliography

[8] International Football Association Board.Laws of the Game.Federal International Football Association. 2012.url: http://www.fifa.com/mm/document/affederation/generic/81/42/36/lawsoft

hegame_2012_e.pdf (visited on 07/07/2012).

[9] Nadjet Bouayad-Agha, Gerard Casamayor, Leo Wanner, Fernando Dıez, and Sergio LopezHernandez.

“FootbOWL: Using a Generic Ontology of Football Competition for Planning Match Sum-maries”.

In: Proceedings of the 8th extended semantic web conference on The semantic web: researchand applications.

2011, pp. 230–244.

[10] Ronald Brachman and Hector Levesque.Knowledge Representation and Reasoning.San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2004.isbn: 1558609326.

[11] Cycorp.OpenCyc Knowledge Base 4.0.2012.url: http://www.opencyc.org/ (visited on 09/15/2012).

[12] Randall Davis, Howard Shrobe, and Peter Szolovits.“What is knowledge representation?”In: AI Magazine 14.1 (1993), pp. 17–33.

[13] Premkumar T. Devanbu and Diane J. Litman.“Taxonomic Plan Reasoning.”In: Artificial Intelligence 84.1-2 (1996), pp. 1–35.issn: 0004-3702.doi: 10.1016/0004-3702(95)00091-7.

[14] Francesco M. Donini, Daniele Nardi, and Riccardo Rosati.“Autoepistemic Description Logics”.In: International Joint Conference on Artificial Intelligence, (IJCAI).1997, pp. 136–141.

[15] Alexander Ferrein, Christian Fritz, and Gerhard Lakemeyer.“On-Line Decision-Theoretic Golog for Unpredictable Domains”.In: Proceedings of the 27th Annual German Conference on Artificial Intelligence, (KI).Ed. by Susanne Biundo, Thom W. Fruhwirth, and Gunther Palm. Vol. 3238. Lecture Notes

in Computer Science.Springer Verlag, 2004, pp. 322–336.

54

Bibliography

[16] Aldo Gangemi, Eva Blomqvist, Mari Carmen Suarez-Figueroa, and Karl Hammar.3rd Workshop on Ontology Patterns (WOP2012).Nov. 2012.url: http://ontologydesignpatterns.org/wiki/WOP:2012 (visited on 09/02/2012).

[17] Yolanda Gil.“Description Logics and Planning”.In: AI Magazine 26.2 (2005), pp. 73–84.

[18] Stephan Gspandl, Andreas Hechenblaickner, Michael Reip, Gerald Steinbauer, Mate Wol-fram, and Christoph Zehentner.

“The Ontology Lifecycle in RoboCup: Population from Text and Execution”.In: RoboCup 2011: Robot Soccer World Cup XV.Vol. 15.2011.

[19] Jerry R. Hobbs and Feng Pan.Time Ontology in OWL.W3C. Sept. 2006.url: http://www.w3.org/TR/owl-time/ (visited on 08/06/2012).

[20] Frederik Hogenboom, Bram Borgman, Flavius Frasincar, and Uzay Kaymak.“Spatial Knowledge Representation on the Semantic Web”.In: Proceedings of the International Conference on Semantic Computing.2010, pp. 252–259.doi: http://dx.doi.org/10.1109/ICSC.2010.31.

[21] Matthew Horridge.“Justification Based Explanation in Ontologies”.PhD thesis. University of Manchester, 2011.

[22] Matthew Horridge and Sean Bechhofer.“The OWL API: A Java API for OWL Ontologies”.In: Semantic Web Journal 2.1 (2011), pp. 11–21.

[23] Matthew Horridge, Bijan Parsia, and Ulrike Sattler.“Explaining Inconsistencies in OWL Ontologies”.In: SUM.2009, pp. 124–137.doi: 10.1007/978-3-642-04388-8_11.

[24] Matthew Horridge and Peter F. Patel-Schneider.OWL 2 Web Ontology Language Manchester Syntax.W3C. Oct. 2009.url: http://www.w3.org/TR/owl2-manchester-syntax/ (visited on 07/29/2012).

55

Bibliography

[25] Ian Horrocks, Oliver Kutz, and Ulrike Sattler.“The Even More Irresistible SROIQ”.In: Proceedings of the 10th International Conference on Principles of Knowledge Repre-

sentation and Reasoning.Ed. by Patrick Doherty, John Mylopoulos, and Christopher A. Welty.AAAI Press, 2006, pp. 57–67.isbn: 978-1-57735-271-6.

[26] Ian Horrocks and Ulrike Sattler.“Decidability of SHIQ with complex role inclusion axioms”.In: Artificial Intelligence 160.1–2 (2004), pp. 79 –104.issn: 0004-3702.doi: 10.1016/j.artint.2004.06.002.

[27] Ian Horrocks, Ulrike Sattler, and Stephan Tobies.“Practical Reasoning for Expressive Description Logics”.In: Proceedings of the 6th International Conference on Logic for Programming and Auto-

mated Reasoning (LPAR’99).Ed. by Harald Ganzinger, David A. McAllester, and Andrei Voronkov. 1705.Springer-Verlag, 1999, pp. 161–180.

[28] Ian Horrocks, Peter F. Patel-Schneider, Harold Boley, Said Tabet, Benjamin Grosof, andMike Dean.

SWRL: A Semantic Web Rule Language Combining OWL and RuleML.W3C. May 2004.url: http://www.w3.org/Submission/SWRL/ (visited on 08/01/2012).

[29] Alexander Kleiner, Christian Dornhege, and Andreas Hertle.RmasBench – Rescue Multi-Agent Benchmarking.2011.url: http://kaspar.informatik.uni-freiburg.de/˜rslb (visited on 07/05/2012).

[30] Deutsches Forschungszentrum fur Kunstliche Intelligenz GmbH.IMPERA - Integrated Mission Planning for Distributed Robot Systems.Apr. 2011.url: http : / / robotik . dfki - bremen . de / fileadmin / CONTENT / Flyer / DFKI _ RIC _

IMPERA_EN.pdf (visited on 11/25/2011).

[31] Hector Levesque and Ronald Brachman.“A Fundamental Trade-Off in Knowledge Representation and Reasoning”.In: Readings in Knowledge Representation.Ed. by Ronald Brachman and Hector Levesque.San Mateo, Californien: Morgan Kaufmann, 1985, pp. 42–70.

56

Bibliography

[32] Jeff McAffer and Jean-Michel Lemieux.Eclipse Rich Client Platform: Designing, Coding, and Packaging Java Applications.Upper Saddle River, NJ: Addison-Wesley, 2005.isbn: 978-0-321-33461-9.

[33] Marvin Minsky.“A Framework for Representing Knowledge”.In: The Psychology of Computer Vision.Ed. by P. Winston.McGraw-Hill, New York, 1975,Pp. 211–277.

[34] Knud Moller.SWAN Soccer Ontology.2004.url: http://sw.deri.org/2005/05/swan/soccer/ontology/soccer.owl (visited on

07/21/2012).

[35] Alvaro Moreira, Renata Vieira, Rafael H. Bordini, and Jomi Hubner.“Agent-oriented programming with underlying ontological reasoning”.In: Proceedings of the 3rd International Workshop on Declarative Agent Languages and

Technologies (DALT-05).Ed. by M. Baldoni, U. Endriss, A. Omicini, and P. Torroni.Springer-Verlag, June 2005, pp. 155–170.

[36] Boris Motik, Bernardo Cuenca Grau, and Ulrike Sattler.“Structured Objects in OWL: Representation and Reasoning”.In: Proceedings of the 17th international Conference on World Wide Web.Beijing, China: ACM, 2008, pp. 555–564.isbn: 978-1-60558-085-2.doi: 10.1145/1367497.1367573.

[37] Boris Motik, Ulrike Sattler, and Rudi Studer.“Query Answering for OWL-DL with rules”.In: Web Semantics: Science, Services and Agents on the World Wide Web 3.1 (2005),

pp. 41–60.issn: 1570-8268.doi: DOI:10.1016/j.websem.2005.05.001.

[38] Boris Motik, Rob Shearer, and Ian Horrocks.“Hypertableau Reasoning for Description Logics”.In: Journal of Artificial Intelligence Research 36 (2009), pp. 165–228.

[39] Boris Motik, Rob Shearer, Birte Glimm, Giorgos Stoilos, and Ian Horrocks.Hermit OWL Reasoner.2012.url: http://www.hermit-reasoner.com (visited on 08/16/2012).

57

Bibliography

[40] Boris Motik, Bernardo Cuenca Grau, Ian Horrocks, and Ulrike Sattler.“Representing ontologies using description logics, description graphs, and rules”.In: Artificial Intelligence 173.14 (2009), pp. 1275–1309.

[41] Mark Musen, Matthew Horridge, Natasha Noy, Timothy Redmond, Tania Tudorache,Martin O’Conner, Csongor Nyulas, Samson Tu, and Jennifer Vendetti.

Protege.Stanford Center of Biomedical Informatics Research. 2012.url: http://protege.stanford.edu (visited on 07/05/2012).

[42] Natasha Noy, Alan Rector, Pat Hayes, and Chris Welty.Defining N-ary Relations on the Semantic Web.W3C. Apr. 2006.url: http://www.w3.org/TR/swbp-n-aryRelations/ (visited on 07/18/2012).

[43] Terence Parr.The Definitive ANTLR Reference: Building Domain-Specific Languages.1st ed. The Pragmatic Programmers. Pragmatic Bookshelf, May 2007.

[44] Bijan Parsia and Ulrike Sattler.OWL 2 Web Ontology Language Data Range Extension: Linear Equations.W3C. Oct. 2009.url: http://www.w3.org/TR/owl2-dr-linear/ (visited on 07/30/2012).

[45] M. Ross Quillian.“Word Concepts: A Theory and Simulation of Some Basic Semantic Capabilities”.In: Behavioral Science 12 (1967), pp. 410–430.

[46] David A. Randell, Zhan Cui, and Anthony Cohn.“A Spatial Logic Based on Regions and Connection”.In: Proceedings of the 3rd International Conference ont the Principles of Knowledge Rep-

resentation and Reasoning.Ed. by Bernhard Nebel, Charles Rich, and William Swartout.San Mateo, California: Morgan Kaufmann, 1992,Pp. 165–176.

[47] Sylvie Ranwez.Soccer Ontology.DAML. Apr. 2002.url: http://www.daml.org/ontologies/273 (visited on 09/15/2012).

58

Bibliography

[48] Anand S. Rao.“AgentSpeak(L): BDI Agents Speak Out in a Logical Computable Language.”In: Proceedings of the 7th Workshop on Modelling Autonomous Agents in a Multi-Agent

World (MAAMAW’96).Ed. by Walter Van de Velde and John W. Perram. Vol. 1038. Lecture Notes in Computer

Science.Springer, 1996, pp. 42–55.isbn: 3-540-60852-4.doi: 10.1007/BFb0031845.

[49] RoboCup.RoboCup Foundation.2012.url: http://www.robocup.org/ (visited on 07/05/2012).

[50] Sebastian Rudolph, Markus Krotzsch, and Pascal Hitzler.“Cheap Boolean Role Constructors for Description Logics”.In: Proceedings of the 11th European Conference on Logics in Artificial Intelligence (JELIA).2008, pp. 362–374.doi: 10.1007/978-3-540-87803-2_30.

[51] Stuart Russell and Peter Norvig.Artificial Intelligence: A Modern Approach.2nd ed. Prentice Hall, 2003.

[52] Earl D. Sacerdoti.A Structure For Plans and Behavior.Tech. rep. 109.333 Ravenswood Ave., Menlo Park, CA 94025: AI Center, SRI International, 1975.

[53] Ulrike Sattler.Describing Trees in OWL?June 2012.url: http://lists.w3.org/Archives/Public/public-owl-dev/2012AprJun/0037.

html (visited on 07/31/2012).

[54] Ulrike Sattler.Modal and Description Logics.2011.url: http://www.cs.man.ac.uk/˜sattler/teaching/COMP61132-slides5.pdf (visited

on 07/16/2012).

[55] Andreas Scharf.“Grafische Verhaltensmodellierung fur kooperative autonome Roboter”.MA thesis. University of Kassel, Dec. 2008.

59

Bibliography

[56] Stefan Schiffer, Alexander Ferrein, and Gerhard Lakemeyer.“Qualitative World Models for Soccer Robots”.In: Qualitative Constraint Calculi, Workshop at KI.2006, pp. 3–14.

[57] Manfred Schmidt-Schauss and Gert Smolka.“Attributive concept descriptions with complements”.In: Artificial Intelligence 48.1 (1991), pp. 1–26.issn: 0004-3702.doi: DOI:10.1016/0004-3702(91)90078-X.

[58] Guus Schreiber.“Knowledge Engineering”.In: Foundations of Artificial Intelligence.Ed. by Frank van Harmelen, Vladimir Lifschitz, and Bruce Porter.Elsevier, 2008.Chap. 25, pp. 929–946.

[59] Evren Sirin.“Combining Description Logic Reasoning with AI Planning for Composition of Web Ser-

vices”.PhD thesis. College Park, MD, USA: University of Maryland, 2006.isbn: 978-0-542-96121-2.

[60] Hendrik Skubch.“Modelling and Controlling Behaviour of Cooperative Autonomous Mobile Robots”.PhD thesis. University of Kassel, May 2012.

[61] Hendrik Skubch.“Solving Non-Linear Arithmetic Constraints in Soft Realtime Environments”.In: 27th Symposium On Applied Computing.Vol. 1.ACM, 2012, pp. 67–75.

[62] Hendrik Skubch, Daniel Saur, and Kurt Geihs.“Resolving Conflicts in Highly Reactive Teams”.In: Proceedings of the 17th GI/ITG Conference on Communication in Distributed Systems,

(KiVS’11).Kiel, Germany, Mar. 2011, pp. 170–175.

[63] Hendrik Skubch, Michael Wagner, and Roland Reichle.A Language for Interactive Cooperative Agents.Tech. rep.University of Kassel, Distributed Systems, Mar. 2009.

60

Bibliography

[64] Hendrik Skubch, Michael Wagner, Roland Reichle, and Kurt Geihs.“A Modelling Language for Cooperative Plans in Highly Dynamic Domains”.In: Mechatronics 21.2 (2011), pp. 423–433.issn: 0957-4158.doi: 10.1016/j.mechatronics.2010.10.006.url: http : / / www . sciencedirect . com / science / article / B6V43 - 51NDYV0 - 1 / 2 /

4fcb40d82d704c20132f7ef901b8d337 (visited on 12/18/2011).

[65] Hendrik Skubch, Michael Wagner, Roland Reichle, Stefan Triller, and Kurt Geihs.“Towards a Comprehensive Teamwork Model for Highly Dynamic Domains”.In: Proceedings of the 2nd International Conference on Agents and Artificial Intelligence.Ed. by Joaquim Filipe, Ana Fred, and Bernadette Sharp. Vol. 2.INSTICC Press, Jan. 2010, pp. 121–127.

[66] International Organization for Standardization.Information technology - XML Metadata Interchange (XMI).ISO/IEC 19503:2005-11.2005.

[67] Dave Steinberg, Frank Budinsky, Marcelo Paternostro, and Ed Merks.EMF: Eclipse Modeling Framework.2. Boston, MA: Addison-Wesley, 2009.isbn: 978-0-321-33188-5.

[68] Bill Swartout and Yolanda Gil.“EXPECT: Explicit Representations for Flexible Acquisition”.In: Proceedings of the 9th Knowledge Acquisition for Knowledge-Based Systems Workshop

(KAW’95).Banff, Canada, Feb. 1995.

[69] The Eclipse Foundation.Graphical Editing Framework.2012.url: http://www.eclipse.org/gef/ (visited on 07/12/2012).

[70] Dmitry Tsarkov and Ian Horrocks.“DL Reasoner vs. First-Order Prover.”In: Description Logics.Ed. by Diego Calvanese, Giuseppe De Giacomo, and Enrico Franconi. Vol. 81. CEUR

Workshop Proceedings.CEUR-WS.org, 2003.

[71] Andrei Voronkov and Krystof Hoder.Vampire - A first-order theorem prover.2012.url: http://www.vprover.org (visited on 09/04/2012).

61

Bibliography

[72] Markus Waibel et al.“RoboEarth”.In: Robotics Automation Magazine, IEEE 18.2 (2011), pp. 69–82.issn: 1070-9932.doi: 10.1109/MRA.2011.941632.

[73] Michael P. Wellman.“Formulation of Tradeoffs in Planning under Uncertainty”.PhD thesis. Boston, MA: Massachusetts Institute of Technology, Sept. 1988.

[74] Michael J. Wooldridge.Reasoning about Rational Agents.MIT Press, July 2000,P. 241.isbn: 0262232138.

62

List of Figures

1.1 Application Domains for ALICA . . . . . . . . . . . . . . . . . . . . . . . . . . . 2(a) Rescue Multi-Agent System . . . . . . . . . . . . . . . . . . . . . . . . . . . 2(b) Lunar Test Bed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2(c) Carpe Noctem Football Robot . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.1 Agent Environment Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2 Agents Controlled by FSMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

(a) Single FSM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6(b) Multiple FSMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.3 Simple Golden Goal Plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4 Abstract Part of an ALICA Program . . . . . . . . . . . . . . . . . . . . . . . . . 92.5 The Graphical User Interface of the Plan Designer . . . . . . . . . . . . . . . . . 102.6 ALICA Plan Designer Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 112.7 Knowledge Representation by Semantic Networks and Frames . . . . . . . . . . . 11

(a) Semantic Network about Animals . . . . . . . . . . . . . . . . . . . . . . . 11(b) Frames about Geometric Shapes . . . . . . . . . . . . . . . . . . . . . . . . 11

2.8 An Aperiodic Set of 13 Wang Dominoes . . . . . . . . . . . . . . . . . . . . . . . 162.9 Structures Inexpressible in SROIQ . . . . . . . . . . . . . . . . . . . . . . . . . 17

(a) Fourth Constraint of the Domino Problem . . . . . . . . . . . . . . . . . . . 17(b) Generic Commutative Square . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.1 Qualitative Spatial Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21(a) Relations of RCC8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21(b) Egocentric Qualitative Distances . . . . . . . . . . . . . . . . . . . . . . . . 21

4.1 The Concept Hierarchy of the ALICA Ontology . . . . . . . . . . . . . . . . . . . 244.2 Concept Graph and Axioms for Tree-Shaped ALICA Programs . . . . . . . . . . 27

(a) Plan Concepts and Role Restrictions . . . . . . . . . . . . . . . . . . . . . . 27(b) Role Hierarchy and Assertions . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.3 The Concept Hierarchy Part for Agents’ Plan Participation . . . . . . . . . . . . 284.4 Concepts and Roles for Agents’ Plan Participation . . . . . . . . . . . . . . . . . 284.5 Graph Matched by SWRL Rule 4.25 . . . . . . . . . . . . . . . . . . . . . . . . . 294.6 The Concept Hierarchy of the MSL Ontology . . . . . . . . . . . . . . . . . . . . 314.7 The Areas of a MSL Football Field . . . . . . . . . . . . . . . . . . . . . . . . . . 324.8 The Example ALICA Program Simple Strategy . . . . . . . . . . . . . . . . . . . 344.9 Graph Describing the Cardinality Restriction . . . . . . . . . . . . . . . . . . . . 344.10 Graph Describing the Simple Attack World . . . . . . . . . . . . . . . . . . . . . 364.12 Origin of Conflicting Task Assignments . . . . . . . . . . . . . . . . . . . . . . . 38

(a) Robot a detects a conflict and tracks back. . . . . . . . . . . . . . . . . . . 38(b) Robot a computes a conflict free allocation. . . . . . . . . . . . . . . . . . . 38(c) Team members have conflicting allocations. . . . . . . . . . . . . . . . . . . 38

63

List of Figures

4.13 User Interface of the Reasoning Support Plugin . . . . . . . . . . . . . . . . . . . 41

64