Multi-Objective Path-Based D* Lite

D* Lite [8] is an incremental version of A* [7] that searches backwards from $u_{d}$ to $u_{c}$ so that the constructed search tree, which stores partial solution paths, can be reused as $u_{c}$ changes. To make the presentation consistent, for the rest of the work, we present all the methods by searching backwards from $u_{d}$ to $u_{c}$.

During the search, D* Lite maintains two types of cost-to-come at a node $u\in\mathcal{U}$: the $\mathbf{g}$-value $\mathbf{g}(u)$ and $\mathbf{v}$-value $\mathbf{v}(u)$.¹¹ 1 We follow the convention in [1], where $\mathbf{g}$- and $\mathbf{v}$-values are introduced. Value $\mathbf{v}(u)$ stores the cost of the best path found between $u_{d}$ and $u$ during its last expansion, while $\mathbf{g}(u)$ is computed from the $\mathbf{v}$-values of $ngh(u)$, and thus, is potentially better informed than $\mathbf{v}(u)$. Formally,

Based on the $\mathbf{g}$- and $\mathbf{v}$-values, a node $u$ is consistent if $\mathbf{v}(u)=\mathbf{g}(u)$, and inconsistent otherwise. An inconsistent node $u$ is either underconsistent ($\mathbf{v}(u)>\mathbf{g}(u)$) or over-consistent ($\mathbf{v}(u)<\mathbf{g}(u)$). To initialize, the $\mathbf{g}$-values of all nodes but $u_{d}$ are set to $\infty$ and $\mathbf{g}(u_{d})$ is set to zero, while the $\mathbf{v}$-values of all nodes are set to $\infty$. Clearly, $u_{d}$ is the only inconsistent (and overconsistent as $\mathbf{v}(u_{d})<\mathbf{g}(u_{d})$) node at initialization.

Let $h(u)$ denote the cost-to-go, which underestimates the cost of paths between $u$ and $u_{c}$, and define $\mathbf{f}(u):=\mathbf{g}(u)+\mathbf{h}(u)$. D* Lite defines the key of nodes as $key(u)=[k_{1}(u),k_{2}(u)]$ with $k_{1}(u)=\min\{\mathbf{v}(u),\mathbf{g}(u)\}+\mathbf{h}(u)$ and $k_{2}(u)=\min\{\mathbf{v}(u),\mathbf{g}(u)\}$. Let OPEN denote a priority queue containing all inconsistent nodes to be expanded, where the nodes are prioritized by comparing their keys in the lexicographic order. In other words, $key(u)<key(w),u,w\in\mathcal{U}$ if $k_{1}(u)<k_{1}(w)$ or both $k_{1}(u)=k_{1}(w)$ and $k_{2}(u)<k_{2}(w)$. The OPEN in D* Lite always contains all inconsistent nodes, and in each search iteration, the node with the minimum key is selected for expansion.

To expand an inconsistent node $u$, $\mathbf{v}(u)$ is made equal to $\mathbf{g}(u)$, which makes $u$ consistent, and for every node $w\in ngh(u)$, $\mathbf{g}(w)$ is updated based on Eqn. (1). Additionally, a parent pointer $parent(u)$ is maintained at node $u$ when $u$ is expanded so that a path between $u_{d}$ and $u$ can be easily reconstructed by iteratively following the parent pointers. D* Lite terminates when no node in OPEN has a smaller key than $key(u_{c})$, which guarantees that $\mathbf{v}(u_{c})$ has reached the minimum and an optimal solution path between $u_{d}$ and $u_{c}$ can be reconstructed.

When computing the initial solution path $\pi(u_{d},u_{o})$ (note that $u_{c}=u_{o}$), D* Lite is equivalent to (backwards) A* search. After the generation of $\pi(u_{d},u_{o})$, if edge costs change, D* Lite recomputes the $\mathbf{g}$-values of nodes that are immediately affected by these edges. Among these nodes, inconsistent ones are inserted into OPEN with updated keys. Then, D* Lite runs in the same manner by expanding inconsistent nodes until all remaining nodes in OPEN have keys no less than $key(u_{c})$.

