International Journal

on Marine Navigation

and Safety of Sea Transportation

Volume 2

Number 4

December 2008

363

Planned Route Based Negotiation for Collision

Avoidance Between Vessels

Qinyou Hu, Chun Yang, Haishan Chen & Baojia Xiao

Merchant Marine College, Shanghai Maritime University, Shanghai, China

ABSTRACT: Automatic vessel collision-avoidance systems have been studied in the fields of artificial

intelligence and navigation for decades. And to facilitate automatic collision-avoidance decision-making in

two-vessel-encounter situation, several expert and fuzzy expert systems have been developed. However, none

of them can negotiate with each other as seafarers usually do when they intend to make a harmonious and

more economic overall plan of collision avoidance in the COLREGS-COST-HIGH situations where collision

avoidance following the International Regulations for Preventing Collisions at Sea(COLREGS) costs too

much. A negotiation framework was put forward in our previous research to enable vessels to negotiate for

optimizing collision avoidance in the COLREGS-COST-HIGH situations at open sea. In this paper, the

negotiation framework is improved by considering the planned route of both vessels. The simulation results

show that more economic overall plan of collision avoidance may be achieved by the improved framework

when one or both parties deviate from their planed route or are approaching their next way points.

1 GENERAL INTRODUCTION

Automatic vessel collision-avoidance systems have

been studied in the fields of artificial intelligence

and navigation for decades. And to facilitate

automatic collision-avoidance decision-making in

two-vessel-encounter situation, several expert and

fuzzy expert systems (Chengneng, H. 2002, Coenen,

F. et al. 1980, Hanjin, L. et al. 2001, 1993,

Hasegawa, K. et al.1989, Iwasaki, H. et al. 1986,

Koyama, T. et al. 1987, Saburo,T. et al. 1987) have

been developed. However, none of them can

negotiate with each other as seafarers usually do

when they intend to make a harmonious and more

economic overall plan of collision avoidance in the

COLREGS-COST-HIGH situations where collision

avoidance following the International Regulations

for Preventing Collisions at Sea(COLREGS) (Leo,

P. 1979) costs too much. A negotiation framework

was put forward in our previous research (Qinyou,

H. et al. 2006a, b) to enable vessels to negotiate for

optimizing overall collision avoidance plan in the

COLREGS-COST-HIGH situations at open sea.

Planned routes of both vessels, however, were not

considered in our previous work. As a result, better

overall collision-avoidance might not be achieved

when one or both vessels deviate from their planed

route or are approaching their next way points.

In this paper, we have involved the planned route

information in the negotiation framework. That is to

say, when vessels are not proceeding on their

planned route or are approaching the next way

points, they would prefer to return to their planned

route or to navigate on the new course line easily at

the next way points when they take collision-

avoidance action. Therefore, taking the vessel’s

planned route information into consideration when

they are negotiating will enable them to achieve a

better action plan to avoid collision.

This paper is organized as follows: Section 2

briefs our previous work, i.e. the CANFO

364

negotiation framework for collision avoidance

between vessels in the COLREGS-COST-HIGH

situations. Section 3 improves our previous

negotiation framework by considering the planned

route information of the involved vessels. Section 4

illuminates the simulation results of this research.

Finally, main conclusion and future researches are

offered in section 5.

2 CANFO

The previous automatic Collision-Avoidance

Negotiation FramewOrk (CANFO) can be defined

by Equ. (1).

, ,,,,,CANFO A X R U P

=< Π>

(1)

where:

The

denotes the set of the participants involved

in a negotiation, which is usually comprised of a

give-way vessel and a stand-on vessel or two give-

way vessels.

The

stands for the set of negotiation issues. The

negotiation issues are the overall collision-avoidance

plan that the vessels in

will

negotiate on.

The

presents the reserved values of both

parties. The reserved value of a stand-on vessel is

the extent to which the stand-on vessel would like to

compromise, while a give-way vessel’s reserved

value is the action plan generated by its expert

system. To a give-way vessel, the negotiation result

should be more economic than its reserved plan,

while to a stand-on vessel, the negotiation result

should not worse than its reserved value.

The

describes the utility model of each vessel

The

is the set of the preference model of each

vessel in

. In a two vessel encounter situation,

one vessel can be either a give-way vessel or a stand-

on vessel. Different role means different preference

model. The preference model of a give-way vessel

includes four sub-models. 1) the negotiation

intention model which describes the favor degree of

negotiation when a give-way vessel encounters a

collision risk; 2) the collision avoidance action

preference model which describes the preference to

different kinds of collision avoiding action, such as

turnaround, shift or both; 3) the collision risk

tolerance model which describes the adjacent degree

of the target vessel in space and time that the give-

way vessel can tolerate; and 4) the negotiation

strategy model which describes the strategies the

