Multi-Task Option Learning and Discovery for Stochastic Path Planning
Authors: Naman Shah
Siddharth Srivastava
Venue: Submitted to ICLR 2023 (2023)
Keywords: Option discovery
learning abstractions
planning and learning
reinforcement learning
RL for robotics
hierarchical methods
stochastic path planning

Abstract: This paper addresses the problem of reliably and efficiently solving broad classes of long-horizon stochastic path planning problems. Starting with a vanilla RL formulation with a stochastic dynamics simulator and an occupancy matrix of the environment, our approach computes useful options with policies as well as high-level paths that compose the discovered options. 
Our main contributions are (1) data-driven methods for creating abstract states that serve as endpoints for helpful options, (2) methods for computing option policies using auto-generated option guides in the form of dense pseudo-reward functions, and (3) an overarching algorithm for composing the computed options. We show that this approach yields strong guarantees of executability and solvability: under fairly general conditions, the computed option guides lead to composable option policies and consequently ensure downward refinability. Empirical evaluation on a range of robots, environments, and tasks shows that this approach effectively transfers knowledge across related tasks and that it outperforms existing approaches by a significant margin.

MULTI-TASK OPTION LEARNING AND DISCOVERY FOR STOCHASTIC PATH PLANNING
Anonymous authors Paper under double-bling review
ABSTRACT
This paper addresses the problem of reliably and efficiently solving broad classes of long-horizon stochastic path planning problems. Starting with a vanilla RI formulation with stochastic dynamics simulator and an occupancy matrix of the environment, approach computes useful options with policies well high-level paths that compose the discovered options.
Our main contributions are (1) data-driven methods for creating abstract states that serve as end points for helpful options, (2) methods for computing option policies using auto-generated option guides in the form of dense pseudo-reward functions, and (3) an overarching algorithm for composing the computed options. We show that this approach yields strong guarantees of executability and solvability: under fairly general conditions, the computed option guides lead to composable option policies and consequently ensure downward refinability. Empirical evaluation on a range of robots, environments, and tasks shows that this approach effectively transfers knowledge across related tasks and that outperforms existing approaches by significant margin.
INTRODUCTION
Autonomous robots must compute long-horizon motion plans (or path plans) to accomplish their tasks. Robots use controllers to execute these motion plans by reaching each point in the motion plan. However, the physical dynamics can be noisy and controllers are not always able to achieve precise trajectory targets. This prevents robots from deterministically reaching a goal while executing the computed motion plan and increases the complexity of the motion planning problem. Several approaches (Schaul et al. 2015 Pong et al. 2018) have used reinforcement learning (RL) to solve multi-goal stochastic path planning problems by learning goal-conditioned reactive policies. However, these approaches work only for short-horizon problems (Eysenbach et al., 2019). On the other hand, multiple approaches have been designed for handling stochasticity in motion planning (Alterovitz et al. 2007, Sun et al.] (016),, but they require discrete actions for the robot. This paper addresses the following question: Can develop effective approaches that can efficiently compute plans for continuous stochastic path planning problems? In this paper, we show that we can develop such an approach by learning abstract states and then learning options that serve as actions between these abstract states.
Abstractions play an important role in long-horizon planning. Temporally abstracted high-level actions reduce the horizon of the problem in order to reduce the complexity of the overall decision- making problem. E.g.. task of reaching location in building can be solved using abstract actions such as "go from room A to corridor A", "reach elevator from corridor A", etc., if one can automatically identify these regions of saliency. Each of these actions action. Not only do these actions reduce the complexity of the problem, but they also allow the transfer of knowledge across multiple tasks. E.g. if we learn how to reach room B from room for a task, we can the same solution when this abstract action is required solve some other task.
temporally abstracted
Reinforcement learning allows learning policies that account for the stochasticity the environment. Recent work (Lyu et al., 2019. Yang al. 2018 Kokel et al. 202I) has shown that combining RL with abstractions and symbolic planning has enabled robots to solve long-horizon problems that require complex reasoning. However, these approaches require hand-coded abstractions. In this paper,

---

we show that the abstractions automatically learned (Shah & Srivastava, 2022) can be efficiently combined with deep reinforcement learning approaches.
The main contributions to this paper are: (1) A formal foundation for constructing a library of two different types of options that are task -nseeendeenndnt and transferable, (2) A novel approach for auto-genesn geooeeeetnaiing dense pseudo-reward function in the form of option guides that can be used to learn policies for synthesized options, and (3) An overall hierarchical algorithm approach that uses combines these automatically synthesized abstract actions with reinforcement learning and uses them for multi-task long-horizon continuous stochastic path planning problems. We also show that these options are composable and can be used as abstract actions with high-level search algorithms.
Our formal approach provides theoretical guarantees about the composability of the options and their exccutability using an option guide. We present an extensive evaluation of our approach using two separates sets of automatically synthesized options in a total of 14 settings to answer three critical questions: (1) Does this approach learn useful high-level planning representations? (2) Do these learned representations support transferring learning to new tasks?
The rest of the paper is organized as follows: Sec. 2 some of the existing approaches that are closely related to our approach; Sec. 3 introduces a few existing ideas used by our approach; See. presents our algorithm; Sec. presents an extensive empirical evaluation of our approach.
2 RELATED WORK
To the best of our knowledge, this is the first approach that uses a data-driven approach for synthesizing transferable and composable options and leverages these options with a hierarchical algorithm to compute solutions for stochastic path planning problems It builds upon the concepts of abstraction, stochastic motion planning, option discovery, and hierarchical reinforcement learning and combines reinforcement learning with planning. Here, we discuss related work from each of these areas.
Motion planning is a well researchhd area. Numerous approaches( Kavraki et al. 1996 La Valle
1998. Kuftner& & Valle 2000 Pivtoraiko al., 2009) [Saxena et 2022) have been developed for motion planning in deterministic environments. Kavraki et al. (199);; La Vall (9988 Kutfner
Valle (2000) develop sampling-based techniques that randomly sample configurs infiguraaiinn in the environment and connect them for computing motion plan from the initial and goal configurations.
Holte et al. (1996): Pivtoraiko et al. (2009); Saxena et al. (2022) discretize the configuration space
and use search techniques such as A search to compute motion plans in the discrete space.
Multiple approaches (Du et al.
2010: Kurniawati et al. 2012 Vitus et al.. 2012 Berg et al., 2017
Hibbard et al. 2022) have been developed for performing motion planning with stochastic dynamics.
Alterovitz et al. (207)) build weighted graph called stochastic motion roadmap (SMR) inspired from the probabilistic roadmaps (PRM) (Kavraki et al. 1996) where the weights capture the probability of the robot making the corresponding transition. Sun et al. (016)) use linear quadratic regulator -- a linear controller that does not explicitly avoid collisions along with value iteration to compute trajectory that maximizes the expected reward. However, these approaches require an analytical model of the transition probability of the robot's dynamics. Tamar et al. (2016) develop fully differentiable neural module that approximates the value iteration and can be used for computing solutions for stochastic path planning problems. However, these approaches (Alterovitz al., 2007 Sun al. 2016: Tamar et al., 2016) require discretized actions. Du et al. (2010): Van Den Berg et al. (2012 2)
formulate a stochastic motion planning problem as POMDP capture the uncertainty in robot sensing and movements. Multiple approaches (Jurgenson & Tamar 2019 Eysenbach et al., 2019
Jurgenson al., 2020) design end-to-end reinforcement learning approaches for solving stochastic motion planning problems. These approaches only learn policies to solve one path planning problem at a time and do not transfer knowledge across multiple problems. contrast, our approach does not require discrete actions and learn options that are transferrable to different problems.
Several approaches have considered the problem of learning task-specific subgoals. Kulkarni et al. (2016); [acon et al. (2017); Nachum et al. 20188 2019): Czechowski et al. (2021) use intrinsic reward functions to learn a two-level hierarchical policy. The high-level policy predicts a subgoal that the lew-level goal-conditione' policy should achieve. The high-level and low-level policies
are then trained simultancously using simulations in the environment. Paul et al. (2019) combine imitation learning with reinforcement learning for identifying subgoals from expert trajectories and
2