The basic difference between MO-SPP and SPP is that there are multiple non-dominated partial solution paths between any pair of nodes in the graph in general. Consequently, different from A* where $\mathbf{g},\mathbf{h},\mathbf{f}$-values are computed for each node, MOA* [21] introduces $G,H,F$ sets: $G(u),\forall u\in\mathcal{U}$ is a set of non-dominated cost vectors, each of which represents a non-dominated path between $u_{d}$ and $u$. Similarly, $H(u)$ is a set of heuristic vectors, each of which underestimates the cost of a non-dominated path between $u$ and $u_{c}$. The $F$-set is defined as $F(u):=ND\{\vec{g}+\vec{h}\,|\,\vec{g}\in G(u),\vec{h}\in H(u)\}$, where $ND(\cdot)$ is an operator that takes a set of vectors (denoted as $B$) as input and computes its non-dominated subset (denoted as $ND(B)$), $i.e.$ for any $a,b\in ND(B)$, $a$ and $b$ are non-dominated. To simplify the presentation without losing generality, we consider the case where $H(u)$ of a node $u$ contains only a single heuristic vector $\vec{h}(u)$ that (component-wise) underestimates the cost vector of all paths between $u$ and $u_{c}$.

At any stage of the search process, let $\mathcal{C}$ denote the set of non-dominated cost vectors of the solutions found by the search thus far. Initially, $\mathcal{C}$ is empty. The output of the search process is $\mathcal{C^{*}}$ which is the true Pareto-optimal front for a given problem instance. In every search iteration, MOA* selects a node $u$ from OPEN so that there exists $\vec{f}\in F(u)$ that is non-dominated by any vector $\vec{f}^{\prime}\in F(u^{\prime})$ for any other node $u^{\prime}\in$ OPEN, $u^{\prime}\neq u$. MOA* then expands the selected node $u$ by extending all partial solutions represented by vectors in $G(u)$. For each node $w\in ngh(u)$, a set of new partial solution paths represented by cost vectors $G^{\prime}=\{\vec{g}(u)+\vec{c}(w,u)\,|\,\vec{g}(u)\in G(u)\}$ is computed and $G(w)\leftarrow ND(G(w)\bigcup G^{\prime})$, so that $G(w)$ contains all non-dominated cost vectors at $w$ after expanding $u$. In addition, $F(w)$ is updated and node $w$ is added to OPEN for future expansion if there exists $\vec{f}\in F(w)$ that is non-dominated by cost vectors in $\mathcal{C}$.

There are two features of MOA* (node-based) that distinguish it from NAMOA* (path-based, see Sec. IV-D):

• •

  when a new non-dominated partial solution is found at node $u$, node $u$ is (re-) inserted into OPEN;

• •

  when a node $u$ is selected from OPEN for expansion, all non-dominated partial solutions at $u$ are extended.

These two features show that MOA* takes a node-based expansion strategy. As one can expect, MOA* can lead to a lot of re-expansion of nodes as there are multiple non-dominated partial solutions at each node for a MO-SPP. In addition, node expansion can be computationally demanding as all partial solutions at this node need to be extended.

D* Lite and MOA* can be combined as MOD* algorithm⁵⁵ 5 The MOD* algorithm presented in this section simplifies the method in [12] to highlight the key idea. Readers can refer to [12] for more details. by introducing a $V$-set at each node, which resembles the $\mathbf{v}$-value of a node in D* Lite, and stores the set of non-dominated cost vectors during its last expansion. Formally, it has the following relationship with the $G$-sets of neighbors.

Correspondingly, a node $u$ is consistent if $G(u)=V(u)$ (two sets are exactly the same) and inconsistent otherwise. Similarly to D* Lite, the OPEN in MOD* contains inconsistent nodes. MOD* iteratively selects inconsistent node $u$ from OPEN for expansion until all vectors in $F(u)$ of any inconsistent nodes $u$ in OPEN are dominated by some cost vector in $\mathcal{C}$.