give-way vessel will adopt in a negotiation process.

The preference model of a stand-on vessel also

includes an action preference model and a collision

risk tolerance model, describing the same things as is

in the case of a give-way vessel. Besides that, a

benevolence model, which describes the extent to

which the stand-on vessel may compromise in a

negotiation process, is also included.

The

denotes the set of the reasoning model of

each vessel in

. The reasoning model of a give-

way vessel will determine whether it should start a

negotiation process with another vessel or not based

on its expert plan and its negotiation intention

model. Whether the give-way vessel need the co-

operate action of stand-on vessel or not is also

determined by the reasoning model. After received

the proposals from stand-on vessel, the give-way

vessel’s reasoning model shall calculate the utilities

of each proposals and determine which proposal

should be accepted. At the same time, the reasoning

model should generate the counter offer. The

reasoning model of stand-on vessel shall generate

counter offer based on its preference model, and

determine whether accept the proposals received

from the give-way vessel or not.

The

defines the negotiation protocol, which

controls the negotiation process.

For more information about the negotiation

framework, please consults our previous work

(Qinyou, H. et al. 2006a, b).

3 IMPROVING CANFO BY CONSIDERING

VESSELS’ PLANNED ROUTES

When vessels are not proceeding on their planned

route or are approaching the next way points, they

would prefer the collision action which can enable

them to return to their planned route as soon as

possible or to navigate on the new course line

economically at the next way point while they take

collision avoidance action. Therefore, in these

situations, the preferred course and speed of the

vessels are not their planned course and speed which

are assumed to be the preferred course and speed of

negotiation participants in our previous work.

For simplicity, in this paper, we assume that

vessels only alter their courses when they avoid a

collision. Therefore, the calculation of the preferred

course (denoted by c

pre

) of vessels which are

deviating from the planned route or approaching the

next way point is the base work to improve the

CANFO framework (see section 3.1).

The new preferred course will influence the

definitions of the negotiation intention space of give-

way vessel, utility model of the negotiation

participants and the reasoning model of a negotiation

365

responder. The new definitions will be described in

section 3.2, 3.3 and 3.4 respectively.

3.1 Calculation of

pre

3.1.1 Vessel only deviating from its planned route

Fig. 1. Diagram for calculating the preferable course of a vessel

when it deviates from their planned routes, where D is the

distance that the vessel departs from its planned route; S is the

distance from the vessel’s present position O to its next

waypoint or next planned position;

is the planned course.

Figure 1 shows a situation where a vessel deviates

from its planned route. The

pre

of the vessel can be

calculated by Equ. (2).

arcsin( )

pre p

= ±

(2)

In (2), when the vessel is on the right side of its

planned route, the operator shall be “+”, otherwise it

shall be “-“.

3.1.2 Vessel approaching its next way point

Figure 2 illuminates the situation that a vessel is

approaching a way point.

Fig. 2. Diagram for calculating the preferable course of a vessel

when it deviates from their planned routes, where AD is the

plan route; D is the waypoint; C is the vessel’s present position

The

pre

in Figure 2 can be calculated by

algorithm (1).

2 22

(1 )

pre p

Algorithm (1)

suppose s AD l CD

let h tg k

h hk k hk

then c c arctg

= =

− +−

= ±

−

3.1.3 Vessel not only deviate from its planned route

but also is approaching its next way point.

Fig. 3. Diagram for calculating the preferable course of a vessel

when it deviates from their planned routes and is approaching

the next way point, where d is the shortest distance from the

vessel’s present position to it’s planned route

Figure 3 shows a situation that a vessel not only

deviates from its planned route but also is

approaching the next way point. While in such

situations, then

pre

of the vessel can also be

calculated by algorithm (1) with two small

modifications shown in Equ. (3) and Equ. (4).

s s dctg

= +

(3)

l l dctg

= +

. (4)

3.2 Modifying the negotiation intention space of

a give-way vessel

Two negotiation intention spaces are defined in a

negotiation–intention model of a give-way vessel b,

namely B and M.

ccv

−+−

=<∆ ∆ ∆ >

and

,,,

ccvv

+−+−

=<ΘΘΘΘ>

. If

the action plan generated by the collision-avoidance

expert system of b alone, denoted by

does not

belong to the space B defined ( denoted by

Ω

), The

b will intend to make a negotiation with its

opponent; Furthermore, If

does not belong to the

space M defined ( denoted by

Ω

), The b will try to

persuade the stand-on vessel to take a collaboration

action. And if

belongs to

Ω

while not belongs

Ω

, The b will try to persuade the stand-on vessel

to permit b to break the COLREGS.

Given

(Qinyou, H. et al. 2006a, b), the gross

tonnages of b and a stand-on vessel p, denoted

and

respectively, in the improved CANFO

366