---

bootstrap reinforcement learning. Levy et al. (2019) learn multi-level policy where each level learns subgoals for the policy at the lower level using Hindsight Experience Replay (HER) (Andycchoiccz et 2017) for control problems rather than hong-horizon motion planning problems in deterministic settings. Kim et al. (202)) randomly sample subgoals in the environment and use a path planning algorithm to select the closest subgoal and learn a policy that achieves this subgoal.
Numerous approaches (Stolle & Precup, 2002
Simsek et al.
2005
Brunskill & Li
2014 Kurutach
et al.
2018 Eysenbach et al.) 2019; Bagaria & Konidaris
2020: Bagaria al. 2021 perform
hierarchical learning by identifying task-specific options through experience collected in the test enviromment and then use these options (Sutton et al.. 1999) along with low-level primitive actions. Stolle & Precup (2002); Siimşe et al. (2005) lay foundation for discovering options in discrete settings. They collect trajectories in the environment and use them to identify high-frequency states in the environment. These states are used as termination sets of the options and initiation sets are derived by selecting states that lead to these nighfrequency states. Once options are identified, they use Q-learning to learn policies for these options independently to formulate Semi-MDPs (Sutton et al. 1999). Bagaria & Konidaris (2020) learn options in reverse fashion. They compute trajectories in the environment that reaches the goal state. In these trajectories, they use the last K points define an option. They use these points to define the initiation set of the option and the goal state is used as the termination set. They continue to partition rest of collected trajectories similarly and generate fixed number (a hyperparameter) of options.
Approaches for combining symbolic planning with reinforcement learning (Silver & Ciosek 2012
Yang et al., 2018: Jinnai et al. 2019, Lyu et al., 2019; Kokel et al. (02T)) use pre-defined abstract models to combine symbolic planning with reinforcement learning. In contrast, our approach learns such options (including initiation and termination sets) as well as their policies and uses them to compute solutions for stochastic path planning problems with continuous state and action spaces. Now, we discuss some of the existing concepts required to understand our approach.
3 BACKGROUND
Motion planning Let X' Xiree Kats be the configuration space of a robot R and let O be the set of obstacles in a given environment. Given a collision function f X' -> {0, 1]. Xiee represents the set of configurations that are not in collision with any obstacle e O such that f(x) = 0 and Xots represents the set of configurations in collision such that f(z) = 1. Let x; E Xiree be the initial configuration of the robot and xg Xiter be the goal configuration of the robot. The motion planning problem can be defined as:
Definition 1. A motion planning problem M is defined as 4-tuple (X, f. f,, where X = X/ree J Xabz is the configuration space, f is the collision function, I, is an initial configuration, and F. is goal configuration.
solution to a motion planning problem motion plan T. A motion plan a sequence of configurations (zo.... ..e........ zn, such that zo = 24. In Ig. and Vr E T. f(x) = O. Robots use controller that accepts sequenced configurations from the motion plan and generates controls that take the robot from one configuration to the next configuration. In practice, these environment dynamics are noisy, which introduces stochasticity in the overall motion planning problem. This stochasticity can be handled by computing motion policy X + X that takes the current configuration of the robot and generates the next waypoint for the robot.
Markoy decision process In this work, we define the stochastic path planning problem as a continuous stochastic shortest path (SSP) problem (Bertsekas & Tsitsiklis 1991). A continuous stochastic shortest path problem is defined as a 5-tuple A,",,,,,, so, G) where X' is continuous state space (configuration space of the robot), A is set of continuous actions, T A'x is transition function, C. X > IR is cost function, 8p is an initial state, and G S S is set of goal states. Discount factor 7 is set to 1 for this work. A solution to an SSP is a policy π : X + A that maps states to actions that take the robot to the goal states and minimizes the cumulative cost. Dynamic programming methods such as value iteration (VI) or policy iteration (PI) can be used to compute such policies when every component of the MDP is known. When or more SSP components are unknown various reinforcement learning (RL) approaches (Watkins) 1989 Mnih
[0. 1
al. 2015 Lillierp al. 2016 Haarnoja et al. 2018) can be used to learn policies.
3

---

Options framework Options framework (Sutton et al. 1999) models options temporal abstrac- tion over primitive actions in an MDP. Let S be the state-space of an MDP. An option o is defined as 3- 3-tuple (Io: Boy no). I, S S defines the initiation set of an option o. An option can be applied in state s iff 8 E I.- So is the termination set of an option o. Execution of an option o terminates when the agent reaches state & E 13.. To S A defines policy for the option [Sutton et al. (1999) define Semi-Markov Decision Process (SMDP) by adding available options to the set of primitive actions available in the MDP. Solution for an SMDP is a policy π :S A where AU O and O is set of options.
Automated synthesis of abstractions Shah & Srivastava (022) use region-based Voronoi di- agrams (RBVDs) to define abstractions for motion planning problems. To construct effective abstractions, they use critical regions (Molina et al. 2020) to construct the RBVD, Intuitively, critical regions are defined as regions that have high density of solutions for a given class problems but low sampling probability under uniform sampling distribution. (Shah & Srivastava (2022) regions to define RBVDs as follows:
use critical
Definition 2. Given a configuration space X, let df define minimum distance between a configuration E X and a region e S X. Given a set of regions & and a robot R, region-based Voronoi diagram T is partitioning of X such that for every Voronoi cell 1/. E V there exists region de E & such that forall x E i and forall 6j + oú. dx 0i) < dx 6j) and each 1/s is connected.
In this framework, abstract states are defined using a bijective function E V + S that maps each Voronoi cell to an abstract state. The abstraction function a: X' - S is defined such that (xx and only if there exists a Voronoi cell da such that x E 1b and {( = 8. A configuration x E X is said be in the high-level abstract state E S (denoted by x E s) if (x)) s. In this work, we use RB VDs along with critical regions to construct abstractions and synthesize options.
4
OUR APPROACH
Algorithm 1: Stochastic Hierarchical Abstraction- guided Robot Planner (SHARP)
Alg. D outlines approach stochastic hierarchical abstraction-guided robot planner (SHARP) - for computing policy for the given stochastic path planning problem. Our approach requires robot simulator to compute path plans. It takes the occupancy matrix of the environment along with the initial and goal configuration of the robot as the input and produces policy com- posed of options as the output.
Input: Training environments Eusin. e-space X,, initial configuration xi, goal configuration Fg
Output: A policy II composed of options θ <- get__eeeteee cwwpecccttreeeeee regions_predieenee if θ is not trained then train using Emii
if abstraction is not constructed then + Beaffet__ritica__eiooneeeee
Learning the critical regions The first step in our approach is to identify critical regions in the given environment. We use a deep neural network identify these critical regions. We train (lines 1-3) this neural network with the kinematic model of the robot and set of train- ing environments Eusain that do not include the test environments. We discuss this in detail in Sec. 4.1 Once the network is trained, the same network is used to identify critical regions (line 5) in all test environments for the same robot. Synthesizing option endpoints Alg. [ uuee these identified critical regions to construct RBVD (line 6) and generate set of abstract states (line 7). We then use this RBVD to con- struct collection of options and synthesize op- tion endpoints for the given environment (line 7). Sec. 4.2 explains this step in detail. These option are synthesized only once per the robot and the environment. They are reused for each subsequent pair of initial and goal pairs. We refer to option endpoints as options for brevity.
construct_RBVDIee. b);
8t, 8g <- abbsttracttssatss(r..r....>
p A* search(O,ss..9))
10 empty_
11 To + lelar__pllccccce In,
12 ILadd(rr))
foreach E
14
if o o.poliicy does not exist then
15
G - wwwpooommmpppppeeeec cecttee_pptto_nnteee Opption_uiid(To.BB.> train o.policy:
16
adjust the cost of the option o;
18
I.add(o.policy);
19 tn+1 +- learn_ (attm__nlic((@,,.....
20
a.dd(
21
return II;
Options as abstract actions Let be the set of synthesized options. Our approach uses these options as high-level abstract actions. It considers the initiation sets of these options as preconditions
4

---

for the abstract actions and the termination sets as their effects. We identify the abstract initial and goal state for the robot's initial and goal configuration (line 8) and use the A search to compute a sequence of identified abstract actions that takes the robot from the initial abstract state to the goal abstract state (line 9). We use the Euclidean distance between the termination set of the corresponding option and the goal configuration as the heuristic for the A search. The A search also requires the costs for the options which are initially unknown. Therefore, we use the Euclidean distance between the initiation and termination sets of an option as an approximation to its cost.
Computing policies for options Let p- (01,...,,o)) on) be the sequence of options that takes the robot from its initial abstract state so to its goal abstract state 8g. Alg. thhnn computes policies for each of the options in this sequence of options. It first starts by computing a policy mo that takes the robot from its initial configuration r; to some point in the initiation set of the first option or (line 11). Alg. then starts computing the policy for every option in p. First, we check a policy for an option is already computed from the previous call of Alg. oo not (line 14). If is already computed, use the same policy. Otherwise, our approach computes an option guide for the given option using its endpoints, and it then uses this option guide to compute policy for the option (lines 15-16). Sec. 4.3 presents this in details. Lastly, Alg. ! computes policy that takes the robot from the termination set of the last option in p to the goal configuration 2g (line 19).
Updating the option costs To efficiently transfer the learned option policies, our approach needs to update the option costs that A search uses to compute the sequence of options. We update this cost (line 17) by collecting rollouts of the learned policy and using the average number of steps from the initiation set to the termination set an approximation of the cost of the option. Now, we explain each step our approach in detail.
4.1 LEARNING CRITICAL REGIONS
Our approach first needs to identify critical regions (Sec. 3 to synthesize options in the given environment. Recall that critical regions are regions in the environment that have high density of solutions for the given class of problems but at the same time, they are hard to sample under uniform distribution over the configuration space. The training data is generated by solving randomly sampled motion planning problems. Input into the network is an occupancy matrix of the environment that represents the free space and obstacles in the given environment. Labels represent critical regions in the given environment.
These critical region predictors are environment independent and they are also generalizable across robots to a large extent. Furthermore, the approach presented here directly used the open-source critical regions predictors made available by (Shah & Srivastava (2022). These predictors are envi- ronment independent and need to be trained only once per kinematic characteristics of robot. E.g., the non- holonomioc robots used to evaluate our approach (details in Sec. 55) are different from those used by Shah & Srivastava (2022) but used the critical regions predictor developed by them for rectangular holonomic robot.
Shah & Srivastava (2022) use 20 training environments (Eurin) to generate the training data. For each training environment Grain E Erainn they randomly sample 100 goal configurations. [Shah & Srivastava 2022) randomly sample 50 initial configurations for each goal configuration and compute motion plans for them using an off-the-shelf motion planner and a kinematic model of the robot. They use UNet (Ronneberger et al., 2013) with Tanh activation function for intermediate layers and Sigmoid activation for the last layer. They use the weighted logarithmic loss as the loss function. Lastly, they use ADAM optimizer (Kingma & Ba 2014) with learning rate 10-4 to minimize the loss function for 50, 000 epochs.
4.2 SYNTHESIZING OPTION ENDPOINTS
The central idea of this paper is to synthesize transferable options using the set of critical regions and the RBVD V. Our approach uses these critical regions and RBVD for identifying option endpoints, i.c., initiation and tenmination sets. In this work. we define between centroids of two critical regions- centroid options (O.) and 2. Options between interfaces of two pairs of abstract states interface options (O:). Now we define each of these options.
types of options: 1. Options
5

---

Centroid options Centroid options are defined using centroids of two neighboring critical regions. Intuitively, these options define abstract actions that transition between a pair of critical regions. Formally, let & be the set of critical regions and v/ be the RBVD constructed using the critical regions 6. Let So be a set of abstract states defined using the RBVD VV.
Definition 3. Let 8; E be an abstract state in the RBVD with the corresponding critical region ds E &. Let d be the Euclidean distance measure and let I. define threshold distance. Let be the centroid of the critical region Tt. A centroid region of the critical region Ti with the centroid o₁ is defined as a set of configuration points {a|œ E s; A d(z,ci) < <t}.
We use this definition to define the endpoints for the centroid options as follows:
Definition 4. Let 8,, S, E be a pair of neighboring states in an RBVD W constructed using the set of critical regions 4. Let di, 6j E & be the critical regions for the abstract states s, and s; and let ca and 9j be their centroids regions. The endpoints for a centroid option are defined as a pair (Isj, Biz) such that Iıj = c; and 3ij Cy.
Interface options Interface options are defined using intersections of high-level states. Intuitively, these options define high-level temporally abstracted actions between intersections of pairs of abstract states and take the robot across the high-level states. To construct interface options, we first need to identify interface regions between a pair of neighboring abstract states. Let S be set of abstract states defined using the RBVD V. We define interface region as follows:
Definition 5. Let st, 3j E S be pair of neighboring states and é; and 6j be their corresponding critical regions. Let d' Φ) define the minimum euclidean distance between configuration x E X and some point in region & C X. Let p be configuration such that d' d' 9.) = d' (p. 0z) that is. p is on the border of the Voronoi cells that define st and 8j. Given the Euclidean distance measure d and a threshold distance an interface region for a pair of neighboring states (81,8) is defined as a set {z[(x= E S, V 8z) A d(x,p) p) < <t}.
We use this definition of interface regions to define endpoints for the interface options as follows: Definition 6. Let 8i, 8j, 8k E Sy be abstract states in the RBVD V such that 8; and 83 are neighbors and sj and sy are neighbors. Let Φi; and 6ikk be the interface regions for pairs of high-level states (st, 83) and (s)) The endpoints for an interface option defined as a pair (Josgu Posgu such that To.gx = dig and Boug
sk).
We construct a collection of options for the given environment using these definitions for endpoints of centroid and interface options. Let V S x S -> {0. 1} define neighborhood function such that V(s,, 8,) = iff s; 83 E S are neighbors. We define the set of centroid options as O2 {oss VVs, 8, V(s., 5;) = 1} with endpoints computed as in Def. E. Similarly, we define the set of
interface options as O. = Dusjk|Vs, 8j, 5k (ss,,,)) = 1 A V55 8k) = 1} with endpoints computed as in Def.
Our approach uses this collection of options to compute composed policy. Let $1, 8n be a set of distinct adja- cent states such that Vss 81+1) 1. Let O {o on be the set of centroid or interface options for these sequence of adjacent states. The com- posed policy 11 is finite state au- tomaton as shown in Fig. D Recall that for a sequence of options 01,-..,0z. On. Alg. computes To and T as special cases. For a controller state q; [Tx) = (x(x)) where represents the policy for option o, E O. The controller makes a transition qi + 9i+1 when the robot reaches a configuration I E Io.. Now, we prove the existence of a composed policy for approach. Recall that for configuration space X' and a set of critical regions Φ, the RBVD Ti induces a set of abstract state and an abstraction function a.
x 3a,
x Dep
X J.
Xo
X
du
q.
qn
Gass
Gasa
Figure I: A policy composed of collection of options 01,- On for a sequenee of distinct adjacent abstract states 81, Sn-
Theorem 4.1. Let I1 and F, be the initial and goal configurations of the robot such that $1 = a(11) and sn a(xn). Let V : S x S > (0. 1} be the neighborhood function as defined above. Let O be the set of centroid or interface options. If there exists a sequence of distinct abstract states si..... Sn such that V(si, 8i+1) = then there exists a composed policy II such that the resultant configuration after the termination of every option in would be the goal configuration En--
6

---

Proof. (Sketch) The proof directly derives from the definition of the endpoints for the centroid and interface options. Given a sequence of adjacent abstract states $1,.... Sn, Def. and ensures a sequence of options ........ On such that 3 I++1- This implies that option once the previous option is terminated. Given this sequence of options o1,..., On. according to the definition of the compound policy, there exists compound policy IT such that for every pair
be executed resulting configuration would be the goal configuration.
of options o,, Oj E 11, Io, = Bo,- Thus, we can say that if every option in II terminates, then the
4.3 SYNTHESIZING AND USING OPTION GUIDES
Once we identify the endpoints- -- initiation and termination sets - for the option, we use these sets to compute option guides for these options. We use option guides to formulate reward function that is used to train policies for them. The option guides contain two components: a guide path and pseudo reward function. We formally define an option guide as follows:
Definition 7. Given an option o E O with option endpoints (I,, Rt), an option guide Go, is defined as 4-tuple (I,, Br, Gi Ra) where Ij and 3r are endpoints of the option os GJ is the guide path, and Rd is the pseudo reward function.
We now define both components of the option guide. A guide path is a motion plan from the initiation set to the termination set of an option. Recall that a is an abstraction function defined using the RBVD Vr We defune guide path as follows:
Definition 8. Let X be the configuration space of the robot R. Let d. be the Euclidean distance measure. Given an option og with endpoints (I,33). let cı, and c3, define centroids for the initiation and termination sets respectively. Given a threshold distance and the Euclidean distance measure d, a guide path Gi for the option o, is a sequence of points [PI...., .p]] in the configurations space X such that p1 CL.- Pn cB:, for each pair of consecutive points ps. Pj 9r, d(pe.p)) <t,, t, and for every point P. E Gs. Ps E aII)) or E a(3)).
Here, we abuse the notation and use the abstraction function with set of low-level configurations rather than single configuration. Intuitively, (Z,) = {a(>)]Vr E Z.J. can be similarly computed for Sr. We generate this guide path using campling-based motion planner HARP (Shah & Srivastava 2022) and the kinematic model of the robot.
The guide path is used to define pseudo reward function R for the option. It is dense reward function that provides a reward to the robot according to the distance the robot from the nearest point in the guide path and the distance from the last point of the guide path. For option o, define the dense pseudo reward function R₂ : X -> IR as follows:
Definition 9. Let o, be an option with endpoints (I,, B,) and let G. = [p.......... Pnl be the guide path. Given a configuration x E X, let n(x) = ps define the closest point the guide path. Let d be the Euclidean distance measure. The pseudo reward function R2 R2(x)) is defined as:
i E B if E S/(a(Z)) otherwise
Rx(z)
Tp (d(c, + d(n(x), p.))
Here 7t is a large positive reward and rp is a large negative reward that can be tuned as hyperparam- wish automatically generate dense pseudo-reward function based on the
eters. Intuitively, information available form the environment. Thus rather than providing only sparse reward function (e.g. "+1 when you reach the termination set of the option"), that captures this condition (first case), a penalty for straying away from the source and target abstract states (second case), and reward for covering more of the option guide (third case).
develop the pseudo reward function
Given an option o; with endpoints (I,, 3&)) and an option guide G; = (I,, Be, 9i, Rt), our approach can use arbitrary reinforcement learning algorithm to learn the policy for the option. For our empirical evaluation (Sec. 5) we use Soft Actor Critic (Haarnoja et al. 2018).
5 EMPIRICAL EVALUATION
We conduct an extensive evaluation of our approach in a total of four different environments with two different robots. All experiments were conducted on system running Ubuntu 18.04 with AMD
7