When the cost vector of an edge changes, MOD* first recomputes the $G$-set of each node $u$ that are immediately affected and inserts $u$ into OPEN if $u$ is inconsistent. Then MOD* searches in the same manner by expanding inconsistent nodes until all Pareto-optimal paths are found.

While both MOA* and MOD* expand nodes, NAMOA* [11], employs a path-based expansion to mitigate the drawbacks of the node-based expansion.

Let $s=(u,\vec{g})$ denote a state, a tuple of a node $u$ and a cost vector $\vec{g}$, which identifies a partial solution path between $u_{d}$ and $u$ with cost $\vec{g}$. Additionally, $s$ is said to be at node $u$. To simplify notations, let $u(s)$ and $\vec{g}(s)$ denote the node and the cost vector contained in $s$. For a state $s$, the $\vec{f}$-vector of $s$ is defined as $\vec{f}(s):=\vec{g}(s)+\vec{h}(u(s))$. In NAMOA*, states (rather than nodes) are stored in OPEN as candidates. In every search iteration, NAMOA* expands a non-dominated state $s$ in OPEN, i.e. $\vec{f}(s)$ is non-dominated by the $f$-vector of any other states in OPEN. To expand $s$, the partial solution path represented by $s$ is extended to each neighbor $w\in ngh(u(s))$, where a new state $s^{\prime}=(w,\vec{g}^{\prime})$ with $\vec{g}^{\prime}\leftarrow\vec{g}+\vec{c}(u,w)$ is generated. Cost vector $\vec{g}^{\prime}$ is then compared with both the cost vectors of other partial solution paths at $w$ and the cost vectors in $\mathcal{C}$. If $\vec{g}^{\prime}$ is non-dominated, $s^{\prime}$ is added to OPEN for future expansion.

As every state represents a partial solution path, expanding a state is essentially expanding a path. This path-based strategy employed by NAMOA* avoids the large number of re-expansion of nodes as in MOA*. In addition, expanding a path is computationally cheaper than expanding a node.

MOPBD* inherits (i) the notions of $G,H,F$-sets from MOA* (Sec. IV-B), (ii) the $V$-sets from MOD* (Sec. IV-C), and (iii) the concept of states from NAMOA* (Sec. IV-D). During the search, each vector $\vec{g}\in V(u),\forall u\in\mathcal{U}$ represents a non-dominated path between $u_{d}$ and $u$ that has been found by the planner. $G(u)$ “looks one step ahead” and is computed from $V(u^{\prime}),\forall u^{\prime}\in ngh(u)$. Each vector in $V(u_{c})$ identifies a Pareto-optimal solution path between $u_{d}$ and $u_{c}$ and we also refer to $V(u_{c})$ as $\mathcal{C}$ (the set of solution cost vectors found by the planner) for presentation purposes. Finally, we introduce a new concept of inconsistent states, which identifies partial solution paths that need to be expanded.

MOPBD* is described in Alg. 1 and is conceptually visualized in Fig. 2. MOPBD* is initialized (line 1-2) by inserting a zero vector into $G(u_{d})$ and creating an initial state $s_{d}$. Since $V(u_{d})=\emptyset$ at initialization, state $s_{d}$ is an inconsistent state by Def. 2 and is inserted into OPEN for expansion. Then, MOPBD* plans paths via the ComputePath procedure (line 3 in Alg. 1). If the robot has not yet reached its destination, MOPBD* receives updating information about the cost vector of edges, finds all inconsistent states caused by the edge cost change (via the ProcessEdge procedure) and re-computes paths. If no change in edge costs, the robot navigates towards the destination along planned paths (denoted as FollowPath). Note that for each $\vec{g}\in\mathcal{C}$, a corresponding solution path can be readily reconstructed by following the parent pointers.

