1

Recent Advances in Multi-Objective Search

Ariel Felner

ISE Department

Ben-Gurion University

ISRAEL

felner@bgu.ac.il

Ariel Felner

Ben-Gurion Univ.

Israel

Oren Slazman

Technion

Israel

Carlos Hernández 

Universidad San Sebastian

Chile

Sven Koenig

USC

USA

Han Zhang

USC

USA

• Introduction: Ariel
• Specific Algorithms: Ariel
• Approximations: Han
• Heuristics: Han
• Summary and challenges: Sven

​

​

​

​

2

Overview

1�Introduction�

3

Unidirectional search

Different costs functions:

f(n)=g(n) Breadth-First Search. AKA Dijkstra’s algorithm.

f(n)=g(n)+h(n) The A* algorithm (1968).

​

​

4

g(n)

h(n)

start

goal

n

Breadth

First

Search

A*

Adding heuristics to unidirectional search is very beneficial

Unidirectional search

f(n)=g(n)+h(n) The A* algorithm (1968).

​

Must-expand States: States with f(n)<C*

Maybe expand States: States with f(n)=C*

Never-expand States: States with f(n)>C*

​

​

​

5

start

Goal

C*

Start

Goal

S

G

S

G

(1,7)

1h

7k $

S

G

A

(2,1)

(1,1)

(1,7)

3h

1h

2k $

7k $

S

G

A

B

(2,1)

(1,1)

(1,7)

(1,2)

(1,3)

2h

3h

1h

5k $

2k $

7k $

S

G

A

B

C

(2,1)

(1,1)

(1,7)

(1,2)

(1,3)

(3,1)

(2,3)

5h

2h

3h

1h

4k $

5k $

2k $

7k $

S

G

A

B

C

(2,1)

(1,1)

(1,7)

(1,2)

(1,3)

(3,1)

(2,3)

5h

2h

3h

1h

4k $

5k $

2k $

7k $

S

G

A

B

C

(2,1)

(1,1)

(1,7)

(1,2)

(1,3)

(3,1)

(2,3)

?

7k $

5h

S

G

A

B

C

(2,1)

(1,1)

(1,7)

(1,2)

(1,3)

(3,1)

(2,3)

5h

2h

3h

1h

4k $

5k $

2k $

7k $

S

A

B

C

G

S

G

A

B

C

(2,1)

(1,1)

(1,7)

(1,2)

(1,3)

(3,1)

(2,3)

S

G

A

B

C

(2,1)

(1,1)

(1,7)

(1,2)

(1,3)

(3,1)

(2,3)

(1,7)

(5,4)

(3,2)

Duration (h)

(2,5)

Cost (x10³)

S

G

A

B

C

(2,1)

(1,1)

(1,7)

(1,2)

(1,3)

(3,1)

(2,3)

(1,7)

(5,4)

(3,2)

Duration (h)

(2,5)

Cost (x10³)

S

G

A

B

C

(2,1)

(1,1)

(1,7)

(1,2)

(1,3)

(3,1)

(2,3)

(1,7)

Duration (h)

(2,5)

Cost (x10³)

(3,2)

(5,4)

Pareto-Optimal Frontier (POF)

S

G

A

B

C

(2,1)

(1,1)

(1,7)

(1,2)

(1,3)

(3,1)

(2,3)

Duration (h)

Cost (x10³)

(3,2)

(2,5)

(1,7)

Multi-Objective Search

S

G

A

B

C

(2,1)

(1,1)

(1,7)

(1,2)

(1,3)

(3,1)

(2,3)

Multi-Objective Search

S

G

A

B

C

(2,1)

(1,1)

(1,7)

(1,2)

(1,3)

(3,1)

(2,3)

(2,3) and (4,1)

Are mutually undominated

Must Expand Nodes

1

2

3

4

5

…

Must Expand Nodes

B

Must-Expand Nodes

B

B

Must Expand Nodes

A

D

C

C

C

C

C

D

B

B

B

B

A

B

A*

1 OPEN.insert(n_root);

2 while OPEN ≠ ∅ do {

3 n ← OPEN.pop() // according to minimal f-value

4 if duplicate-detection(n)

then continue

5 if (s(n) = goal) then

6 return(f(n))

7 for each s′ neighbour of s(n) do{

8 n′ ←new node at s′ with h(n′) = h(s′),

g(n′) = g(n) + c((s, s′))

9 if duplicate-detection(n′)

then continue // line 7

10 f(n′) = g(n′) + h((n′))

11 OPEN.insert(n′)

}

}

12 return POF

31

A*

1 OPEN.insert(n_root);

2 while OPEN ≠ ∅ do {

3 n ← OPEN.pop() // according to minimal f-value

4 if duplicate-detection(n)

then continue

5 if (s(n) = goal) then

6 return(f(n))

7 for each s′ neighbour of s(n) do{

8 n′ ←new node at s′ with h(n′) = h(s′),

g(n′) = g(n) + c((s, s′))

9 if duplicate-detection(n′)

then continue // line 7

10 f(n′) = g(n′) + h((n′))

11 OPEN.insert(n′)

}

}

12 return POF

32

General Algorithm: MOS-A*

1 OPEN.insert(n_root); POF ← ∅

