International Journal

on Marine Navigation

and Safety of Sea Transportation

Volume 2

Number 4

December 2008

369

Building of CBR’s DB Using Ontology for a

Collision Avoidance System

G.K. Park, W.G. Kim & J.L.R.M. Benedictos

Mokpo National Maritime University, Mokpo, South Korea

ABSTRACT: We have proposed Fuzzy-CBR to find a solution from past knowledge retrieved from the

database and adapted to the new situation. However, ontology is needed in identifying concepts, relations and

instances that are involved in a situation in order to improve and facilitate the efficient retrieval of similar

cases from the CBR database. This paper proposes the way to apply ontology for identifying the concepts

involved in a new case, used as inputs, for ship collision avoidance support system and in solving for

similarity through document articulation and abstraction levels. These ontologies will be used to build a

conceptual model of a manoeuvring situation.

1 INTRODUCTION

Ship manoeuvring is a part of navigation where

bridge officers develop their skill through years of

experience and knowledge acquisition in able to

understand the relation between his ship and ships

that are within his sight. This understanding provide

him with the necessary idea of what is supposed to

be done and of what is not supposed to be done

before even deciding what precaution or action he

needs to apply to keep his own ship (OS) out of

danger of collision (Lee & Rhee 2001; Im & Park

2005; Na et al. 2003; Park & Benedictos 2006)

There has been ship maneuvering systems

proposed before but they have failed to capture the

expert knowledge in ship maneuvering like the one

captured using ontology. We propose to use

ontology together with CBR in the acquisition of an

expert knowledge in a ship maneuvering system

(Watson. 1998; Iwatani etal. 1994; Tano et al. 1995;

Fojioka et al. 1995; Aadmont & Plaza 1994).

Ontology will be considered as knowledge structures

that will identify the concepts, property of concepts

and relationships among them to enable share and

reuse of knowledge that are needed to acquire

knowledge in maneuvering a ship safely in the

vicinity of other ships (Nossum et al 2005; Sanches

et al. 2005).

In Section 2 we will first discuss the types of

maneuvering situation involving a single target ship

that are most often used by bridge officers that

require basic maneuvering knowledge in order to

understand the situation before taking action based

on past similar experiences. We will then introduce

how ontology can be used to identify the concepts of

ship maneuvering and the relations among these

concepts (Sanches et al. 2005). In Section 3 we will

adapt a new method using ontology for document

indexing as discussed by R. Nossum and V.

Oleshchuk to find the similarity of a maneuvering

situation to any of the ontology describing the

concepts of maneuvering (Park & Benedictos 2006).

Finally we will be using these ontologies to build a

conceptual model of a maneuvering situation

involving multiple target ships.of

370

2 ONTOLOGY IN MANEUVERING

SITUATIONS

There are several maneuvering situations that can

represent the basic ship maneuvering knowledge of a

bridge officer. The knowledge used in this situations

are somewhat related to each other though each one

is also separated by distinct attributes that can be

considered different from the rest. The following are

the maneuvering situations in navigation involving a

single target ship:

1 Collision Avoidance

2 Altering Course

3 Maintaining Course

4 Overtaking

5 Crossing

6 Non-collision

Though the above maneuvering situations have

distinct attributes from each other some of them may

share a similar concept or instance to be related to

each other. Take for example the first two situations;

Collision Avoidance and Altering Course are related

with each other when we think about avoiding

collision with another ship whose distance is slowly

getting near your own ship. On the other hand they

are a separate maneuvering situation when you are

maintaining a course in order not to be in collision

with another ship. This conditional relationship is also

present among the other maneuvering situations.

In Figure 1 we can see the five basic maneuvering

situations and how they can be related to each other.

In the following sections we will be discussing how

ontology can be used to represent them as context

descriptions together with the algorithm to find the

similarity of a given situation.

Fig. 1. Basic maneuvering situations and their ontological

relations

2.1 Using ontology in defining concepts

In this paper we consider ontologies as knowledge

structures that identify concepts, properties of

concepts and relations among them to enable share

and reuse of knowledge. Ontologies. As shown in

Figure 2 we will use ontology to collect and organize

terms of references presented as graphs that reflect

structural and semantic relationships between

contexts.

Fig. 2. Mapping of Vertices and Edges

2.2 Graphical Representation of ontology

We will assume, that contexts are given in form of

ontology. Ontology O is presented as a directed

graph G = (V, E) where vertices from V are labeled

by elements from T and edges from E are labeled by

elements from R. We denote such ontology as O =

G(T, R). The mappings of V and edges E are

defined by surjective functions τO : V→T and ρO :

E→R respectively, that is, τO (V)=T and ρO (E)=R.

In Fig.2, we can see how the relation between graph

G = (V, E) is mapped by ρO and τO to an ontology

O = G(T, R).

Using the basic maneuvers, enumerated in the

first paragraph of this section, as concepts or terms,

we can let T be the set of maneuvers and R be the set

of predefined semantic relations among the

maneuvers such as instance_of, subset_of,

