MORRF*: Sampling-Based Multi-Objective Motion Planning

1 Introduction

Many tasks assigned to robots are complex, can be performed in several different ways, and must maximize several different performance objectives. For example, a robot in a search task may be expected to maximize the area that it covers while minimizing energy consumption and avoiding risk (see, for example [Mei et al., 2005; Yi and Goodrich, 2014]). As another example, a robot manipulator may need to satisfy performance criteria related to movement, joint velocities, joint accelerations, etc. [Pires et al., 2004].

A common method for finding a solution to a multiobjective optimization problem is to optimize a single objective created by a weighted sum of the multiple objectives. In path-planning the properties of the path produced by this method depend strongly on how each objective is weighted. This means that a programmer, designer, or human teammate must decide how to assign the weights so that the qualitative behavior matches what is intended. In addition to the burden

Kevin D. Seppi

Computer Science Dept. Brigham Young University Provo, UT 84602, USA kseppi@cs.byu.edu

this places on the human operator, optimizing a weighted sum does not work when the multiple objectives are very difficult to compare or are expressed in incommensurate units.

In response to these challenges, it is useful to find the set of Pareto optimal solutions to the multi-objective path-planning problem, meaning the set of solutions for which there is no other solution that produces better payoffs for every objective. If an algorithm could produce the set of Pareto optimal solutions then a human could interactively explore this set to find one or more solutions that matches his or her expectations. The objective of this paper is to create an algorithm that efficiently finds the Pareto set in a multi-objective path-planning problem.

Most popular methods in multi-objective optimization do not naturally apply to path-planning problems [Zhang and Li, 2007; Deb and Jain, 2014]. The main reason for this is that path-planning often represents the problem to be solved as a semi-structured tree with an exponential number of possible trajectories through the tree, and the number of evaluations of the objective function required by existing algorithms do not scale well when there are an exponential number of solutions. One approach to addressing this issue is to change the representation for a path by, for example, coding a path as a sequence of fixed-length line segments represented by direction [Ahmed and Deb, 2013; Howlett et al., 2006] or waypoints [Sujit and Beard, 2009; Pires et al., 2004] so that an evolutionary algorithm can be applied. This produces an encoding that can be "fed into" an appropriate evolutionary algorithm to search for the Pareto set. Unfortunately, these approaches do not scale well for large problems, because the number of segments required to represent the paths grows too quickly and estimating the required number of segments a priori is very challenging. Another approach is to represent the path as a point in a very high-dimensional vector space. In this approach a path is represented as a point in a n ∗ d dimensional space formed by n d-dimensional way-points. If the number of way-points can be held constant, we can use standard approaches to explore the space. However the search can be more difficult if we allow the number of way-points, and therefor the dimensionality of the optimization problem, to vary. Indeed, we will use this to guide our solution, but the algorithm we present works when the obstacles in the path-planning space introduce discontinuities in these high-dimensional spaces, which limits the applicability of heuristic-based search approaches [Sujit and Beard, 2009; Zhang and Li, 2007].

The RRT (Rapidly exploring Random Tree) algorithm is popular for finding feasible solutions from a start position to a goal position in continuous or very large search spaces; it also works well when environments have complex obstacles. The reason that RRT is popular is that the tree structure tends to find solutions very efficiently. The RRT∗ algorithm was a recently introduced modification to RRT that is guaranteed to find an optimal path given enough sampling time [Karaman and Frazzoli, 2011; 2010].

The remainder of the paper presents the MORRF∗ (MultiObjective Rapidly exploring Random Forest*) algorithm, which we used to find a set of Pareto optimal paths. MORRF∗ blends concepts from RRT∗ a decomposition-based approach to multi-objective optimization [Zhang and Li, 2007].

2 RelatedWork

