P LANNING collision-free trajectories for a robot amid dy- namic obstacles is of fundamental importance in Robotics with numerous applications [24], [26]. In this work, we focus on a graph-based formulation of the problem in which the goal is to find a collision-free trajectory from a given start node to a destination node in the presence of dynamic obstacles whose motions are known. This problem has been addressed for a single objective (e.g. minimizing the arrival time of the robot at its destination) by several algorithms, such as the popular safe-interval path planning (SIPP) [13] method and its variants [4], [12], [27].
One can envision applications, ranging from urban search and rescue [5], [7], autonomous driving [1] to logistics [26], where multiple (conflicting) objectives such as arrival time, energy consumption and communication robustness, need to be optimized simultaneously. Aggregating these objectives into a single, weighted objective is difficult because the choice of weights is hard to obtain [19] and may not be known apriori. This challenge motivated research in multi-objective path planning (MOPP) problems [8], [22], which generalizes the conventional (single-objective) path planning problem by associating each edge in the graph with a cost vector where Zhongqiang Ren, Maxim Likhachev and Howie Choset are with Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15213, USA. (email: zhongqir@andrew.cmu.edu; maxim@cs.cmu.edu; choset@andrew.cmu.edu).
Sivakumar Rathinam is with Texas A&M University, College Station, TX 77843-3123. (email: srathinam@tamu.edu). Fig. 1: A motivating example of MOPPwDO in the context of urban search and rescue. A robot needs to plan collisionfree paths among dynamic obstacles in a city-like map while optimizing the arrival time and communication robustness along the path. For paths with smaller arrival times, the robot may have to traverse regions with no communication (the white area). Computing a Pareto-optimal set of solutions can reveal the underlying trade-off between different objectives and can potentially help decision makers to better understand the mission and make informed decisions. each component of the vector corresponds to an objective to be minimized.
In the presence of multiple conflicting objectives, in general, there is no single solution path that optimizes all the objectives at the same time. Therefore, the goal of MOPP is to find a Pareto-optimal set and its corresponding cost vectors referred to as the Pareto-optimal front. A solution is called Pareto-optimal if no objective can be improved without deteriorating at least one of the other objectives. Finding the Pareto-optimal front for MOPP even with two objectives can be computationally hard [6], [21]. There are several multiobjective A* (MOA*) planners [9], [22] in the literature to address the challenges in MOPP. However, we are not aware of existing MOA* planners that can find the Pareto-optimal front for a MOPP with Dynamic Obstacles (MOPPwDO). This paper aims to fill this gap.
One way to solve MOPPwDO is to (i) add a time dimension {0, 1, . . . , T } to the given graph G and construct a timeaugmented graph G t = G × {0, 1, . . . , T } where dynamic obstacles are represented as blocked nodes in G t , and (ii) run existing MOA* planners on G t to find the Pareto-optimal front. The inclusion of the time dimension complicates the problem as it significantly increases the size of the graph to be searched. To bypass this challenge, we leverage the concept of safe intervals from SIPP which compresses time steps into contiguous safe and unsafe intervals to efficiently represent the search space. We then develop an algorithm called Multi-Objective Safe-Interval Path Planning (MO-SIPP) by leveraging the notion of dominance from the multi-objective optimization literature [2] and search techniques from MOA* algorithms [9], [23]. We show that MO-SIPP is guaranteed to find the entire Pareto-optimal front.
Motivated by urban search and rescue [5], [7], we generate test instances using city-like maps (Fig. 1) from an online data set and evaluate MO-SIPP with extensive tests where arrival time, communication robustness and obstacle clearance are considered. Our numerical results show that MO-SIPP runs up to an order of magnitude faster than the baseline. 1 To facilitate practitioners' usage and further development, we have made our MO-SIPP implementation available online 2 .
The rest of the article discusses the related work in Sec. II, formulates the problem in Sec. III, and reviews SIPP in Sec. IV. We then present MO-SIPP in Sec. V, and analyze its properties in Sec. VI. Numerical results are then presented in Sec. VII, with conclusion and future work in Sec. VIII.
Existing approaches for multi-objective path planning (MOPP) problems compute an exact or approximated set of Pareto-optimal paths for the robot between its start and goal locations with respect to multiple objectives. One common approach to solve a MOPP is to weight the multiple objectives and transform it to a single-objective problem [2], [3]. The transformed problem can then be solved using any singleobjective algorithm. This approach, however, requires an indepth knowledge of the application to design the weighting procedure; it may also requires one to repeatedly solve the transformed single-objective problem for different sets of weights in order to capture the Pareto-optimal front which is quite challenging [10].
Additionally, MOPP has been solved directly via graph search techniques [9], [22], [23] and evolutionary algorithms [25], to name a few, where a Pareto-optimal set of solutions is computed exactly or approximately. These graphbased approaches provide guarantees about finding all Paretooptimal solutions but may run slow for hard cases, especially when the number of Pareto-optimal solutions is large. The MO-SIPP in this work belongs to this category of methods that compute a set of Pareto-optimal solutions with quality guarantees.
Finally, MO-SIPP differs from our prior work MOPBD* [18]. Although both algorithms consider a dynamic environment, MOPBD* considers the scenario where graph edge costs can change while MO-SIPP focuses on avoiding dynamic obstacles.
Safe-interval path planning (SIPP) [14] was originally developed to compute a collision-free trajectory from a start to a goal location while minimizing the arrival time, in an environment with dynamic obstacles moving along known trajectories. SIPP introduces the notion of safe intervals to efficiently represent the search space and identifies that by arriving at each safe interval at the earliest possible time, the computed solution is optimal. SIPP has been extended in several variants in the literature, such as sub-optimal SIPP [13], anytime SIPP [12], generalized SIPP [4], any-angle SIPP [27], etc. However, all these algorithms optimize a single objective.
Let G = (V, E) denote a graph with vertex set V representing the possible locations of the robot in the workspace, and edge set E representing the transition between locations. Let G t = (V t , E t ) = G × {0, 1, . . . , T } denote a time-augmented graph corresponding to G, where each vertex v ∈ V t is defined as v = (u, t), u ∈ V, t ∈ {0, 1, . . . , T } and T is the time horizon, which is typically a large positive integer. Edges in G t are represented as E t = V t × V t where vertices (u 1 , t 1 ), (u 2 , t 2 ) are connected in G t if (u 1 , u 2 ) ∈ E and t 2 = t 1 + 1. 3 In addition, (u, t), (u, t + 1), u ∈ V is connected in G t to represent the wait in place action of the robot.
A dynamic obstacle along known trajectory is represented as a set of blocked nodes in G t . An illustration of G, G t and dynamic obstacles is shown in Fig. 2. Each edge e ∈ E is associated with a non-negative cost vector c(e) ∈ (R + ) M with M being a positive integer and R + being the set of non-negative real numbers. The wait in place action takes a constant non-negative cost vector c wait at any nodes in G.
Let π(v 0 , v ℓ ) denote a path connecting a pair of vertices
where the subscript t of v t ∈ π(v 0 , v ℓ ) indicates the time step and v t , and v t+1 are connected by an edge
Let g(π(v 0 , v ℓ )) denote the cost vector corresponding to the path π(v 0 , v ℓ ), which is the sum of the cost vectors of all edges present in the path:
To compare any two paths, we compare the cost vectors associated with them using the dominance relation [2]:
Definition 1 (Dominance): Given two vectors a and b of length M , a dominates b (denoted as a b) if and only if a(m) ≤ b(m), ∀m ∈ {1, 2, . . . , M }, and a(m) < b(m), ∃m ∈ {1, 2, . . . , M }. If a does not dominate b, we say a is non-dominated by b. Any two paths π 1 (v 0 , v ℓ ), π 2 (v 0 , v ℓ ) are non-dominated (with respect to each other) if the corresponding cost vectors are non-dominated by each other.
Let v o and v d denote the initial and destination nodes in G respectively. The set of all non-dominated paths between v o and v d is called the Pareto-optimal set. A maximal subset of the Pareto-optimal set, where any two paths in this subset do not have the same cost vector is called a cost-unique Paretooptimal set. This paper considers the Multi-Objective Path Planning with Dynamic Obstacles (MOPPwDO) problem that aims to compute a cost-unique Pareto-optimal set.
MOPPwDO reduces to the SIPP problem [14] when the number of objectives (M ) is equal to 1 and the cost of any edge e ∈ E is the time required to traverse e. A naive baseline approach to solve the SIPP problem is to apply A* to search over G t . However, this A* approach is inefficient as the time dimension is searched in a step-by-step manner (i.e., the time step is increased by one unit after each expansion). To overcome this challenge, SIPP [14] compresses time steps into intervals. Let tuple s = (v, [t a , t b ]) denote a search state at node v ∈ G, where t a , t b are the beginning and ending time steps of a safe (time) interval respectively. A safe interval is a maximal contiguous time range in which a node is not blocked by any dynamic obstacles. State s = (v, [t a , t b ]) indicates that node v is not blocked by any dynamic obstacle and hence the name safe interval for [t a , t b ]. Note that, any two safe intervals at the same node never intersect. Two states are the same, if both states share the same node, the beginning and ending time steps. Otherwise, two states are different. For example, two states with the same node but different safe intervals are different states.
SIPP conducts A*-like heuristic search. For each state s, let g(s) represent the earliest arrival time at state s at any time of the search and let h(s) denote the heuristic value of s, which underestimates the cost-to-go (i.e., travel time to v d from s). In addition, the f -value of a state is f (s) := g(s) + h(s). Let OPEN denote the open list containing candidate states to be expanded, where candidate states are prioritized by their f -values.
SIPP starts by inserting the initial state s o into OPEN, where s o is a tuple of v o and the safe interval with a beginning time set to zero. In each search iteration, a state with the minimum f -value in OPEN is popped and expanded. To expand a state s = (v, [t a , t b ]), SIPP considers all reachable successor states from s and finds the earliest possible arrival time at each of those states via "wait and move" actions (i.e., wait for a minimum amount of time to arrive at the successor state as early as possible). A key observation in SIPP is that, arriving at a state s at the earliest possible time can generate the maximum number of successors from state s.
We provide examples of states and state expansion. In Fig. 2, at node b, there are two possible states (b, [0, 1]) and (b, [3, T ]) while at node e, there is only one possible state (e, [0, 2]). The agent's initial state is (a, [0, T ]). To expand the initial state, one successor is generated at node d, which is the state (d, [0, T ]) with the earliest arrival time 1, and two successors are generated at node b, which are (b, [0, 1]) and (b, [3, T ]) with the earliest arrival time 1 and 3 respectively. During the search, SIPP records the earliest arrival time found thus far as g(s) at each state s. When a new path is found to reach state s (from v o ) with an earlier arrival time, g(s) is updated. Here, a path from v o to some state s = (v, [t a , t b ]) means a path from v o to v with an arrival time at v within the safe interval [t a , t b ]. When a state at the destination node (i.e., the node contained in the state is v d ) is expanded, a path with the minimum arrival time is found and SIPP terminates.
As in SIPP, let a search state s = (v, [t a , t b ]) be a tuple of a node and a safe interval. In SIPP, at each state s, a gvalue is maintained to keep track of the minimum-arrival-time partial solution path from s o to s. In a multi-objective problem, however, there can be multiple partial solution paths with nondominated cost vectors from v o to s, and all of them need to be recorded at s in order to compute a set of cost-unique Paretooptimal solutions. The algorithm also needs to discriminate between those non-dominated partial solutions that arrive at the same state s with different cost vectors and arrival times.
Based on this observation, let l = (s, g, t r ) denote a labelfoot_3 at state s, which identifies a partial solution path from v o to s with an arrival time t r and a cost vector g. For presentation purposes, let g(l), t r (l) and s(l) represent the cost vector, arrival time and state associated with label l respectively. Also, let v(l), t a (l) and t b (l) denote the node (in G), beginning time and ending time of the safe interval of state s(l) respectively. Let frontier set α(s) denote a set of labels at state s, each of which identifies a non-dominated partial solution path from v o to s. Let parent(l) denote the parent label of l, which enables easy reconstruction of a path for any label after the search. In addition, let S denote a set of (solution) labels, each of which identifies a Pareto-optimal solution path from v o to v d .
Scalar values g, h, f used in SIPP are now replaced with the corresponding cost vectors g, h, f in MO-SIPP. Specifically, g is associated with labels and it describes the cost-to-come from v o . Notation h stands for an admissible heuristic 5 and is defined over states. Intuitively, h(s) provides a componentwise underestimate of the cost vector of all non-dominated paths from state s to v d . Finally, f is defined over labels and f (l) := g(l)+ h(s(l)), which underestimates the cost vector of all paths from v o to v d via label l. At any time of the search, let OPEN denote a list of labels, where labels are prioritized in lexicographic order based on their f -vectors.
As shown in Algorithm 1, the pseudo-code can be roughly divided into three parts: initialization (lines 1-5), checking and filtering (lines 7-21) and expansion (lines 22-28).
To initialize, MO-SIPP begins by creating an initial label l o and inserts it into OPEN. The solution set S and all frontier sets α(s) are initialized to empty sets. Then, label l o is added to the frontier set of the initial state α(s o ).
At the beginning of each search iteration (line 6), a lexicographically minimum label l is popped from OPEN for checking and filtering before being expanded:
• (Solution check) If f (l) is dominated by the f -vector of any solution that is already found (identified by a label in S), l is discarded (lines 8-9).
any other labels in the current frontier set of s(l), then l cannot lead to a cost-unique Pareto-optimal solution, and is thus discarded (lines 10-11). After those checks, if v(l) = v d , a new solution is found, and l is then used to filter existing solutions by removing any label l ∈ S if f (l) ≤ f (l ) (lines [13][14][15]. This ensures that the solution set S always contains labels that represent nondominated solution paths. l is then added to S and the current iteration ends (lines [16][17]. If v(l) = v d , l is used to filter the frontier of state s(l) so that the frontier set α(s(l)) contains labels that represent non-dominated partial solution paths from v o to s(l) (lines 18-20). Then, l is added to α(s(l)).
After all the checking and filtering, l is expanded in a similar way as SIPP does, with the only difference that MO-SIPP expands and generates new labels (rather than states as in SIPP). Specifically, to expand a label l, MO-SIPP considers all possible reachable states from state s(l), and then for each reachable state s , the earliest arrival time t r and the cost vector g for reaching s from s(l) are computed. A successor label l = (s , g , t r ) is then generated. Then, for each successor label l , the aforementioned solution check and frontier check are applied to l (line 24) to ensure l is not dominated. Finally, the parent of l is set to be l, and l is added to OPEN for future expansion. The entire search process terminates when OPEN depletes, and all cost-unique Paretooptimal solution paths are found (Sec. VI).
The comparison step in MO-SIPP differs from the one in SIPP. In SIPP, when a new path from v o to a state s is found, the g-value of this new path and the previously stored gvalue at s is compared and the smaller value is kept. In MO-SIPP, multiple non-dominated paths, which are represented by labels, need to be tracked at state s. To properly compare two labels, a new type of dominance between labels is defined as follows.
Algorithm 1 Pseudocode for MO-SIPP 1: lo ← (so, 0, 0) 2: add lo into OPEN 3: S ← ∅ 4: α(s) ← ∅, ∀s 5: add lo into α(so) 6: while OPEN not empty do Main search loop.
l ← pop from OPEN 8:
if f (l ) ≤ f (l), ∃l ∈ S then continue Pruned by label dominance.
12:
for all l ∈ S do Filter existing solutions.
14:
Remove l from S 16:
add l into S 17:
continue Find a new solution.
18:
for all l ∈ α(s(l)) do To filter other labels.
19:
if l l l then 20:
Remove l from α(s(l))
21:
add l to α(s(l))
22:
Lsucc ← GetSuccessors(l)
23:
for all l ∈ Lsucc do Label expansion.
if l l l , ∃l ∈ α(s(l )) or f (l ) ≤ f (l ), ∃l ∈ S then
25:
continue 26:
add l into OPEN 29: return S Definition 2 (Label-dominance): Given two labels l = (s, g, t r ) and l = (s , g , t r ) with s = s (i.e., nodes and safe intervals in both s and s are the same), if the following two conditions both hold: (i) t r ≤ t r , (ii) g + (t r -t r ) c wait ≤ g (in (ii), ≤ means component-wise no larger than), then we say l label-dominates l with notation l l l . (Here, l can be intuitively interpreted as "better than".)
In this label-dominance relationship, if l l l , condition (i) guarantees that label l will have at least the same set of successor labels as l (refer to Lemma 1 in Sec. VI). Condition (ii) ensures that, if there exists a path π from v o to v d via l , then the portion of the path from l to v d can be cut-and-paste to l, and the resulting path π , which connects v o and v d via l, has a cost that is component-wise no larger than the cost of π . Therefore, l can be discarded. Remark. Similar comparison rules to the label-dominance in this work have been developed in GSIPP [4] for a singleobjective case, where a single non-arrival-time objective is minimized. The label-dominance here can be regarded as a generalization of the rule in GSIPP [4] from single-objective to multi-objective.
For readers that are familiar with SIPP, this section explains how MO-SIPP is related to SIPP. When MO-SIPP is applied to solve the aforementioned SIPP problem, MO-SIPP works in the same way as SIPP in the following sense: First, the labeldominance rule becomes a comparison between the arrival times of any two labels, which is the same as in SIPP. Second, the frontier set at each state contains only a single label, whose g-value is the minimum arrival time at s. Maintaining a frontier set at each state is thus equivalent to maintaining a g-value at each state. Third, the solution set S will either be empty or contain a single optimal solution at any time during the search, and the solution cost is the minimum arrival time at v d . Fourth, when the first solution label l is found, all other candidate labels in OPEN must have a cost that is no less than f (l) and are thus filtered in lines 8-9, which leads to the termination of Algorithm 1. As a result, MO-SIPP solves the SIPP problem by finding a collision-free path with the minimum arrival time.
A. Pareto-Optimality Lemma 1: Arriving at a state s at the earliest possible time can generate the maximum number of successors.
Proof 1: Note that the set of reachable states from a label depends only on the arrival time of the label and is not dependent on the cost vector of the label. Therefore, given two labels l = (s, g, t r ) and l = (s, g , t r ) at the same state s = (v, [t a , t b ]) with t r ≤ t r , any reachable state from l (within time interval [t r , t b ]) is also reachable from l (within time interval [t r , t b ]), regardless of the cost vectors g or g . Hence proved. Lemma 2: At any time of the search, if a label at state s is pruned, the path represented by the label cannot be part of a cost-unique Pareto-optimal path.
Proof 2: In MO-SIPP, there are four cases where a generated label l is pruned: (i) l is pruned in the solution check by comparing f -vectors (lines 8-9, line 23); (ii) l is pruned in the frontier check by the label-dominance (lines 10-11, line 23); (iii) l is filtered by a new label l that enters S when comparing their f -vectors (lines 13-15). (iv) l is filtered by label-dominance when a new label l enters α(s(l )) (lines [18][19][20]. For either of those four cases, l cannot lead to a costunique Pareto-optimal solution. Therefore, in MO-SIPP, label expansion always generates successors with the earliest arrival time which guarantees the maximum number of successors (Lemma 1). Those generated successor labels are pruned if they cannot lead to a costunique Pareto-optimal solution (Lemma 2). MO-SIPP terminates when OPEN is empty, which means all labels are expanded or pruned, which guarantees that all cost-unique Pareto-optimal paths are found. The corresponding cost vectors of these cost-unique Pareto-optimal paths form the entire Pareto-optimal front. This property can be summarized with the following theorem:
Theorem 1: MO-SIPP algorithm is able to compute all costunique Pareto-optimal paths connecting v o and v d .
In the formulation of MOPPwDO, the maximum possible time step is bounded by a finite time horizon T . Therefore, there are a finite number of states to be searched and MO-SIPP terminates in finite time if the given problem instance is infeasible (i.e., there does not exist a collision-free path connecting v o and v d within the time horizon T ). When there exists a feasible solution, since the number of search states and the number of paths between any pair of nodes are finite, MO-SIPP finds a solution in finite time.
We select four maps of different sizes from a online data set 6 and generate a four-connected grid-like graph G from each of the maps. This data set also includes 25 test instances for each map, where each instance includes hundreds of start-goal pairs. We use the first start-goal pair as the v o and v d for the robot. We then use A* to plan shortest paths between other start-goal pairs while considering only the static obstacles, and the dynamics obstacles move back-and-forth between their respective starts and goals along these shortest paths. The dynamic obstacles are allowed to overlap with each other during their movement. The number of dynamic obstacles (denoted as #Obst) is a parameter that varies in different tests.
Motivated by urban search and rescue [5], [7], we consider up to three objectives: arrival time, communication robustness and obstacle clearance, each of which is represented as a component of the cost vector of edges in G. To test MO-SIPP, we approximate the continuous measure of communication robustness and obstacle clearance as follows. We randomly generate circles in each of the map (Fig. 3) to represent the possible communication ranges after an urban disaster, where the communication infrastructure may be partially damaged [5], [7]. Each move within the communication range incurs a unit cost, while each move outside the communication range incurs a cost of ten (to penalize). For obstacle clearance, we inflate all the static obstacles by a certain range, which varies in maps of different sizes (see Fig. 6). Each move outside the inflated zone incurs a unit cost, while each move within the inflated zone incurs a cost of ten (to penalize). The cost vector for the wait action c wait is set to a vector of all ones (at any node in the graph).
We implement MO-SIPP and NAMOA* [9] in C++ without multi-threading or compiler optimization. Here, NAMOA* serves as a baseline and is used to search the time-augmented graph G t and is hereafter referred to as NAMOA*-st (-st stands for space-time). The heuristic vectors for both algorithms are computed by running an exhaustive backwards Dijkstra search for each type of the cost over the graph G ignoring all dynamic obstacles. 7 The resulting heuristic vectors are guaranteed to be admissible. All experiments are carried out on a laptop with a CPU i7-11800H 2.30GHz and 16GB RAM.
We begin our tests with two objectives (arrival time and communication robustness). As shown in Fig. 3, in terms of runtime, MO-SIPP runs up to four times faster than NAMOA*st, which demonstrates the efficiency of MO-SIPP. Additionally, when the size of the map increases, the advantage of MO-SIPP over the baseline becomes more obvious. We also report the number of Pareto-optimal solutions and the number of expansions for reference. 8 Additionally, we introduce a metric "state-vertex ratio" to describe the impact of dynamic obstacles on the complexity of the problem, which is defined as the ratio of the number of states being explored by MO-SIPP over the number of vertices being explored by MO-SIPP. A state (or vertex) is explored by MO-SIPP if at least one label is generated at that state (or vertex).
We then test MO-SIPP with the same two objectives as the previous section and change the number of obstacles. We select two maps, random 32x32 and Boston 256x256. In this experiment, we let the obstacles disappear after their arrival at the destinations to make the instances feasible. Otherwise, when #Obst is large, for some of the instances, there is no feasible trajectory for the robot to move from v o to v d .
As shown in Fig. 4, MO-SIPP runs faster than NAMOA*st in all settings. In the Boston 256x256 (large) map, MO-SIPP runs up to an order of magnitude faster on average than 8 Each expansion in MO-SIPP is in general more time-consuming than NAMOA*-st since MO-SIPP needs to lookup safe-intervals at adjacent nodes to find reachable states, while the expansion in NAMOA*-st only needs to consider the next time step and adjacent nodes. NAMOA*-st for any considered #Obst. For the random 32x32 (small) map, the online data set has at most 409 start-goal pairs, and we test for up to 400 obstacles in this map. As shown in Fig. 4, the advantage of MO-SIPP over NAMOA*st is less obvious in this smaller map. Additionally, after #Obst increases above a certain threshold (e.g. 200), the runtime of both algorithms start to decrease. To find the reason, we simulate some of the instances (Fig. 5). The large number of Fig. 5: Visualization of an instance with different #Obst (black dots), and the percentage of free vertices occupied by the dynamic obstacles is also shown for each map. As a complement to Fig. 4, when #Obst increases above a certain threshold, the large number of obstacles reduces the number of successors to be generated by both planners during the search and thus reduces the runtime.
obstacles reduces the number of successors to be generated by both planners during the search, and thus reduces the runtime, which is also verified by the average number of expansions as shown in the bar plots in Fig. 4.
Finally, we test MO-SIPP with three objectives. As shown in Fig. 6, MO-SIPP runs up to five times faster than NAMOA*st. Additionally, by comparing the number of Pareto-optimal solutions, we find that the Berlin and Boston maps with three objectives are quite challenging as there are many Paretooptimal solutions to be found. The difficulty of those instances can also be observed from the number of expansions required by both planners. In our tests, we set a runtime limit of ten minutes and NAMOA*-st times out for 6 and 8 instances in the Berlin and Boston maps respectively, which are removed from the data in Fig. 6.
With all these experiments, we can summarize our observations as follows. First, MO-SIPP (ours) runs up to an order of magnitude faster than NAMOA*-st (baseline). Second, the advantage of MO-SIPP becomes more obvious when the size of the map is large. Third, increasing the number of dynamic obstacles in general slows down MO-SIPP. But after a certain threshold, more obstacles makes MO-SIPP run faster. Fourth, a larger number of objectives leads to more Pareto-optimal solutions, which slows down MO-SIPP.
This article considers the problem of Multi-Objective Path Planning with Dynamic Obstacles (MOPPwDO). We develop an algorithm called MO-SIPP by leveraging both the notion of safe intervals from SIPP, the dominance principle from multiobjective optimization literature and search techniques from multi-objective A* algorithms. We show that MO-SIPP finds the entire Pareto-optimal front and verify the performance of MO-SIPP with extensive tests. Our numerical results show that MO-SIPP runs up to an order of magnitude faster than the baseline and is particularly advantageous in large maps.
There are several possible directions for future work. MO-SIPP does not consider obstacle clearance with respect to dynamic obstacles or communication range centered on moving agents. One can also extend MO-SIPP to address dynamic obstacles along unknown or uncertain trajectories. To further expedite MO-SIPP, one can consider leveraging other multiobjective planning techniques (e.g. [17]) to handle the case when there are many Pareto-optimal solutions. In addition, MO-SIPP can also be leveraged as a building block to solve multi-objective multi-agent planning problems [15], [16]. Finally, one can consider leveraging the recent notion of rulebooks [1] from autonomous driving to smartly select a Paretooptimal solution that respects the most social conventions for execution.
As discussed before, adding the time dimension to the given graph and using MOA* on the augmented graph.
https://github.com/wonderren/public mosipp
To represent an edge (u 1 , u 2 ) ∈ E whose transition time takes multiple time steps, note that the edge can be "broke up" into a sequence of nodes {u 1 , u k 1 , u k 2 , . . . , u k ℓ , u 2 } so that the transition between any two subsequent nodes takes unit time, and those intermediate nodes {u k 1 , u k 2 , . . . , u k ℓ } can be added to the graph G.
To identify a partial solution path, different names such as nodes[23], states[15],[18] and labels[11],[20], have been used in the multi-objective path planning literature. This work uses "labels" to identify partial solution paths.
The heuristic is not required to be consistent in this work.
https://movingai.com/benchmarks/mapf/index.html
Using Dijkstra search to obtain heuristic vectors are common for MOA*like algorithms[17],[23] due to its small runtime in comparison with the MOA* search. The numerical results about the runtime in this work do not include the time to compute the heuristic vectors.