As shown in Alg. 2 (ComputePath), in each search iteration, an inconsistent state $s$, with a non-dominated $\vec{f}(s)$ is popped.²² 2 In practice, the OPEN list is often implemented by prioritizing states using the lexicographic order of their $\vec{f}$-vectors [14, 22]. The popped state has the lex. min. $\vec{f}$-vector in OPEN and is thus non-dominated within OPEN. We follow this practice in this work. Then, $\vec{f}(s)$ is first compared against every cost vector in $V(u_{c})$ ($i.e.$ $\mathcal{C}$). As $\vec{h}(u_{c})=\vec{0}$, if any $\vec{g}^{\prime}\in V(u_{c})$ is component-wise no larger than $\vec{f}(s)$ ($i.e.$ $\vec{g}^{\prime}\leq\vec{f}(s)$), then $s$ can not lead to a cost-unique Pareto-optimal solution and is thus filtered by solutions: $s$ is inserted into another queue $Q$ and the current iteration ends. Here, $Q$ stores all states that are filtered by solutions and are reserved for expansion in the next planning task. This is necessary because: When the cost of an edge changes, a (previously found) solution may become no more Pareto-optimal and the states in $Q$ may lead to a Pareto-optimal solution in the next planning task. To conceptually visualize, in Fig. 2 (d), the blue dashed line represents such a partial solution path, which leads to a Pareto-optimal solution after the green path is no more Pareto-optimal due to the cost change.

If not filtered by solutions, $\vec{g}(s)$ is compared against each vector $\vec{g}^{\prime}\in V(u(s))$ (line 7-9 in Alg. 2). If $\vec{g}^{\prime}\leq\vec{g}(s)$ ($i.e.$ component-wise no larger than), then $s$ cannot lead to a cost-unique Pareto-optimal solution and is thus discarded. The current iteration ends.

After these comparisons, state $s$ is made consistent by adding it to $V(u(s))$ to update $V(u(s))$ via the UpdateVset procedure, which is elaborated in the ensuing section. Note that this includes the case when $u(s)=u_{c}$, where $V(u_{c})$ ($i.e.$ $\mathcal{C}$) is updated. It means a new solution path with cost vector $\vec{g}(s)$ is found between $u_{d}$ and $u_{c}$.

After UpdateVset, $s$ is expanded (line 11-16 in Alg. 2): For each $u^{\prime}\in ngh(u(s))$, a path that reaches $u^{\prime}$ from $u(s)$ is generated and represented by state $s^{\prime}=(u^{\prime},\vec{g}(s)+\vec{c}(u^{\prime},u))$. Then $\vec{g}(s^{\prime})$ is compared with each vector in $G(u(s^{\prime}))$: If there exists a vector in $G(u(s^{\prime}))$ that is no larger than $\vec{g}(s^{\prime})$, $\vec{g}(s^{\prime})$ is then discarded; Otherwise, state $s^{\prime}$ is added to OPEN for future expansion, and vector $\vec{g}(s^{\prime})$ is added to $G(u(s^{\prime}))$. Additionally, the parent of $s^{\prime}$ is marked as $s$, and $s^{\prime}$ is marked as a children of $s$. MOPBD* keeps track of ancestors and descendants of each state during the search via these parent and children pointers of generated states, which are used in the Delete procedure (Sec. V-C).

The search process iterates until OPEN is empty. Then, $Q$ is assigned to OPEN for the next planning task (line 17 in Alg. 2), and $V(u_{c})$ ($i.e.$ $\mathcal{C}$) is returned, which is guaranteed to be equal to $\mathcal{C}^{*}$, the true Pareto-optimal front of the current planning task.

Before describing UpdateVset, we introduce the Delete procedure, which is invoked by UpdateVset. As its name suggests, the purpose of the Delete procedure is to remove all descendant states that have been generated during the search of a given state $s$. First, the Delete procedure invokes itself recursively for each children state of $s$ (line 1-2 in Alg. 3). Then, vector $\vec{g}(s)$ is removed from $G(u(s))$. If $V(u(s))$ contains $\vec{g}(s)$, then $\vec{g}(s)$ is also removed from $V(u(s))$ and node $u(s)$ is added to set $N$, which stores all the nodes whose $V$-sets have been modified during the recursive deletion. Note that, set $N$ is passed from outside as an argument of Delete and is modified within Delete. Finally, the parent and children pointers related to $s$ are removed.