Prior work has modeled the search space as a graph and applied a multi-objective A* search to find the solution [Mandow et al., 2005]. The limitation of this approach is that it requires an a priori discretization rather than a discretization that is guided by the objectives as is done in RRT∗ ; a coarse discretization throws away potentially valuable information and a fine discretization increases complexity and adds redundancy in the resulting graph structures. Obstacles can make it more difficult to determining which cells in the discretized space are connected to which others, especially when searching a space of more than 2 dimensions such as in planning the trajectory for a robotic manipulator. Another approach that uses an a priori discretization (and suffers from these limitations) is to encode a path as a sequence of directions from one cell to next cell and then using the NSGA-II algorithm to find a set of Pareto optimal solutions [Ahmed and Deb, 2013]. Constrained splines have been introduced to interpolate a sequence of way points into a trajectory that avoids obstacles [Ahmed and Deb, 2011], but the effect of the interpolation on the quality of the solution has not been evaluated. In addition to the sorting approach used in NSGA-II, evolutionary algorithms based on the decomposition method have also been proposed [Deb and Jain, 2014].

Evolutionary algorithms can be used to fine the Pareto set, but these approaches tend to be inefficient when applied to spaces with high dimensions [Marler and Arora, 2004]. For such spaces, small deviations in possible solutions may need to be considered in order to find an optimal solution, but this means exploring many possible solutions for problems with non-linearities or multiple local maxima. A path in a fixedlength search tree of depth d can be considered as a point in ℜd , so tree-based approaches followed by an evolutionary "fine-tuning" stage risk running into the problems just listed with evolutionary approaches.

In contrast to searching through and comparing solutions in order to find the Pareto optimal set, decomposition-based methods provide an attractive alternative. In this paper we use a decomposition-based method similar to MOEA-D [Zhang and Li, 2007]. MOEA-D is an algorithm that decomposes a multi-objective optimization problem into a set of subproblems. Each subproblem uses a weighed combination of the objectives to find specific points in the Pareto set or to guide the search for such points. Let λ = [λ1, · · · , λK]T be a weighting vector such that ∑Kk=1 λk = 1. Let {c1(·), c2(·), . . . cK(·)} denote the K-element set of objective functions, let c(x) = [c1(x), c2(x), . . . , cK(x)]T , and let x denote a potential solution. Finally, let zutop = [z∗ 1 , · · · , z∗K ]T denote the socalled Utopia reference vector. Three types of decomposition methods have been used in prior work [Zhang and Li, 2007]; however we will use only the two methods described below, leaving the third (the boundary intersection method) to future work.

The solutions generated by each method are a subset of the Pareto optimal set.

Sampling-based path planning works effectively in continuous space. The RRT (Rapidly exploring Random Tree) has been one of the most popular tools, which efficiently explores the space by randomly sampling the search space; this algorithm tends to work well in the presence of complex obstacles. Unfortunately, RRT has been shown to fail in optimality guarantee [Karaman and Frazzoli, 2010]. In response, the RRT∗ algorithm was proposed, which uses a Rewire process to gradually update the tree structure when new samples of the space indicate that this is needed. Thus RRT∗ is asymptotically optimal [Karaman and Frazzoli, 2010; 2011].

3 Multi-Objective Rapidly exploring Random Forest∗

In this section, we present an algorithm that explores the solution space using RRT∗ -based tree structures but uses multiple trees in the spirit of decomposition-based multi-objective optimization. Because a set of trees are constructed in the exploration process, we call the algorithmMORRF∗ (MultiObjective Rapidly exploring Random Forest∗ ).

Consider a multi-objective path planning problem defined on a bounded, connected open set X ⊂ Rd of possible solutions, and K different objectives {c1(·), c2(·), ...cK(·)}. Without loss of generality, assume that the objective is to minimize these functions. Since the Pareto optimal set is not enumerable, the goal is to find a representative, finite (M-element) subset of the Pareto optimal set.

Definition 1. Multi-Objective Path Planning Consider a bounded, connected open set X ⊂ Rd , an obstacle space Xobs, an initial state xinit, and a goal region Xgoal. Consider the set of K objectives determined by a vector function c(·) = [c1(·), . . . , cK(·)]T defined by c : X → RK . Denote the obstacle-free space by Xfree = X \ Xobs. Note that c is defined for all points in X both those in free space and obstacle space.