attribute_of, member-of_group etc.

Using the ontologies shown in Figures 3 to 8 we

can go further to include more transitive and

asymmetric relations that will define a hierarchal

structure between more specific and more general

concepts, where terms inherit all characteristics from

their ancestor terms. We take R to represent a

hyponymy-like relations, and then from (a, b) ∉ R it

follows that b represents a more general concept

than a.

We will define sub-ontology relation ⊆ similar to

the subgraph relation (Nossum et al. 2005).

Let O

= G

, R

) where G

=(T

, R

), i = 1,2 be

two ontologies. O

is a sub-ontology of O

denoted

⊆

if the following properties are satisfied:

– Graph G

is a subgraph of G

– T

⊆ T

and R

⊆ R

– τo

⊆ τo

and ρo

⊆ ρo

371

Fig. 3. Ontologies under the concept collision avoidance

Fig. 4. Ontologies under the concept non-collision avoidance

Fig. 5. Ontologies under the concept altering course

Fig. 6. Ontologies under the concept maintaining course

Fig. 7. Ontologies under the concept overtaking

Fig. 8. Ontologies under the concept crossing

As shown in Figure 9, let us take the ontologies

from the root altering course having a relation,

is_a_concept, as an example. It will be mapped by

the τo and ρo, has_a_subconcept, to collision

avoidance which has a relation is_a_sub-concept.

The sub-concept will have a mapping has_a_subset

to Altering course having a relation is_a-subset. The

sub-set will have a mapping has_a_member to ship

having a relation is_a_member. The member

will

also have a mapping has_an_attribute to the

attributes course, distance, relative bearing, TCPA,

DCPA, and αβ having a common relation

is_an_attribute. These will have a common mapping

has_a_value to their respective parameters having a

relation is_a_value that could describe a maneuver

that calls for an alteration of course.

372

Fig. 9. Ontologies describing the concept altering course

3 DOCUMENT ARTICULATION AND

SOLVING FOR SIMILARITY

We will give a formal definition of semantic

similarity and explain how to calculate similarity

between two maneuvering situation using abstraction

levels and based on context defined in the form of

ontology ( Nossum et al. 2005).

3.1 Document articulation

Parameters used in this articulation will be defined

as the following:

Distance - Distance between the ship in the

vicinity from (OS).

TRB – Target ship's relative bearing will help

determine the type of approach of the dangerous

ships as well as in adjusting the solution to be

adapted by its similarity from the that in the case

base.

TCPA – Time of CPA will be used to determine

the CR of each vessel within the dangerous area. It is

also used to adjust the solution to be adapted by

finding its similarity from that in the case base.

DCPA – Distance at CPA will be used as a

fuzzified input implicated by the rules in the case

base to produce an adjusted output of new heading.

CR – Collision Risk is the result of implicating

the TCPA and TRB rules. I will indicate the degree

of danger that an approaching ship poses to OS.

αβ – The angle of approach of a ship in the

vicinity in relation to OS heading measured from the

direction of OS’s heading for ships forward of OS’s

beam and measured from the direction of OS’s stern

for ships abaft OS’s beam.

We take maneuvering situation t as document

containing the set of values of the attributes

distance, TRB, DCPA, TCPA, CR and αβ as the

input. The input t is to be articulated with respect to

an ontology O = G(T,R), where G = (V,E). O will

represent the ontology representing our maneuvering

situations above.

The articulation of t with respect to O is a sub-

ontology O denoted as O

such that O

⊆ O, let term

(t,O) denote the set of terms from T that occur in t

that is, term(t,O) ⊆ T.

We can define O

as G

, R

), where G

= (V

), and let G

= (V

) be the subgraph of G = (V,

T) spanned by V

In the articulation of a document, we try to find

all terms from T occurring in t by selecting V

⊆ V

such that τ

) = term(t, O).

3.2 Similarity using Abstraction Levels

The articulation of our document t, containing a set

of attribute values, relative to an ontology O that

defines a maneuvering situation is in general a forest

of trees or sub-ontology of O where parent vertices

represent more abstract concepts than their children

and root vertices are the most abstract concepts.

Root vertices have abstraction level 0 and non root

vertices have abstraction level 1 more than its parent.

We will denote abstraction level of a vertex v∉V as

level(v) expressed as:

level : V → {0,1,2,…}

Defining the similarity of a set of input t

to a set

of ontology t

relative to an on ontology O = G(T, R)

where G = (V, E). Let Ot

= Gt

(Tt

, Rt

), i = 1,2

denote articulations of t

and t

with respect to O.

Similarity is measured as a number between 0 and 1

which is a ratio of the number of common terms at

the relevant abstraction level shown in Fig. 10.

Assuming that Gt

= (Vt

, Et

)

and V

is the set of

vertices at abstraction level j in the articulation of t

relative to O. let m

be the highest value of j such

that V

≠

0, i = 1,2 and let m = min(m

, m

), M =

max(m

, m

)

The similarity of t

and t