Now, we explain UpdateVset. As shown in Alg. 4, given a state $s$, to update $V(u(s))$, UpdateVset loops over each existing vector $\vec{g}^{\prime}$ in $V(u(s))$. If $\vec{g}(s)\leq\vec{g}^{\prime}$, then both the corresponding state $s^{\prime}\leftarrow(u(s),\vec{g}^{\prime})$ and all descendants of $s^{\prime}$ are removed by invoking the Delete procedure.³³ 3 Note that both UpdateVset and Delete are necessary as edge costs can become smaller at line 5 in Alg. 1, and in the next planning task, some vectors in $V(u),u\in\mathcal{U}$ are no more non-dominated. Additionally, let $N$ denote a set of nodes, which is initialized as an empty set (line 1 in Alg. 4), and is passed to the Delete procedure to store all the nodes whose $V$-sets are modified during Delete. The usage of $N$ is explained in the next paragraph. Then, $\vec{g}(s)$ is added to $V(u(s))$. By doing so (line 1-6 in Alg. 4), $V(u),\forall u\in\mathcal{U}$ always contains the cost vectors of non-dominated paths between $u_{d}$ and $u$ (Invariant-1).

The second part of the UpdateVset procedure (line 7-12 in Alg. 4) seeks to find all new inconsistent states that should be generated and expanded after the modification of $V$-sets: As aforementioned, $V(u)$ for each $u\in N$ has been modified during the Delete procedure, which means, some vector $\vec{g}_{k}$ has been removed from $V(u)$. It’s possible that the vectors $\{\vec{g}_{l}\}$ that are previously ($i.e.$ before the removal of $\vec{g}_{k}$) dominated by $\vec{g}_{k}$ becomes non-dominated after the removal of $\vec{g}_{k}$, and may lead to Pareto-optimal solutions. To find $\{\vec{g}_{l}\}$, UpdateVset loops over each node $u\in N$ and computes the new $G$-set of $u$ (after Delete) based on Eqn. (2), which is denoted as $G^{\prime}$. Then, for each vector $\vec{g}^{\prime}$ that is contained in $G^{\prime}$ but not contained in $G(u)$, a corresponding new state $s^{\prime}\leftarrow(u,\vec{g}^{\prime})$ is generated and inserted to OPEN for future expansion. Also, $\vec{g}^{\prime}$ is added to $G(u)$, and the parent and children pointers of $s^{\prime}$ are updated correspondingly. By doing so (line 7-12 in Alg. 4), all new inconsistent states at each node in $N$ are found and are added to OPEN.

After ComputePath, Alg. 1 either follows the planned paths or finds changes in edge costs. As shown in Alg. 5 (ProcessEdge), when the cost vector of an edge $(u_{1},u_{2})$ changes, for each $\vec{g}\in G(u)$ where $u\in\{u_{1},u_{2}\}$, if the corresponding state $s=(u,\vec{g})$ and its parent state $parent(s)$ are at the both ends of edge $(u_{1},u_{2})$ (line 5 in Alg. 5), then $s$ represents a (partial solution) path that goes through $(u_{1},u_{2})$. This path is thus affected by the change of the cost vector, and both $s$ and all descendant states of $s$ are deleted by invoking the Delete procedure (line 6). Line 1-6 in Alg. 5 ensures that when the edge cost changes, the $V$-set of any node $u\in\mathcal{U}$ still contains the cost vectors of non-dominated paths between $u_{d}$ and $u$ ($i.e.$ Invariant-1).

In the meanwhile, similarly to the aforementioned UpdateVset, the set of all nodes, whose $V$-sets are modified during the Delete procedure, are stored in set $N$. Then, line 7-12 in Alg. 5 are the same as line 7-12 in Alg. 4, which finds all new inconsistent states that should be generated after the modification of $V$-sets.