Define a path in X as a continuous curve parameterized by s, denoted by σ : [0, s] →X. Define the cost of the path as the vector-valued function c(σ) = ∫σ c(x)ds. The goal is to find M Pareto optimal paths σ∗ ∈ Σ∗ that (a) ∀τ ∈ [0, s], σ∗ (τ) ∈ Xfree; (b) σ∗ (0) = xinit and σ∗ (s) =Xgoal; (c) There does not exist σ that ∀k ∈ K, ck(σ) ≤ ck(σ∗ ) and ∃k′ ∈ K, ck′ (σ) < ck′ (σ∗ ).

Adopting the idea from the MOEA-D algorithm [Zhang and Li, 2007], the M elements in the solution set Σ∗ will be obtained by decomposing the multi-objective problem into M subproblems. In this paper, we use the Tchebycheff approach from MOEA-D. The Tchebycheff approach requires us to define a Utopia reference vector zutop in the fitness space. As illustrated in Figure 1, the Utopia reference vector is defined as that point in cost space that would be obtained if it were possible to find a solution that produced the minimum value for all objectives, that is the kth element of zutop is given by zutop k = argminx∈X ck(x).

We will need one type of RRT∗ structure to explore in an attempt to find the Utopia reference vector in payoff space and another type of RRT∗ structure to find paths that minimize the Tchebycheff condition. Thus, there are two types of tree structures used for the optimization process.

• Each reference tree explores using a single objective ck(x), k ∈ K. The cost of each vertex is calculated using the kth objective function.
• Each subproblem tree explores a subproblem gm(x | λm, zutop ), m ∈ M. The cost associated with each vertex is calculated using gm(x) defined by the corresponding approach.

The K reference trees and M subproblem trees constitute the exploration forest.