framework, B describes a new negotiation intention

space:

( ,),( (), ())

pre c pre c

bB b b b c b v

cvc v

ϕϕ

+−

Ω =< ⊕∆ +∆ >

And its cost equivalent:

( ,),( (), ())

pre c pre c

bB b b b c b v

cvc v

ϕϕ

+−

Ω =< ⊕∆ +∆ >

where

and

are the current course and velocity

of b respectively, and

⊕

is a course plus operator

(Qinyou, H. et al. 2006a). M also describes a new

negotiation intention space:

( (), ()),( (), ())

bb bb

pp pp

pre c pre c

bM b c bv b c bv

bb bb

gg gg

cvcv

gg gg

ϕϕ ϕϕ

−+ +−

Ω < ⊕Θ +Θ ⊕Θ +Θ >

And its cost equivalent:

( (), ()),( (), ())

bb bb

pp pp

pre c pre c

bM b c bv b c bv

bb bb

gg gg

cvcv

gg gg

ϕϕ ϕϕ

−+ +−

Ω < ⊕Θ +Θ ⊕Θ +Θ >

3.3 Reforming the utility model

In our previous work, we suppose that the utility of a

plan is determined by its safety utility and economic

utility, and the economic utility is determined by the

cost of the plan. Given the plan’s cost space

Ω

, its

collision avoidance plan

( , ),( , ),

cc oo

s ss ss s

I cv cv d=<>

, in the

improved CANFO framework, the cost of

should

be calculated by Equ. (5).

() () ()

s nn

Is Is Is

DDDΩ= Ω+ Ω

(5)

where,

( , ),( , ),

pre pc o o

n s s ss s

I c v cv d=<>

, The

and

are the current speed, the objective course and

the objective speed of the vessel s respectively,

()

D Ω

return the cost of shift while

()

D Ω

return

the cost of turnaround.

3.4 Improving the reasoning model of a responder

Given the current course of stand-on vessel

current speed

, preference course

pre

, planned

speed

, gross tonnage

, the course collaboration

coefficient to a give-way vessel

, the speed

collaboration coefficient to give-way vessel

and

the benevolence control coefficient

, for each

request from give-way vessel, namely

( , ),( , ), ,?

cc oo

bb bb b

cv cv d<< > >

, the proposal

space of the stand-on vessel p, namely

Ω

, can be

calculated by Equ. (6).

( ( ( ) ( ( ))), ( ) ( )),

( ( ( ) ( ( ))), ( ) ( ))

c o c p oc

p c b b pv bb

pre o c p o c

p c b b pv bb

c c c v vv

λλ

⊕− ⊕− − −

⊕− ⊕− − − >

Ω=<

where

()

cc⊕−

denotes the variation of the give-

way vessel’s course while

()

vv−

stands for the

variation of its speed.

4 COMPUTER SIMULATION

Suppose the negotiation rate between the give-way

vessel b and the stand-on vessel p is 10 rounds/min.

let b’s gross tonnage (

) be 15,000T, and its

preference model be

,,,

b bbbb

I S AR

P PPPP<>

, where

0.3,1,1=<>

2,10=<>

and

1,1, 1,1,1,1,1,1,1,1 ,

P =<< >

1/ 90,1/ 110,1/ 130,1/ 150,1 / 180,1 / 180,1/ 180,1 / 180< >>

, Let p’s

gross tonnage

(

) be 10,000T, and its preference

model be

p ppp

P PPP<>

, where

1,1, ,=<

1/90,1/110,1/130< ,

1/150,1/180,1/180,1/180,

1/180 >>

and

2,8=<>

In crossing and overtaking situations, let

P =<<

30,30,0>,<60,60,2,2>,1,2 >

and

<0.5,2,<10,0>,<0.5,0>,0.5,1>

In head-on situations, let

P =<<

0,10,0>,<30,30,2,0>,1,2>

and

<0.5,2,<0,0>,<1,1>,0.5,1>=

From Figure 4 to Figure 6 are the simulations of

the collision avoidance negotiation in different

COLREG-COST-HIGH encounter situations. In

each figure, graph (a) shows the initial situation,

graph (b) displays the negotiation results without

considering the planned route information, and graph

the planned route information.

The green vessel model represents a negotiation

initiator vessel while red one represents a negotiation

responder. Lines ending with number represent

routes and the numbers are their courses. Lines

ending with “RMV” represent relative motion

vectors from the stand-on vessel p to the give-way

vessel b.

The simulation results from these three typical

situations and other more situations not presented in

this paper proved the improved CANFO framework

could enable the two vessels in an encounter

situation to achieve a more economic overall

collision-avoidance plan than our previous CANFO

framework, if one or both of them deviates from

their planned route or are approaching their next way

point.

(6)

367