ComputePath is invoked either at line 3 or line 9 in Alg. 1. At both places, before entering ComputePath, it’s ensured that all inconsistent states ($i.e.$ $\{(u,\vec{g})\,|\,\vec{g}\in G(u)\backslash V(u),\forall u\in\mathcal{U}\}$ are in OPEN. After entering ComputePath, in each search iteration, an inconsistent state $s$ is popped from OPEN and must either be (i) inserted into $Q$ ($i.e.$ line 4-6 in Alg. 2), (ii) discarded ($i.e.$ line 7-9 in Alg. 2), or (iii) expanded ($i.e.$ line 10-16 in Alg. 2). For (i) and (ii), it’s impossible for $\vec{g}(s)$ to be part of $\mathcal{C}^{*}$. For (iii), $V(u),\forall u\in\mathcal{U}$ are updated to contain all non-dominated paths between $u_{d}$ and $u$ and all possible non-dominated children states of $s$ (which are inconsistent) are generated and inserted into OPEN when $s$ is expanded. ComputePath iterates until OPEN depletes, which guarantees that $V(u_{c})$ ($i.e.$ $\mathcal{C}$) is the same as $\mathcal{C}^{*}$, which is summarized in the following theorem.

In MOPBD*, each planning task requires solving a MO-SPP, which is known to be NP-hard even with two objectives [6]. It is also known that multi-objective search requires exponential space and time with respect to the size of the graph in the worst case [6]. The runtime of Alg. 1 is determined by the number of states to be deleted (in ProcessEdge) and the number of expansions (in ComputePath). In the worst case, Alg. 1 needs to first recursively delete all previous search results via the Delete procedure and then start to search (from scratch). MOPBD* is thus less efficient in comparison with naively searching from scratch, when there are lots of states to be deleted after the edge cost changes.

When there are more than two objectives, computing $\mathcal{C}^{*}$ becomes computationally expensive due to the enormous size of $\mathcal{C}^{*}$. Correspondingly, how to fast approximate $\mathcal{C}^{*}$ becomes an important problem and several approximation algorithms (such as [5, 13]) have been developed. In this work, we leverage $\epsilon$-dominance [13] to enable MOPBD* to approximate $\mathcal{C}^{*}$.

We propose MOPBD*-$\epsilon$ by replacing the $\leq$ comparison in MOPBD* with $\epsilon$-dominance. It’s obvious that with a larger $\epsilon$, more partial solutions are pruned at each node during the search and the $G$- and $V$-sets at each node have a smaller size. Consequently, both ProcessEdge and ComputePath runs faster as there are fewer paths to be deleted or expanded when edge costs change. As a result, MOPBD*-$\epsilon$ is able to trade off between the quality of the approximated solutions and the search efficiency, which is verified in the ensuing section.

We selected (grid) maps of different categories (empty, maze, random, game) from an online data set [20] and generated a graph $G$ by making each grid four-connected. We assigned every edge in $G$ a random integer vector of length $M$ with components randomly sampled from $[1,10]$, where $M$ varies in the following sections. To test a planning algorithm (referred to as “planner” hereafter), we implemented the following simulator (Fig. 1). For each test instance, the simulator does the following steps in order:

The simulation terminates either when the robot arrives at $u_{d}$ (i.e. $u_{c}=u_{d}$), or when the planner returns no paths, which means the added obstacle in (Step-3) eliminates all feasible solutions. We call (Step-1) the initial planning task and (Step-3) the subsequent planning task. We set a time limit of one minute for each planning task. We implemented MOD*, NAMOA* and MOPBD* in Python. All algorithms use the same heuristic: $\vec{h}(u),u\in\mathcal{U}$, which is a unit vector scaled by the Manhattan distance between $u$ and $u_{c}$. Both MOD* and NAMOA* serve as baselines.

We begin our tests with $M=2$. As shown in Table I, MOPBD* (path-based) runs faster than MOD* (node-based) by up to an order of magnitude. Note that, the number of expansions cannot be directly compared between MOPBD* and MOD* as they conduct path expansion and node expansion respectively. In the last map (a game map of size $65\times 81$), the average number of solutions found by MOD* is smaller than the other two algorithms since MOD* times out in some planning tasks.

Table I also shows a comparison between NAMOA* and MOPBD*, both of which conduct path-based expansion while NAMOA* computes from scratch and MOPBD* reuses previous searches. In terms of the number of expansions, MOPBD* outperforms NAMOA* over all maps. In terms of runtime, MOPBD* outperforms NAMOA* in general. However, as we observed in the $16\times 16$ empty map, MOPBD* runs slower than NAMOA* on average. The reason is that the ProcessEdge procedure in MOPBD* is expensive when cost vectors change, as it requires deleting all affected states, and recomputing the $G$-sets of affected nodes, which is computationally demanding.

Next, we test with $M=3$ (three objectives) using the same simulator described in Sec. VII-A to verify MOPBD*-$\epsilon$ in the aforementioned game map. As a baseline, the dominance in NAMOA* is replaced with $\epsilon$-dominance to search from scratch for each planning task. This baseline is denoted as NAMOA*-$\epsilon$. Here, $\epsilon$ varies among $\{0.01,0.02,0.05\}$.

Given a test instance, let $l_{k}$ denote the average length of the Pareto-optimal paths computed in the $k$-th planning task. When $k=0$, $l_{0}$ denote the average length of the Pareto-optimal paths between the initial start and $u_{d}$. The ratio $l_{k}/l_{0}$ estimates how far away the robot is to $u_{d}$ for the $k$-th planning task. In Fig. 3, the horizontal axis represents $l_{k}/l_{0}$ within the range $[0,1]$ and the vertical axis represents the runtime of all subsequent planning tasks.

Here, green dots correspond to running NAMOA* from scratch for every planning task, and blue stars and red crosses correspond to MOPBD*. Red crosses mean that MOPBD* is slower than NAMOA*, while the blue stars mean MOPBD* is faster. First, both planners run faster when $\epsilon$ increases. When $\epsilon=0.01$, there are only a few data points because many planning tasks time out. Second, as $\epsilon$ increases, there are fewer red crosses and more blue stars, which indicates that MOPBD*-$\epsilon$ gradually outperforms NAMOA*-$\epsilon$. The reason is that when $\epsilon$ increases, only a few non-dominated partial solution paths are stored at each node, and the number of vectors in the $V$-sets (as well as the $G$-sets) at nodes become smaller, which makes the procedure ProcessEdge computationally less demanding when edge costs change.

Finally, we test MOPBD* by adding and deleting multiple obstacles around the robot by modifying (Step-3) of the aforementioned simulator: (Step-3) now alternates between adding and deleting two random obstacle nodes in the $5\times 5$ square area centered on the robot’s location. Note that by adding an obstacle node, we modify the cost vector of each edge incident on that node to an infinite vector. Similarly, deleting an obstacle node means assigning each edge incident on that node some finite random cost vector. In this test, each component of the edge cost vector is randomly sampled from integers within the range $[1,5]$, and the runtime limit is set to five minutes. We select the “maze” map and test with $M=2,3,4$ and $\epsilon=0$.

As shown in Table. II, MOPBD* outperforms running NAMOA* from scratch for each planning task in general, based on the median and the average over succeeded cases (the better results are highlighted in the bold text). The reason is that when randomly adding/deleting multiple obstacles around the robot, these random obstacles may affect only a few or even no paths, which allows MOPBD* to quickly fix the plan. However, as the number of objectives increases, the advantage of MOPBD* becomes less obvious and when $M=4$, NAMOA* outperforms MOPBD*. The reason is that when $M$ increases, there are more non-dominated partial solution path between a pair of nodes in general, which makes ProcessEdge computationally expensive when edge costs change.