The main flow of the MORRF∗ algorithm is given in Algorithm 1. Each reference and subproblem tree are a collection of edges and vertices, Gr = (Vr,Er) and Gs = (Vs,Es), respectively, and the collection of reference trees and subproblem trees are denoted by Gr = {Gr : r ∈ {1, . . . ,K}} and Gs = {Gs : s ∈ {q, . . . ,M}.

Note that each tree, reference and subproblem, uses the same set of vertices, meaning they all share the same points in configuration space. The differences between the trees is the edge set; each reference tree and each subproblem tree has a different way of connecting the vertices.

In each iteration, xrand is generated by randomly sampling from the configuration space. The set of vertices is then searched to find that vertex whose position is nearest to the random point; since all trees share the same set of vertices, any tree G ∈ Gr ∪ Gs may be used to find the nearest point. The location of this vertex is labeled xnearest. The process of finding xnew is represented in the top layer of Figure 2.

The exploration at each iteration is given in Algorithm 1. Like RRT∗ , when the algorithm stops, each reference tree and subproblem tree returns a path, and the set of all these paths forms the solution set.

Algorithm 1 Multi-Objective Rapidly exploring Random Forest∗

1: for each Vr ∈ Vr do 2: Vr ← {xinit}; Er ← ∅; i ← 0 3: for each Vs ∈ Vs do 4: Vs ← {xinit}; Es ← ∅; i ← 0 5: while i < N do 6: xrand ← SAMPLE (i) ; i ← i +1 7: G is arbitrary graph fromGr ∪Gs. 8: xnearest ←NEAREST(G, xrand) 9: xnew ← STEER(xnearest, xrand, η) 10: if OBSTACLEFREE(xnearest, xnew) then 11: for each Gr ∈ Gr do 12: Gr ← EXTENDRef (Gr, xnew, xnearest , r) 13: for each Gs ∈ Gs do 14: Gs ← EXTENDSub (Gs, xnew, xnearest , s)

We now define several functions, using appropriately modified definitions from [Karaman and Frazzoli, 2010].

• SAMPLE(): Returns independent uniformly distributed samples fromXfree.
• NEAREST(): Returns a position of the vertex whose position is closest to point x. NEAREST(G = (V, E), x) = arg minv∈V ‖x - v‖.
• STEER(): Given two points x and y, returns a point z on the line segment from x to y that that is no greater than η from y. STEER( x, y, η ) = argminz∈Rd ,‖z-x‖≤η‖z-y‖.
• OBSTACLEFREE(x, x′ ): Returns True if [x, x′ ] ⊂ Xfree , which is the line segment between x and x′ lies in Xfree.

As illustrated in Figure 2, second layer, edges to the reference trees are added before the edges to the subproblem trees. This allows us to compute the Utopia reference vector using the path costs for each reference tree, each reference tree returning a path that approximates the minimum cost for one objective. The Utopia reference vector is then used to determine which edges should be added for each subproblem.

Consider the second layer in Figure 2, which shows the exploration process for the reference trees. When a new position is obtained (red dot in Figure 2), all reference trees add a vertex that corresponds to this new location. Each reference tree then connects this new vertex to existing nodes by "rewiring" a set of neighboring vertices within a specified radius (red dash circle in Figure 2). The process of rewiring consists of adding edges between existing vertices and the new vertex. This is done using the EXTEND method, given in Algorithm 2.

Algorithm 2 EXTENDRef (G, xnew, xnearest , k)

1: if xnew = xnearest then return G = (V,E) 2: V ′ ← V ∪ {xnew} 3: xmin ← xnearest 4: Xnear ← NEAR(G, xnew, |V |) 5: for each xnear ∈ Xnear do 6: if OBSTACLEFREE(xnew, xnear) then 7: c′k ← COSTk(xnear) +ck( LINE(xnear, xnew) ) 8: if c′k < COSTk(xnew) then 9: xmin ← xnear 10: E′ ←E′ ∪ {(xmin, xnew)} 11: for each xnear ∈ Xnear \ {xmin} do 12: if OBSTACLEFREE(xnew, xnear) then 13: c′k ← COSTk(xnew) +ck( LINE(xnew, xnear) ) 14: if c′k < COSTk(xnear) then 15: xparent ← PARENT(xnear) 16: E′ ← E′ \ {(xparent, xnear)} 17: E′ ← E′ ∪ {(xnew, xnear)} return G′ = (V ′ , E′ )

The precise definitions of the methods used in the Algorithm 2 are given below.

• NEAR(G, x, η): Returns a set of all vertices within the closed ball of radius rn centered at x, in which rn = min{( γ ξd log n n )1/d , η}. The volume of the ball is min{γ log n n , ξdηd }.
• LINE(x, x′ ) : [0, s] ←Xfree denotes the path defined by line segment from x to x′ .
• COST(v): Returns the cost of the unique path (because G is a tree) from xinit to the vertex v ∈ V . COST(xinit) = 0.

Consider the third layer in Figure 2, which illustrates how the subproblem trees "rewire" to connect to the new vertex. The Utopia reference vector, ˆ zutop k is defined as the k-dimensional vector constructed from each reference tree. The minimum cost of each path from the starting vertex over any other vertex is computed for each reference tree. Using the Utopia reference vector, each subproblem tree connects its new vertex and rewire neighboring vertices in a radius as well. Algorithm 3 precisely follows Algorithm 2 except that instead of computing the cost using one of the objectives, the cost is computed using the Tchebycheff method; each of the mth subproblem trees corresponds to a different weighting vector λm. This is performed using the FITNESS method.

Algorithm 3 EXTENDSub (G, xnew , xnearest , m)

1: if xnew = xnearest then return G = (V,E) 2: V ′ ← V ′ ∪ {xnew} 3: xmin ← xnearest 4: Xnear ← NEAR(G, xnew, |V |) 5: for each xnear ∈ Xnear do 6: if OBSTACLEFREE(xnew, xnear) then 7: c′ ← COST(xnear) +c( LINE(xnear, xnew) ) 8: η′ = FITNESS( c′ , ˆ zutop | λm ) 9: cnew = COST(xnew) 10: ηnew = FITNESS( cnew, ˆ zutop | λm ) 11: if η′ < ηnew then 12: xmin ← xnear 13: E′ ←E′ ∪ {(xmin, xnew)} 14: for each xnear ∈ Xnear \ {xmin} do 15: if OBSTACLEFREE(xnew, xnear) then 16: c′ ← COST(xnew) +c( LINE(xnew, xnear) ) 17: η′ = FITNESS( c′ , ˆ zutop | λm ) 18: cnear = COST(xnear) 19: ηnear = FITNESS( cnear, ˆ zutop | λm ) 20: if η′ < ηnear then 21: xparent ← PARENT(xnear) 22: E′ ← E′ \ {(xparent, xnear)} 23: E′ ← E′ ∪ {(xnew, xnear)} return G′ = (V ′ , E′ )

Reference trees Subproblem tree

The FITNESS method computes costs using one of the cost functions in Equations (1)-(2). Different values of λm are obtained using the pattern in the MOEA-D algorithm: (a) pre-deterimining the range of the K-cost functions, {ck() : 1 . . .K} and (b) sampling from the K-dimensional hypercube defined by these ranges. The M samples from this hypercube can be obtained by either creating a uniform (hyper)-grid or by doing uniform sampling across the space.

4 Analysis

The analysis depends on the following restrictions on the cost functions and obstacle placement required by the RRT∗ algorithm [Karaman and Frazzoli, 2010]. We claim without argument that the cost functions and obstacle placements used in the simulation studies satisfy the restrictions.

Assumption 1. (Additivity of the objective functions) For a path constructed by composing two other paths (to create a discontinuous path), ∀k ∈ K, σ1, σ2 ∈ Xfree, ck(σ1 ◦ σ2) = ck(σ1) + ck(σ2).

Assumption 2. (Continuity of the cost functions) For all k ∈ K, the cost function ck is Lipschitz continuous, that is, for all paths σ1 : [0, s1] → Xfree and σ2 : [0, s2] → Xfree, there exists a constant κ(k) ∈ R+ ∪ {0} such that |ck(σ1) - ck(σ2)| ≤ κ(k) supτ∈[0,1]‖σ1(τ s1) - σ2(τ s2)‖.

Assumption 3. (Obstacle spacing) There exists a constant δ ∈ R+ such that ∀x ∈ Xfree , ∃x′ ∈ Xfree such that

• the δ-ball centered at x′ lies inside Xfree;
• x lies inside the δ-ball centered at x′ .

Lemma 1. If the Utopia reference vector satisfies ∀k, σ zutop k ≤ ck(σ), then any solution of Eq. (2) is Pareto optimal.

Proof. The proof is by contradiction. Let the weighting vector λ be arbitrary subject to ∀k λk ≥ 0, and let σ∗ = σ∗ (λ) be a solution given that weighting vector. By definition,

Assume that the path σ∗ is not Pareto optimal. Then there exist another path σo that dominates σ∗ and the Utopia reference vector that satisfies ∀k ∈ K, zutop k ≤ ck(σ), it follows that ∀k ∈ K, zutop k ≤ ck(σo ) ≤ ck(σ∗ ) and ∃k′ ∈ K, zutop k ≤ ck′ (σo ) < ck′ (σ∗ ). These equations imply

which yields the following contradiction to Eq (3):

Lemma 2. If σ∗ is Pareto optimal then there exists aweighting vector λ, where ∀k λk ≥ 0 and ∑Kk=1 λk = 1, such that σ∗ is a solution of Eq. (2).

Proof. This is a proof by construction over cases. When σ∗ is Pareto optimal, there exist two cases: (a) ∃k, ck(σ) = zutop k and (b) ∀k, ck(σ∗ ) < zutop k .

Define P(σ∗ ) = {j | cj(σ∗ ) = zutop j } and let P = {1, . . . ,K} \ P. Define the weight vector λ as ∀k ∈ P(σ∗ ), λk = 1 |P | and ∀k ∈ P (σ∗ ), λk = 0. For these weights, Eq. (2) returns a set of solution paths, all of which have the same cost for the k-cost functions when k ∈ P but different possible costs for k ∈ P. σ∗ is trivially in this set of solution paths.

For all k, define the weights as λk = ℓk ∑Kj=1 ℓj , where ℓk = 1 |ck(σ∗ )-zutop k | . The Tchebycheff cost (Eq. (2)) becomes

Given any other path σ, we can represent the Tchebycheff cost as follows:

Because σ∗ is Pareto optimal, [∃k′ ∈ K, ck′ (σ) > ck′ (σ∗ )] ∨ [∀k ∈ K, ck′(σ) = ck′(σ∗ )] for any σ. As ∀k, ck(σ∗ ) ≥ zutop k , we have ∀k, ck(σ∗ ) - zutop k ≥ 0. This implies ∃k′ ∈ K, ck′ (σ)-ck′ (σ∗ ) ck′ (σ∗ )-zutop k′ ≥ 0, which, in turn, implies

that maxk∈K

1

∣∣∣1 + ck(σ)-ck(σ∗ )

ck(σ∗ )-zutop

k

∣∣∣ ≥ 1. Therefore, gte (σ) ≥

∑Kj=1 ℓj = gte (σ∗ ). Thus, σ∗ is a solution to Eq. (2).

By Lemma 1 and Lemma 2, we have the following:

Theorem 1. A path is Pareto optimal if and only if it is a solution to Eq. (2) for some weight vector.

Theorem 1 implies that we can use the Tchebycheff method to find the Pareto set for the multi-objective path-planning problems. The next question that needs to be answered is whether the subproblem tree can find the optimal solution of its assigned subproblem.

The way that the RRT∗ algorithmworks is that it incrementally constructs a tree from a root position. The cost of the path from the position of the root node to the positions of every other node converges to the minimal possible cost between the positions as the number of iterations approaches infinity. We restate this as a lemma, and note that it corresponds exactly to that given for Theorem 22 in [Karaman and Frazzoli, 2010].

Lemma 3. Given Assumptions 1-3, the cost of the minimum cost path from the root to any vertex in RRT∗ converges to the optimal cost almost surely.

Lemma 3 and Theorem 1 imply that each reference tree converges to the optimal path from the root to any node in the tree, including a node arbitrarily close to the goal node. This means that the costs returned by those trees for the path from the start to the goal for the cost function ck converges to the kth element of the Utopia reference vector zutop . We state this as a lemma.

Lemma 4. Given Assumptions 1-3, the cost of the minimum cost path from the root to any vertex in kth reference tree converges to z∗ k almost surely.

We now turn to the proof that the subproblem trees converge to paths in the Pareto set. The proof of this claim requires that we know zutop to compute the Tchebycheff cost associated with the cost used in the subproblem. If we knew that the reference trees had already converged to zutop , then we could simply instantiate Lemma 3. Unfortunately, the reference trees are converging at the same time that the subproblem trees are converging. We now address this problem.

Let ˆ zutop (v; i) denote the approximate Utopia reference vector for position v on iteration i, estimated by the cost from the root to position x from the k-reference trees. Recall that the mth subtree attempts to generate a solution to Eq. (2) for a given weight vector λm. Let

denote the cost vector in mth subproblem tree given the reference vector z and let ˆ cSUB m (i, z) denote its estimation at iteration i. A subproblem tree obtains ˆ zutop (v) for vertex v in the reference trees and generate the corresponding cSUB m (v; i, ˆ zutop (v)). This forms a cascade structure from the reference trees to the subproblem tree. By Lemma 4, we have the convergence of the reference trees.

We introduce Assumption 4 to get Lemma 5.

Assumption 4. (Lipschitz continuity) cSUB m (z) in Eq. (4) and its estimation ˆ cSUB m (i, z) are Lipschitz continuous, i.e. ‖cSUB m (za) -cSUB m (zb)‖ ≤K‖za -zb‖.

Lemma 5. Given Assumptions 1-4 , the cost of the solution of mth subproblem tree converges to the corresponding cost of the mth subproblem c∗m almost surely.

Proof. By Lemma 4, we have limj→∞‖z∗ - ˆ z(j)‖ = 0. By Lemma 3, we have limi→∞ ˆ c(i, ˆ z(j)) = c(ˆ z(j)). Thus, limi→∞‖c(z∗ ) - ˆ c(i, ˆ z(j))‖ = ‖limi→∞c(z∗ ) - limi→∞ ˆ c(i, ˆ z(j))‖ = ‖c(z∗ ) - c( ˆ z(j))‖.

Since c(z) and ˆ c(i, z) are Lipschitz continuous; limi→∞‖c(z∗ ) - ˆ c(i, ˆ z(j))‖ ≤ K‖z∗ - ˆ z(j)‖. As j →∞, we have ˆ z(j) → z∗ , thus limi→∞‖c(z∗ ) - ˆ c(i, ˆ z(j))‖ → 0. This implies P({limi→∞ j→∞ cSUB m (i, ˆ z(j)) = c∗m}) = 1.

Now, we can prove that the solution fromMORRF∗ almost surely converges to a subset of the Pareto optimal set.

Theorem 2. Given Assumptions 1-4 , the solution generated by MORRF∗ converges to a subset of the Pareto optimal set almost surely.

5 Simulation

We now present a series of simulation studies that provide evidence that MORRF∗ produces a representative set of samples from the Pareto set. Results fromMORRF∗ are obtained for path-planning problems with two objectives and three objectives, and are compared to a modified version of the NSGA-II multi-objective path-planning algorithm [Ahmed and Deb, 2013] as well as a variant of MORRF∗ that uses a weighted sum rather than the Tchebycheff approach. NSGA-II was selected because evidence suggests that it provides more uniform samples from the Pareto set than other approaches [Deb et al., 2002]. We modified the NSGA-II algorithm for this problem to use paths as inputs, represented by a series of waypoints connected by line segments; the cost calculation is identical with that in MORRF∗ , calling LINE(x1, x2) to calculate the cost between two way points x1 and x2. The weighted sum approach was chosen because evidence suggests that it works well only when all the objectives are convex [Zhang and Li, 2007] whereas the Tchebycheff approach should bring better diversity in the solutions [Zhang and Li, 2007]. The weighted sum approach uses the same sampling method for weights as that used to generate the λi in MORRF∗ . Each method was run for 5000 iterations and restricted to 30 solutions.

(g) Pareto set: Tchebycheff (h) Pareto paths: Tchebycheff

Figure 4: Path planning with two objectives.

The first simulation study compares three algorithms in an obstacle-free world with two objectives: minimize Euclidean distance, see Figure 4a, and minimize a cost function, see Figure 4b. The first thing to note is that the convergence of NSGA-II-based path-planning is very slow. This is indicated in Figures 4c-4d, which show the approximation to the Pareto set and corresponding paths, respectively, after 5000 iterations; observe how the quality of the paths and sampling of the Pareto set is uneven and unsatisfactory. By contrast, the weighted sum approach returns a set of high-quality solutions close to the Pareto optimal set, see Figures 4e and 4f; Finally, note the somewhat uneven clustering of solutions on Pareto front for MORRF∗ using weighted sum, and compare this to the slightly more uniform clustering of MORRF∗ using the Tchebycheff approach in Figures 4g-4h.

We therefore compared results for the two approaches for an environment with obstacles, omitting results for NSGA-II because convergence is so slow. The results are shown in Figure 5. As before, observe that the Tchebycheff approach yields a more uniform sampling, albeit one that appears to be somewhat noisy approximation to the Pareto set.

Finally, we evaluated how MORRF∗ performs three objectives: Euclidean distance and the two other objectives are shown in Figures 6a-6c. As shown in Figure 6, the Pareto front uses the Utopia reference vector (Green point) to better approximate the Pareto set than the weighted sum approach.

(a) Distance

(b) Cost 1

(c) Cost 2

600

550

500

450

400

350

300

200 250 300 350 400 450 500

(e) Pareto set: Tchebycheff

Figure 6: Path planning with three objectives.

6 Summary and FutureWork

This paper presented the MORRF∗ algorithm for the multiobjective path-planning problems on continuous spaces. The algorithm blends principles from the RRT∗ algorithm with principles from multi-objective optimization to produce an algorithm that provides a reasonable approximation of the Pareto set, outperforms a common multi-objective optimization problem on a path-planning problem, and has guaranteed best-case performance.

Future work should extend the algorithm to include not only the weighted sum and Tchebycheff approach but also the boundary intersection approach, which results from [Zhang and Li, 2007] suggest might have even better diversity. MORRF∗ could also be made more efficient by, for example, using prior information to improve the set of sample points.

Another area of future work is to combine MORRF∗ with Bellman's principle of optimality. This could be done by setting a goal position as the root node in the algorithm and then generating a set of Pareto optimal paths. The algorithm should then converge to the set of Pareto optimal from any vertex in the tree to the goal.

Object ive 3