5 CONCLUSIONS AND FUTURE WORK

Negotiation is a very important method to optimize

and coordinate the vessel collision avoidance actions

taken to avoid collision. Enabling the vessel

collision-avoidance (fuzzy) expert systems to

negotiate with each other will greatly improve their

usability. Based on our previous research, this paper

took the vessel’s planned route information into

account and made out the influences it might bring

to the negotiation framework for vessel collision

avoidance. The results of the computer simulations

proved that the improved CANFO framework could

enable the two vessels in an encounter situation to

achieve a more economic overall collision-avoidance

plan than our previous CANFO framework, if one or

both of them deviates from their planned route or are

approaching the next way point.

(a) Initial situation, where:

DCPA=0. 09 n miles

TCPA=11.11 minutes

Expert plan of b:<0°,032,starboard>

(b) Negotiation results

b:<0°,032°,starboard>

p:<180°,180°, null >

DCPA: 2.01 n miles

b:<0°,344°,port>

p:<180°,161°, port >

DCPA: 2.02 n miles

Fig. 4. A simulation of a head-on situation, where both vessels are approaching their next way points

(a) Initial situation, where:

DCPA=0. 00 n miles

TCPA=18 minutes

Expert plan of b:<0°,060°,starboard>

(b) Negotiation result:

b:<0°,060°,starboard>

p:<270°,270°, null >

DCPA: 2.0 n miles

b:<0°,339°,port>

p:<270°,247°, port >

DCPA: 2.05 n miles

Fig. 5. A simulation of a crossing situation, where both vessels deviate from their planned routes and are approaching their next way

point

368

(a) Initial situation, where:

DCPA=0. 49 n miles

TCPA=36 minutes

Expert plan of b:<0°,012°,starboard>

(b) Negotiation results:

b:<000°,012°,starboard>

p:<000°,000°, null >

DCPA: 2.08 n miles

b:<000°,350°,port>

p:<000°,027°, port >

DCPA: 2.00 n miles

Fig. 6. Simulation of an overtaking situation, where both vessels deviate from their planned routes and are approaching their next

way point

The CANFO, however, is still on its starting

stage. The preferred speed is also need to be

considered in a negotiation when one or both vessels

are not proceeding at their planned speed. And how

to enable CANFO work in multi-vessel-encounter

situations and in restricted waters also needs further

research.

ACKNOWLEDGEMENTS

This work was supported by Education Ministry of

China under Grant No.20050254001, Shanghai

Leading Academic Discipline under Grant No.T0603

and HuoYingdong educational fund under Grant

No.0254-05-FN580001.

REFERENCES

Chengneng, H., 2002, The Integrated Design of Fuzzy

Collision-Avoidance and

∞

-Autopilots on Ships, Journal of

Navigation, Vo. 55, No. 1, pp. 117-136.

Coenen, F. & Sneaton, G. & Bole, A., 1980, Knowledge-based

collision avoidance. Journal of Navigation, Vo. 42, No. 1,

pp. 107-116.

Hanjin, L. & Key, R., 2001, Development of Collision

Avoidance System by Using Expert System and Search

Algorighm”, Int. Vesselbuild. Progr., pp. 197-212.

HanJin, L.etc.,1993, Development of collision avoidance

system by fuzzy theory, The Second Japan-Korea Joint

Workshop on Vessel & Marine Hydrodynamics, Osaka, pp.

164-169.

Hasegawa, K. & Kouzuki, A. & Muramatsu, T. & Komine, H.

& Watabe, Y.,1989, Vessel auto-navigation fuzzy expert

system (SAFES), Journal of the Society of Naval

Architecture of Japan, Vo.166, 1989.

Iwasaki, H. & Hara, K., 1986, A fuzzy reasoning model to

decide the collision avoidance action. The Journal of Japan

Institute of Navigation, Vo. 75, pp. 69-70.

Koyama, T. & Yan, J., 1987,An expert system aproach to

collision avoidance, Proceeding of the 8th Vessel Control

System Symposium, Hague.

Leo P., 1979, The International Regulations for Preventing

Collision at Sea in 1972, Hi Wug.

Qinyou, H. & Chaojian, S., etc., 2006a, Enabling Vessel

Collision-Avoidance Expert Systems to Negotiate, The

proceeding of IAIN/GNSS, Jeju, Korea, pp. 77-82.

Qinyou, H.& Qiaoer H.& Chaojian S., 2006b, A Negotiation

Framework for Automatic Collision Avoidance between

Vessels, The proceeding of IEEE/WIC/ACM International

Conference on Intelligent Agent Technology, Hongkong,

China, pp. 595-601.

Saburo, T. & Hisashi M., 1987, Basic research on an expert

system for navigation at sea. The Journal of Japan Institute

of Navigation,Vo. 77, pp. 133-139.