---

SHARP Centroids
SHARP Interfaces
BRT Replan
SAC
Time for Computing a Policy (in seconds)
H Env
H Env B
Env
Env A
L- Env
C
Timeout
1500
1000
500
0
H Env
H- Env
H Env
L- --EnVE
L- Env
L-Env 6
Timeout
8K
P1
P2
P4
P4
P1 P2
P4
PS Problem
P3 P4
P1 P2
P1 P2
#
Figure 2: The figure shows the time taken by our approach and baselines to compute path plans in the test environment. Results for an additional environment is in the Appendix B The x-axis shows the problem instance and the y-axis shows the time in seconds. The reported time for our approach includes time predict critical regions, construct abstractions, and learn policies for all the options. Each subsequent problem instance uses trained policies for options from the previous problems there exists one. Timeout was set to 2400 seconds. The numbers are averaged over independent trails. The transparent bars for SAC show that training was stopped as it reached the timeout.
Ryzen Threadripper 3960X 24-core processor and two NVidia 3080 GPUs. We implement our approach using PyBullet (Coumans Bail 2016) robotics simulator. PyBullet does not explicitly model stochasticity in the movement of the robot. Therefore, we use random perturbations in the actions to introduce stochasticity in the environment while training and use default controllers to evaluate the learned policies.
We implement our approach using PyTorch and Stable Baselines. use a 2- layered neural network with each layer containing 256 neurons in every layer to learn policy for each option. The input the network is the current configuration of the robot and a vector to the nearest point on the guide path for the current option. The network outputs the next point for the robot to reach. We use r, 1000 and rp = - 100 for the pseudo reward function with maximum learning steps set to 150k to learn policy for each option. We evaluate model for 20 episode every 10k steps and stop the training if we achieve an average reward of 500. Our code and data are available in the supplementary material.
Evaluating our approach We evaluate our approach using a total of environments. They are inspired by indoor household and office environments. Appendix A shows our test environments. Dimensions of the first four environments (App. A. are 15m x 15m. The rest of the environments (App. A.2 are of the size 75m 75m. These environments were not included in the set of training environments used to train the network that identifies critical regions. We generate 5 motion planning tasks (P1-P5) for each environment evaluate our approach. We use two non-holonomic robots to evaluate our approach in these four environments: the ClearPath Husky robot (H) and the AgileX Limo (L). The Husky a 4-wheeled differential drive robot that can move one direction and rotate in place. The Limo is also 4-wheeled robot that can move in one direction and has a steering.
We considered set of recent approaches (Kulkarni et al. 2016 Lillicrap et al.. 2016 Levy et al. 2019: BBgaria & Konidaris, 2020) before selecting two approaches to evaluate against our approach. First, we compare our approach against vanilla soft actor-critic (SAC) (Haarnoja et al. 2018). SAC an off-policy deep reinforcement learning approach and learns single policy for taking the robot from its initial configuration to the goal configuration. We use the same network architecture as ours for the SAC neural network. We the tenminal reward of +1000 and a step reward of -1. We also evaluate our approach against a sampling- based motion planner RRT (La Valle 1998) with replanning. We compute path plan with RRT and execute it. If the robot does not reach the goal after executing the entire path plan, then we compute a new path plan from the configuration where the robot ended. We continue this loop until either the robot reaches the goal configuration or we reach the timeout.
Analysis of the results We thoroughly evaluated approach to answer three critical questions: (1) Does this approach learn useful high-level planning representations? (2) Do these learned representations support transferring learning new tasks?
8

---

SHARP Centroids
SHARP Interfaces
ART Replan
SAC
H Env A
H Env
Env
L- Env
L Env
E-Env C
1.0
0.8
0.4
success rate
0.2
8.0
H- Env
H- Env F
H- Env
L- Env
L-Env
E-Env G
0.88
0.6
0.4
1
P1
P3
P1
PS P2
P4
P5
P1
P2
P4
P1
P3 P4
P1
P3
P5
Problem
#
Figure 3: The figure shows the success rate of our approach and baselines in the test environments. Results for an additional environment is in the Appendix B The x-axis shows the problem instance and the y-axis shows the fraction of successful exccutions of the model out of 20 test executions. We used the final policy for approach and SAC. RRT computed a new plan for cach exccution with timcout set 2400 seconds. The numbers are averaged over 5 independent trails.
Fig. 2 shows the time taken by our approach for learning policies compared to the baselines SAC and RRT. Fig. X shows that our approach was able to learn policies significantly faster than the baselines. In most cases, our approach was able to compute solutions in half of the time taken by the baselines. Vanilla SAC was not able reach the threshold average reward of +500 in any environment before the timeout of 2400 seconds. This shows that our approach was able to learn useful high-level planning representations that improve the efficiency of the overall stochastic motion planning.
Fig. 3 shows the success rate for our approach and the baselines. Our approach achieves the goal significantly higher number of times compared to replanning- -base deterministic RRT. Our approach was able to consistently reach the goal configuration more than 80% of times. On the other hand, RRT was able to reach goal only 50% of times the given timeout of 2400 seconds. For larger environments (E-F), SAC was not able to solve single problem. We also conducted a thorough analysis of options being used across problems P1-P5 in each environment. Appendix shows the fraction of options reused by approach across P1-P5. These rates combined with the success rates show that our approaches is able to successfully transfer learned options across new tasks.
6 CONCLUSION
In this paper, we presented the first approach that uses data-driven process automatically identify transferable options. Our approach synthesizes two different types of options: centroid options and interface options. uses these options with our hierarchical algorithm for solving stochastic path planning problems. We also provide way to automatically generate pseudo reward functions for synthesized options to efficiently learn their policies. We show that learned options can transferred to different problems and used to solve new problems. Our formal framework also provides guarantees on the compossibility of the generated options.
Our empirical evaluation large variety of problem settings shows that approach significantly outperforms other approaches. Through our empirical evaluation, we show that by combining reinforcement learning with abstractions and high-level planning we can improve its efficiency and compute solutions faster. We also show that using reinforcement learning to solve path planning problems stochastic environments yields robust plans that perform better than deterministic plans computed using replanning- basend motion planners.
REFERENCES
Ron Alterovitz, Thierry Siméon, and Ken Goldberg. The stochastic motion roadmap: A sampling framework for planning with markov motion uncertainty. In Robotics: Science and systems, 2007.

---

Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. In Proc. NeurlPS, 2017.
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Proc. AAAI, 2017.
Akhil Bagaria and George Konidaris. Option discovery using deep skill chaining. In Proc. ICLR, 2020.
Akhil Bagaria, Jason K Senthil, and George Konidaris. Skill discovery for exploration and planning using deep skill graphs. In Proc. ICML, 2021.
Jur van den Berg, Sachin Patil, and Ron Alterovitz. Motion planning under uncertainty using differential dynamic programming in belief space. In Robotics Research, pp. 473-490. Springer, 2017.
Dimitri P Bertsekas and John N Tsitsiklis. An analysis of stochastic shortest path problems. Mathe- matics of Operations Research, 16(3):580-595 1991.
Emma Brunskill and Lihong Li. Pac-inspired option discovery in lifelong reinforcement learning. In Proc. ICML, 2014.
Erwin Coumans and Yunfei Bai. Pybullet, a python module for physics simulation for games, robotics and machine learning. http://pybullett org 2016.
Konrad Czechowski, Tomasz Odrzygóídž, Marek Zbysińíski, Michal Zawalski, Krzysztof Olejnik, Yuhuai Wu, Lukasz Kuciński, and Piotr Miloš. Subgoal search for complex reasoning tasks. In Proc. NeurlPS, 2021.
Yanzhu Du, David Hsu, Hanna Kurniawati, Wee Sun, Lee Sylvie, CW Ong, and Shao Wei Png. A pomdp approach robot motion planning under uncertainty. In International Conference on Automated Planning & Scheduling, Workshop on Solving Soal-World POMDP Problems. Citeseer, 2010.
Ben Eysenbach, Russ R Salakhutdinov, and Sergey Levine. Search on the replay buffer: Bridging planning and reinforcement learning. In Proc. NeurIPS, 2019.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In Proc. ICML, 2018.
Michael Hibbard, Abraham P Vinod, Jesse Quattrociocchi, and Ufuk Topcu. Safely: Safe stochastic motion planning under constrained sensing via duality, arXiv preprint arXiv:2203.02816, 2022.
Robert C Holte, Maria B Perez, Robert M Zimmer, and Alan J MacDonald. Hierarchical a Searching abstraction hierarchies efficiently. In AAAI/AAII, Vol. 1, pp. 530-535, 1996.
Yuu Jinnai, David Abel, David Hershkowitz, Michael Littman, and George Konidaris. Finding options that minimize planning time. In Proc. ICML, 2019.
Tom Jurgenson and Aviv Tamar. Harnessing reinforcement learning for neural motion planning. In Proc. RSS, 2019.
Tom Jurgenson, Or Avner, Edward Groshev, and Aviv Tamar. Sub-goal trees framework for goal- based reinforcement learning. In International Conference on Machine Learning, pp. 5020-5030. PMLR, 2020.
Lydia E Kavraki, Petr Svestka, J-C Latombe, and Mark H Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE transactions on Robotics and Automation, 12(4):566-580, 1996.
Junsu Kim, Younggyo Seo, and Jinwoo Shin. Landmark-guidedd subgoal generation in hierarchical reinforcement learning. In Proc. NerulPS, 2021.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. Proc. ICLR, 2014.
10

---

Harsha Kokel, Arjun Manoharan, Sriraam Natarajan, Balaraman Ravindran, and Prasad Tadepalli. Reprel: Integrating relational planning and reinforcement learning for effective abstraction. In Proc. ICAPS, 2021.
James J Kuffner and Steven LaValle. Rrt-connect: An efficient approach to single-query path planning. In Proc. ICRA, 2000.
Tejas Kulkarni, Karthik Narasimhan, Ardavan Saeedi, and Josh Tenenbaum. Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. In Proc. NeurIPS, 2016.
Нanna Kurniawati, Tirthankar Bandyopadhyay. and Nicholas M Patrikalakis. Global motion planning under uncertain motion, sensing, and environment map. Autonomous Robots, 33(3):255-272, 2012.
Thanard Kurutach, Aviv Tamar, Ge Yang, Stuart J Russell, and Pieter Abbeel. Learning plannable representations with causal infogan. In Proc. NerulPS, 2018.
Steven M Valle. Rapidly-exploring random trees: new tool for path planning. 1998.
Andrew Levy, George Konidaris, Robert Platt, and Kate Saenko. Learning multi-level hierarchies with hindsight. In Proc. ICLR, 2019.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In Proc. ICLR, 2016.
Daoming Lyu, Fangkai Yang, Bo Liu, and Steven Gustafson. Sdrl: interpretable and data-efficient deep reinforcement learning leveraging symbolic planning. In Proc. AAAI, 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 5 51807540):599-33,, 2015.
Daniel Molina, Kislay Kumar, and Siddharth Srivastava. Learn and link: Learning critical regions for efficient planning. In Proc. ICRA, 2020.
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. In Proc. NeurIPS, 2018
Ofir Nachum, Shixiang Gu, Honglak Lee, and Sergey Levine. Near-optimal representation learning for hierarchical reinforcement learning. In Proc. ICLR, 2019.
Sujoy Paul, Jeroen Vanbaar, and Amit Roy-Chowdhury. Learning from trajectories via subgoal discovery. In Proc. NeurlPS, 2019.
Mihail Pivtoraiko, Ross A Knepper, and Alonzo Kelly. Differentially constrained mobile robot motion planning in state lattices. Journal of Field Robotics, 26(3):308-333 2009.
Vitchyr Pong. Shixiang Gu, Murtaza Dalal, and Sergey Levine. Temporal difference models: Model- free deep rl for model-based control. arXiv preprint arXiv:1802.0908: 2018.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In Proc. MICCAI, 2015.
Dhruv Mauria Saxena, Tushar Kusnur. and Maxim Likhachev. Amra*: Anytime multi-resolution multi-heuristic In Proc. ICRA, IEBE, 2022.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In Proc. ICML, 2015.
Naman Shah and Siddharth Srivastava. Using deep learning to bootstrap abstractions for hicrarchical robot planning. In Proc. AAMAS, 2022.
11

---

David Silver and Kamil Ciosek. Compositional planning using optimal option models. In Proc. ICML, 2012.
Özgür Şimgek, Alicia P Wolfe, and Andrew G Barto. Identifying useful subgoals in reinforcement learning local graph partitioning. Proc. ICML, 2005.
Martin Stolle and Doina Precup. Learning options reinforcement learning. International Symposium on abstraction, reformulation, and approximation, pp. 212-223. Springer, 2002.
Wen Sun, Jur van den Berg, and Ron Alterovitz. Stochastic extended lqr for optimization- based motion planning under uncertainty. IEEE Transactions on Automation Science and Engineering, 13(2):437-447) 2016.
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2)1811-11, 1999.
Aviv Tamar, Yi Wu, Garrett Thomas, Sergey Levine, and Pieter Abbeel. Value iteration networks. Advances in neural information processing systems, 29, 2016.
Jur Van Den Berg, Sachin Patil, and Ron Alterovitz. Motion planning under uncertainty using iterative local optimization in belief space. The International Journal of Robotics Research, 31 111):1263-1278, 2012.
Michael P Vitus, Wei Zhang, and Claire J Tomlin. A hierarchical method for stochastic motion planning in uncertain environments. Proc. IROS, IEEE, 2012.
Christopher JCH Watkins. Learning from Delayed Rewards. PhD thesis, King's College, London, 1989.
Fangkai Yang. Daoming Lyu, Bo Liu, and Steven Gustafson. Peorl: Integrating symbolic planning and hicrarchical reinforcement learning for robust decision- making. Proc. IJCAI, 2018.
12