relative to O is a vector

Sim(t

, t

, O) = (s

…, s

j =

∩V

for 0 ≤ j ≤

j =

0 for m < j ≤ M

373

Fig. 10. Solving similarity using abstraction levels

Similarity will be measured by the total number

of related terms in every abstraction level divided by

the number of vertices.

3.3 Conceptual Model

After solving for the individual similarity of a

maneuvering situation involving a single target ship

in a maneuvering situation, in the preceding sections,

we can further apply ontology to build a conceptual

model (Sanches etal.2005) of a new maneuvering

situation involving multiple target ships in order to

find a similar case from the CBR database where a

solution can be adapted to obtain an optimum output

to avoid collision.

Figure 11 shows how a set of concepts’ relation

to a maneuvering situation can be used to build the

conceptual model of a maneuvering situation by

defining the allowed parameter for alteration of

heading depending to each target ship’s relation to

the concepts of maneuvering situations.

Fig. 11. Constructing a conceptual model of a maneuvering

situation using ontology

Looking at the figure above, The vertices OL,

OLW, OLN, OZ, ORN, ORW, OR are ontologies

having relations mapped to the concepts A, B, C.

They define the allowed alteration in relation to the

respective concepts. The bold lines denote

maneuvers that have no relation to the ontology and

the narrow lines denote the maneuvers that have a

relation to the ontology. Vertices having no relation

to the ontology denote that the alterations are not

allowed.

This conceptual model can be used to find a

similar case in the CBR database that would give the

optimum solution to obtain an output for avoiding

collision. Figure 12 shows the structure of building a

conceptual model of a maneuvering situation using a

set of ontology to be used as a tool in finding a

similar case from the CBR database.

374

Fig. 12. Structure of building a conceptual model.

4 CONCLUSION

We have adapted an algorithm using ontology to

define the basic concepts that can represent an

acquired expert knowledge in maneuvering a ship.

We have also used a set of ontologies to build a

conceptual model that can represent a new

maneuvering situation involving multiple target

ships. The conceptual model can be used as a tool in

improving the algorithm for finding similar cases

from the CBR database.

Future research will focus on finding similar

cases from the CBR database using conceptual

model as a tool. The effect on the efficiency of

obtaining an optimal output from the Fuzzy-CBR

database would be validated by further tests in more

complicated maneuvering environmenst.

REFERENCE

Han-Jin Lee and Key Pyo Rhee, , 2001 Development of

Collision Avoidance System by Using Expert System and

Search Algorithm, Int'l. Ship Building System, Vol.48,

No. 3, pp.197-210.

Nam-Kyun Im and Gei-Kark Park, 2005, Simulation Study on

Auto Navigation System. pp. 572-576, Proceedings of the

6th International Symposium on Advanced Intelligent

Systems.

Yong-Nam Na, Wang-gyu Choi and Sung-juu Lee, 2003, Self

Organizing Fuzzy Controller Using Command Fusion

Method and Genetic Algorithm, International Journal for

Fuzzy Logic and Intelligent Systems.

Gei-Kark Park, John Leslie RM Benedictos, 2006, Ship’s

Collision Avoidance System Using Fuzzy-CBR, Vol.16,

No. 2, pp. 39-44, Proc. of KFIS Autumn Conference, Gumi,

17-18 November.

Ian Watson, 1998, CBR is a methodology not a technology, In,

Research and Development in Expert Systems XV.

Toshiro Iwatani, Shun'ichi Tano and Wataro Okamoto, 1994,

Fuzzy Case Base Reasoning in FLINS (Fuzzy Lingual

Reasoning), LIFE Technical Report, TR-4N020.

Shun'ichi Tano, Toshiro Iwatani, Wataro Okamoto, Atsoushi

Inoue and Ryousuke Fojioka, Fuzzy Natural Language

Communication System - FLINS: Concept and

Conversation Examples, FUZZ-IEEE'95, pp. 1039-1044,

1995.

Ryousuke Fojioka, Shun'ichi Tano, Wataro Okamoto, Atsoushi

Inoue and Toshiro Iwatani, Treatment of fuzziness in

natural language by Fuzzy Lingual Sytem - FLINS, FUZZ-

IEEE'95. pp.1045-1050, 1995.

Agnar Aadmont and Enric Plaza, Case-Based Reasoning:

Foundational Issues, Methodological Variations, and system

approaches,AI Communications, 7(1):39-59, 1994.

R.Nossum and V.Oleschuk, Dynamic Documents Indexing in

Evolving Contexts,Vol=151, Proceedings on CIR’05

Workshop on Context Based Information Retrieval,

<http://sunsite.informatik.rwth-

aachen.de/Publications/CEUR-WS/Vol-151/index.html >.

D.M.Sanches, J.M.Cavero and E. Marcos, On Models and

Ontologies, 1st Workshp on Philosophical Foundations of

Information systems Engineering, PHISE05, 2005

<http://kybele.escet.urjc.es/PHISE05/index.php?page=Prog

ram>