2 while OPEN ≠ ∅ do {

3 n ← OPEN.pop() // according to un-domination

4 if domination-check-exp(n)

then continue

5 if (s(n) = goal) then

6 add n to POF and continue // line 2

7 for each s′ neighbour of s(n) do{

8 n′ ←new node at s′ with h(n′) = h(s′),

g(n′) = g(n) + c((s, s′))

9 if domination-check-gen(n′)

then continue // line 7

10 f(n′) = g(n′) + h((n′))

11 OPEN.insert(n′)

}

}

12 return POF

33

General Algorithm: MOS-A*

1 OPEN.insert(n_root); POF ← ∅

2 while OPEN ≠ ∅ do {

3 n ← OPEN.pop() // according to un-domination

4 if domination-check-exp(n)

then continue

5 if (s(n) = goal) then

6 add n to POF and continue // line 2

7 for each s′ neighbour of s(n) do{

8 n′ ←new node at s′ with h(n′) = h(s′),

g(n′) = g(n) + c((s, s′))

9 if domination-check-gen(n′)

then continue // line 7

10 f(n′) = g(n′) + h((n′))

11 OPEN.insert(n′)

}

}

12 return POF

34

Pop from open

Only pop undominated nodes

35

(1,7)

(2,5)

(3,2)

(5,4)

(3,6)

Domination checks

• Path dominance check:
• Only store nodes n(s) with undominated g(s)

​

​

​

36

start

S

5,6

3,7

4,5

S

S

5,6

3,7

OPEN

4,5

Domination checks

• Path dominance check:
• Only store nodes n(s) with undominated g(s)

​

​

​

37

start

S

5,6

3,7

4,5

S

S

5,6

3,7

OPEN

4,5

Path dominance check is optional

S

Domination checks

38

start

S1

f=(5,6)

• Solution dominance check:
• Prune nodes that are dominated by a solution in POF

​

POF= (7,7), (3,8)

Domination checks

39

start

S1

f=(5,6)

• Solution dominance check:
• Prune nodes that are dominated by a solution in POF

​

POF= (5,6), (3,8)

S2

f=(4,9)

Solution dominance check is mandatory

Like expanding nodes with f>C*

General Algorithm: MOS-A*

1 OPEN.insert(n_root); POF ← ∅

2 while OPEN ≠ ∅ do {

3 n ← OPEN.pop() // according to un-domination

4 if domination-check-exp(n)

then continue

5 if (s(n) = goal) then

6 add n to POF and continue // line 2

7 for each s′ neighbour of s(n) do{

8 n′ ←new node at s′ with h(n′) = h(s′),

g(n′) = g(n) + c((s, s′))

9 if domination-check-gen(n′)

then continue // line 7

10 OPEN.insert(n′)

}

}

11 return POF

40

Many variants exist

Pop from open

• Only pop undominated nodes
• How do we choose among them

​

41

(1,7)

(2,5)

(3,2)

(5,4)

(3,6)

• Only pop undominated nodes
• How do we choose among them

​

Other ordering functions exist: Max, Min, Ave and more

NAMOA*�Mandow and P´erez-de-la-Cruz 2010

• Only pop undominated nodes
• Choose the node that is lexicographically smallest
• Perform dominance checks upon generation of a node.

​

42

NAMOA_dr*

Pulido, Mandow, and P´erez-de-la-Cruz 2015

​

The idea of dimensionality reduction.

BOA*

• With Lex: g1-values monotonically grow → for a path not to be dominated, it has to have smaller g2-value
• g1 values go up so g2 values must go down to be undominated

​

​

​

43

start

S

1,10

2,8

3,9

g₂min(n)=10

• BOA* Dominance check in a constant time
• For each state n we keep g₂min(n)
• New states must have larger g₁ values.
• We prune if g₂(n)> g₂min(n)

3,5

g₂min(n)=8

g₂min(n)=5

BOBA*

• Bidirectional BOA*
• Runs two searchers and tires to pass information between the two frontiers.

​

​

44

EMOA* and LTMOA*

• Generalizes BOA* to multi-objective search
• Parallel dominance checks (under review)

​

​

​

Heuristics

​

• In A* a heuristic h(n) estimates the shortest distance from n to the goal.
• h(n) is admissible if h(n) ≤ d(n,goal)
• Then in A* we have f(n)=g(n)+h(n)

​

​

• In MOS we have:
• Single-value Heuristic – point heuristic
• Multi-value Heuristic - Vector of heuristics

​

​

45

Single Valued Heuristic

​

​

​

46

4,6

8,3

0,0

3

4

h=4

h=3

f(n)=g(n)+h(n)=(g1,g2)+(4,3)

4,3

h(n)=(4,3)

Multiple Valued Heuristic

​

​

​

47

1,1

2

6

6,2

8,3

4,6

h=6

h=2

h(n)=(6,2)

Multiple Valued Heuristic

​

​

​

48

1,1

5

3

8,3

3,5

4,6

h=5

h(n)=(3,5)

h=3

Multiple Valued Heuristic

​

​

​

49

8,3

4,6

f(n)=g(n)+h(n)=(g1,g2)+(6,2)

h(n)=(6,2)

f(n)=g(n)+h(n)=(g1,g2)+(3,5)

h(n)=(3,5)

1,1

3

3,5

h=5

h=3

2

6

6,2

h=6

h=2

We need a list of vectors that together underesitmates the entire POF

50

​

Thank you!

​

Questions?

​