Reviews:
[{"review_id": "lT7IosRQf06", "reviewer": "Reviewer_Dfkf", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a stochastic path planning algorithm using options to learn a policy that outperforms only RL-based (SAC) or replanning-based (RRT) motion planners. The proposed algorithm, called SHARP, proceeds hierarchically in 3 steps: (1) The search space is segmented into critical regions using a trained UNet. (2) A sequence of option start and end states are constructed using the critical regions, the start and goal locations, and a sequence of intermediate option guides are synthesized. (3) The options serve as the abstractions over the primitive action space. A* search is used to first plan a path over options. Finally, SAC is used to learn an RL policy that guides the agent to select primitive actions for each option.  \n", "summary_of_the_review": "Some more intuitions and motivation for the proposed approach, and better analysis of the experimental results would help improve the paper. \n\n\n==============\n\nPost-rebuttal update: I will keep my original rating of the paper. I agree with reviewer CLF4 regarding insufficient motivation for the real-world applicability of this method in terms of its computational complexity. Although during the rebuttal the authors have provided results on a larger environment (75x75m), Fig 2 also shows that SHARP requires ~6k seconds to find the goal in certain tasks (P1, P2). It would help to provide results on more tasks (currently only 5 tasks are considered), and a thorough analysis of what kinds of tasks SHARP provides an advantage on versus where it can struggle to find the goal and require more time? ", "strength_and_weaknesses": "The paper contains a concise overview of the related works and the background concepts necessary to understand the proposed approach to stochastic path planning. \n\nThe following points should be addressed to improve the paper:\n\n1. In Definition 9, the reward function formulation lacks intuition / motivation. It is not clear to me why this particular formulation was proposed and what is the difference between the second and third case for the definition of $R_i(x)$.\n\n2. The description of the experimental setup is confusing to me.\n\n- (a) I think P1-P5 are the 5 start and goal tasks but it has not been explicitly mentioned in the paper. \n\n- (b) The results show that SHARP-Centroids can sometimes plan faster than SHARP-Interfaces, and vice versa. What if any is the key difference between the two types of options? Is it task dependent or is there a general characterization that can differentiate the performance of the two approaches?\n\n- (c) “Fig 3 and 4 show that our approach was able to successfully transfer learned policies for options for subsequent problem instances without having to compute these policies again” - This is unclear to me. Some more intuition or explanation for transferability among options would be helpful. Are option policies transferable if the option endpoints are the same across different environments or across different start and goal states in the same environment?  \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "kAXwgC1jK4", "reviewer": "Reviewer_CLF4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new algorithm to learn policies for stochastic path problems that is called stochastic hierarchical abstraction-guided robot planner (SHARP). The algorithm consists of four parts: identify critical regions, synthesize option endpoints, generate a pseudo-reward function, and finally learn an option policy. The new approach is claimed to be able to transfer knowledge across tasks, and outperform existing approaches. The claims are supported by experiments in simulated robot navigation domains.", "summary_of_the_review": "Even though the proposed algorithm appears to be novel and interesting, the experimental evaluation is limited. For this reason I suggest rejecting this paper.\n\nThe paper could be improved by some additional experiments on larger and/or more complicated robot navigation tasks. Even including a discussion of how SHARP would scale to larger domains, or to the real world, would be a significant improvement.\n", "strength_and_weaknesses": "The main strength of this paper is that it provides a new and complete algorithm for stochastic path planning. It combines conventional path planning with RL, and its effectiveness is supported by experimental results in some limited simulated domains.\n\nThe main weaknesses of the paper are the complexity of the proposed algorithm and the limited experimental evaluation. The proposed approach requires a complex series of steps to produce the final policy, and it is not clear to me that this complexity is fully justified. For example, a step in the algorithm is to generate a \"guide path\", and this is done using the HARP motion planner. Since you are running HARP, why not just use the path planned by HARP to make the policy directly? What is the advantage of turning the path into a reward function, then training a policy on that?\n\nWhat is not clear from the experimental evaluation is how the method will scale to larger navigation tasks. There is no discussion of this. Will this method be useful in real world robotics navigation problems? It is complicated and requires accurate models: will it scale?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RYqWArCYXG", "reviewer": "Reviewer_pCv5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose to, for a specific robot, learn to recognize possible intermediary goals for motion tasks which generalize to new previously unseen maps with static obstacles. These possible intermediary motion goals (options) are either centroids (one per region) and interfaces (one per pair of connected regions). Abstract actions are formed by the transition between two options. RL policys are learned for motion of abstract actions, and shown in the evaluation to generalize to new maps. Motion planning takes place first at the abstract action level, and the plan is realized by following the policy of each abstract action, in sequence, until the robot reach the goal. The approach is compared to, and shown to outperform, SAC and RRT in both computation time and motion goal success rate (within a timelimit of 1200 seconds).", "summary_of_the_review": "The proposed approach is interesting, well-integrated and show benefits over RL without abstract actions for motion planning.\nIdeas presented are in part explored in the literature in related fields. Since these are important for the current work it might be good to highlight the connections.", "strength_and_weaknesses": "Strength:\n* Abstract actions address one of the brittleness-issues of contemporary DRL. Generalization to new maps is demonstrated, which is a major contribution of the paper.\n* Abstract actions makes the approach more transparent and interpretable - important properties from the perspective of Trustworthy AI. An abstract plan is much easier to understand, explain and monitor than a DRL policy.\n* The approach present an integrated solution, from critical region learning & detection to the hierarchical algorithm that use abstract actions to fine motion plans. It necessitates that the individual parts works in a real way, such that the integrated whole works.\n* Connections to graph search and symbolic action/plan representations (reminds me a bit about landmarks or similar from the automatic planning field) allow the method to use and combine the strengths of different fields (A* and RL, symbols and state-space etc.)\n\nWeaknesses:\n* \\mathcal{S} is used for both state space (configuration space) and for abstract states? Since the state space \\mathcal{S} is equal to \\mathcal{X}, why not use \\mathcal{X} instead?\n* \"This shows that using RL for stochastic motion planning produces robust solutions.\": It is shown to be more robust than RRT (in these environments), but 90% success rate is not *robust*.\n* Not necessarily something that has to change, but there are possibly more suitable baselines to compare with from the path/motion planning literature. Large-scale path planning has and still is often approached using hierarchical planning, e.g. by A* over an \"abstract\" graph, then A* in between the nodes of the graph [1]. Modern non-learning based motion planning approaches (e.g. lattice-based motion planning [2]) use translation invariant motion primitives (generated offline using optimal control) as *actions* in e.g. A*-search to generate physically feasible trajectories in large and complex environments in real-time, with both static and dynamic obstacles. Such methods would provide probably provide a more suitable baseline than RRT (with or without hierarchical comparisons.)\n* Why call it \"Multi-Task\" when it is only path planning? I get that it is for many possible different path goals.\n\n\n[1] Holte, Robert C., et al. \"Hierarchical A*: Searching abstraction hierarchies efficiently.\" AAAI/IAAI, Vol. 1. 1996.\n\n[2] Pivtoraiko, Mihail, Ross A. Knepper, and Alonzo Kelly. \"Differentially constrained mobile robot motion planning in state lattices.\" Journal of Field Robotics 26.3 (2009): 308-333.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CRjjxxe2q3B", "reviewer": "Reviewer_Xjkg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Authors tackled the problem of stochastic path planning using option learning. The idea is to a) sample good trajectories to identify critical regions based on region-based Voronoi diagrams [shah & Srivastava 2022] b) define options based on critical regions, authors explored both centroid based and interface based c) learn the corresponding policies for discovered options d) find a path on the abstracted space using A* e) project the high-level path to lower-level actions using the option policies. The approach was later compared against stochastic actor-critic (SAC) and Rapidly-Exploring Random Tree (RRT) showing advantage in terms of planning time and path success rate.\n", "summary_of_the_review": "Love the direction of the paper, but it needs to be improved in terms of writing and positioning with existing efforts to be fully baked.", "strength_and_weaknesses": "Strengths\n+ Option discovery and planning using abstraction for stochastic path planning is of huge interest to the community.\n+ The main idea of the paper is simple.\n\nWeaknesses\n- Writing: The paper is hard to follow (see below)\n- The literature review misses key references (e.g. [1]).\n- The baseline for empirical results is weak. Two baseline to include [2] using hard-coded options and [1]\n- \"Does combining reinforcement learning with high-level planning improve its efficiency?\", the answer is yes and already covered in [2]\n\n[1] Pierre-Luc Bacon, Jean Harb, Doina Precup, \"The Option-Critic Architecture\", in Thirthy-first AAAI Conference On Artificial Intelligence 2017\n[2] Richard S Sutton, Doina Precup, and Satinder Singh. \"Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learnings\". Artificial intelligence, 112(1-2):181–211, 1999.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject