We present a method for policy learning to navigate indoor environments. We adopt a hierarchical policy approach, where two agents are trained to work in cohesion with one another to perform a complex navigation task. A Planner agent operates at a higher level and proposes sub-goals for an Executor agent. The Executor reports an embedding summary back to the Planner as additional side information at the end of its series of operations for the Planner's next sub-goal proposal. The end goal is generated by the environment and exposed to the Planner which then decides which set of sub-goals to propose to the Executor. We show that this Planner-Executor setup drastically increases the sample efficiency of our method over traditional single agent approaches, effectively mitigating the difficulty accompanying long series of actions with a sparse reward signal. On the challenging Habitat environment which requires navigating various realistic indoor environments, we demonstrate that our approach offers a significant improvement over prior work for navigation. The ability to model and understand the world at a high-level is crucial for performing complex tasks in real world environments. Part of this high-level understanding involves the ability to divide and plan out tasks that are complicated and have long time horizons into more manageable subtasks. For example, when navigating to a new location, we typically break the task down into a set of manageable directions (i.e. drive along a certain road until a familiar landmark before taking a turn). Imbuing machines with this ability of creating abstractions for long and complex tasks is an active area of research known as hierarchical learning (; 1999). Research for navigation has recently seen a rejuvenation due to the advent of learning-based approaches; ). Embodied learning-based approaches have shown some appealing properties over classical approaches such as being able to operate in complex environments with limited sensor data . However, there is a need for the ability to plan across long time horizons with sparse reward signals. This in effect, causes limitations such as the inability to overcome small obstacles when navigating towards a given goal and the requirement of invoking the environment a large number of times for any meaningful learning to occur . Works which have combined hierarchical reinforcement learning with imitation learning have shown promising (b;), by leveraging expert trajectories with policy sketches , which are less expensive to obtain; however these sketches still require annotation of the environment. In this work, we study such hierarchical control for the task of indoor navigation, whereby an embodied agent is randomly spawned within a novel and complex environment and must learn to navigate this environment through interaction (a). We address this challenging learning problem through a hierarchical policy approach, where two agents are cooperatively trained together. Each agent performs a different role, where one agent acts as a Planner, learning how to propose good sub-goals to an Executor agent, which acts at the low level to achieve these sub-goals (Fig. 1). In contrast to existing hierarchical policy learning approaches, communication between our two agents is two-way, where the Executor provides the Planner with a summary of its series of actions and recent observations. This aids the Planner in deciding the next sub-goal with additional side Figure 1: Our PLEX framework adopts a hierarchical policy approach, where a Planner proposes sub-goals for an Executor to act upon within an environment. The Planner receives an egocentric, top-down view with the target location and an embedding summary provided by the Executor. The Executor receives visual sensory data (i.e. colour and depth) as its input and a sub-goal provided by the Planner. Our method reduces the need for long-term planning and addresses the known sample inefficiency problem accompanying memory models within deep reinforcement learning approaches. information provided by the Executor. To this end, we propose PLEX, a planning and executing learning framework which offers the following contributions: • A hierarchical reinforcement learning approach where two agents specialise on different tasks but are jointly trained by sharing information • We demonstrate both theoretically and empirically that our method benefits from significantly improved sample efficiency as the time horizon is distributed between the Planner and Executor • By extension, our approach mitigates problems prevalent in long-horizon planning, especially those adopting LSTM planning approaches Hierarchical Reinforcement Learning The application of hierarchical reinforcement learning (; 1999;) in real world settings has allowed deep reinforcement learning approaches to scale with the increasingly higher sample requirements that are required by complex real world environments (b; a). Early works considered an options-based approach, where there was an underlying assumption of the existence of some useful set of options which are fully defined beforehand; this allowed learning to occur at a higher level in terms of those set of options (; 1999). , a hierarchical approach was adopted without the use of imitation learning. However, the work was limited to exploring non-realistic environments and information flow was uni-directional from master to controller. proposed sub-goals which have semantic meaning; although this demanded a high-level of supervision where rich annotations on a given environment were required. The work of showed that using a hierarchical learning approach can lead to a reduction in the cost of exploration on problems with sparse rewards under the limited context of game environments. Das et al. (2018b) explored the embodied question answering task (a), leveraging heuristics embedded in the environment for providing expert trajectories used in the imitation learning initialisation stage. This method is heavily supervised and assumes that full semantic information of the environment is known. Additionally, the approach of Das et al. (2018b) is limited to a specific set of sub-goals, for example: Exit-room, Find-object, etc., imposing limitations on the expressiveness of the master policy. By contrast, our method allows the Planner to propose sub-goals which directly relate to the given environment (i.e. a continuous point-goal vector) and does not rely on external annotations for supervision. Embodied Agent Learning There has been a recent surge of interest towards embodied agent learning where an agent is personified and spawned within an environment and set to complete a certain task. Such tasks may include question answering (a), point goal navigation , roaming and scene exploration or coverage . This problem is purposely set up in a way which allows for relatively easy transfer from simulation environment to a physical robotic platform operating in a real world environment. Various simulation environments have been designed around this (; ; ; ;), which aim to provide a realistic indoor simulation for training embodied agents on the aforementioned tasks. These environments allow an agent to invoke the environment numerous times, and in effect, scale the sample hungry nature of the problem to an extent where agents perform at a reasonable level (; a). trained an agent using the Proximal Policy Optimisation algorithm , augmenting it with a memory unit . Although this provided a strong initial baseline, achieving this required invoking an environment for millions of steps. The recent work of attempted to address this by proposing a memory component which makes use of the transformer network . Although this approach mitigated a key weakness in LSTM memory units , it incurs with it a linear growth of memory usage which is addressed via memory compression and hence increases the computational complexity of the model. The aforementioned issues are not present in our framework since the Executor's rollout is strictly shorter as we will soon demonstrate. 1 2. The sum of these i.i.d variables is S N = N i=1 X i. As we increase the rollout length N, the agent's probability of exploring decreases exponentially and is given by the following bound: Intuitively and as shown theoretically, reducing the rollout length N has a positive impact on the required exploration (for a more general form of this proposition, we refer the interested reader to). One way to exploit this insight is through a hierarchical approach which allows setting sub-goals that are closer in state space to the agent's current state. Given this insight, we now provide details of our hierarchical approach which consists of two main components: a Planner and an Executor policy. Each of these components is treated as an independent agent with respective policies π θ P L and π θ EX. A high-level overview of our framework is shown in Fig. 2. The environment is denoted as P, from which states s are sampled. A reward function R provides the reward conditioned on a state s, an action a and a goal. In general, a goal denoted by g indicates the end goal for the current episode, with g P denoting the sub-goals given by the Planner. N EX and N P L denote the respective rollout lengths of the Executor and Planner. Executor Building upon previous RL frameworks, an Executor is optimised using standard policy learning techniques . A key difference between existing non-hierarchical Figure 2: A system overview of PLEX which consists of two main components: a Planner and Executor agent. The Executor's task is to perform a series of actions such that it will traverse the environment towards a target location given by a point-goal vector (a sub-goal that is provided by the Planner). The Planner's task is to generate sub-goals that help navigate the entire system to an end goal (which only the Planner can see). An environment's state is comprised of an RGB-D observation, an egocentric map and a point-goal vector measurement pointing towards a target location as defined by. The Executor is provided with the RGB-D observation, a sub-goal generated by the Planner and returns an Executor Latent Information (ELI) vector that summarises its rollout. The Planner sees an egocentric map with a roughly 4m view horizon and the ELI vector. The Planner and Executor agents are trained simultaneously and using the sub-goal by the Planner and ELI vector by the Executor, we create a two-way communication channel, enabling our framework to regulate the flow of information between our two agents. approaches and our approach is the Executor End State or sub-goal g P, which is not provided by the environment but rather by a Planner policy. Consequently, the rewards provided to the Executor are sampled using the sub-goal (i.e.: r i ∼ R(r i |s i−1, a i, g P)). In line with this, the Executor policy also provides an Executor Latent Information (ELI) vector which summarises its rollout experience back to the Planner policy to provide feedback for the Planner towards planning the next sub-goal. In effect, this creates a cooperative feedback loop between the Executor and Planner. A detailed outline of the Executor routine is provided by Algorithm 1. Planner The Planner does not invoke the environment directly, but it modifies the goal and rewards observed by the Executor when the Executor interacts with the environment. This modification is achieved through the generation of planned sub-goals given to the Executor by the Planner. As such, given a state s and an ELI vector provided by the Executor, the Planner produces a subgoal. Using this sub-goal, the Executor routine (Algorithm 1) is invoked and a reward is returned to the Planner which provides it with feedback on the generated sub-goal. Upon optimising the Planner, we note that the Executor should not be directly affected from the Planner optimisation process (i.e. we terminate backpropagated gradients from the Planner policy before they reach the Executor policy). In other words, the ELI vector provided by the Executor does not affect the Executor directly, but implicitly through improving the Planner policy's generated sub-goals since providing direct feedback to the Executor through the ELI vector will in a redundant Planner. Algorithm 2 fully outlines our approach and details the Planner routine. We focus on the indoor PointGoal navigation task as defined in. In this setup, a point-goal vector providing the distance and angle towards the target point in the environment is assumed. If the indoor environment would be an empty space, this task would be trivial. However, in a more realistic, real world setting, the agent is spawned in a room within the environment and the target may be in a different room. In such a case, the agent needs to effectively navigate around obstacles and plan its future actions in the presence of other rooms that may or may not lead to the target point. The environment provides RGB-D sensory information and inaccurate access to the location and orientation (as could be obtained using a fusion of GPS and IMU sensors ). From these sensors, the environment can provide a coarse egocentric top-down map; we construct our egocentric map by adapting a similar approach in 1 (Section A.1 details the method of for constructing the egocentric map). The top-down map has a resolution of 0.5m per pixel which is a reasonable assumption given the provided sensors. In our hierarchical problem formulation, the Planner is provided with the egocentric, top-down map of size 32 × 32 pixels, the point-goal vector (translated to ego-map point-goal) (distance, direction) and the Executor Latent Information (ELI) provided by the Executor (a vector of 128 values). The Planner emits a binary category distribution for continue or stop operations and two continuous sub-goal distributions: the distance N (µ ρ, σ ρ) and direction N (µ θ, σ θ). The Executor is provided with RGB-D sensory information of 256 × 256 resolution along with the sub-goal computed by the Planner and emits a four category distribution with the actions described in Section 4.3, and emits the ELI vector which is returned to the Planner when the Executor stops or performs the maximum number of actions, N EX (note that for the Executor, the stop action does not stop the entire episode but simply returns control back to the Planner). Our Planner has a perception model for extracting embeddings from the egocentric map. This perception model is a CNN composed of 2 convolutional layers with filter size 4 × 4 and 3 × 3 with a stride of 2 and 1 respectively with ReLU activation. The output of these convolution layers is flattened and concatenated with the ELI vector and transferred to the last fullyconnected linear layer which outputs a 512 vector with ReLU activation. This output is concatenated with the 2-valued point-goal vector. The Executor's perception model consists of 3 convolution layers with filter sizes of 8 × 8, 4 × 4 and 3 × 3 with strides of 4, 2 and 1 respectively and ReLU activations. This is followed by a fullyconnected linear layer which outputs an embedding of 512 or 128, which depends on the model variant (LSTM or SMT respectively). We concatenate the 2-valued sub-goal vector to the output embedding. For the LSTM memory model, we employ the GRU formulation with hidden state of size 512. For the SMT memory model, we use an 8 multi-head attention mechanism (we do not employ the furthest point sampling technique used in as it did not affect the performance of our model). The output of either the GRU component or the SMT is the action embedding (a vector of 128 values corresponding to the output state vector of the LSTM) and also functions as the ELI vector. Both the Planner and the Executor policies are trained using the Proximal Policy Optimisation algorithm from , following the original settings found in the paper except for parameters specific to Algorithms 1 and 2: N EX = 10, γ EX = 0.9, N P L = 128, γ P L = 0.95. Note that the values of N EX and γ EX are chosen such that the Executor will focus on short-term rewards; this in turn will implicitly encourage the Planner to generate subsequent sub-goals which are nearby (further discussed in Section 4.4). Habitat is a modular environment API and can be used with realistic indoor environments coupled with tasks such as PointGoal navigation and Embodied Question Answering (a). For our experiments, we use the Gibson dataset and perform the PointGoal navigation task . We use the same train-test split as provided in which consists of 72 train scenes with 4.9M PointGoal navigation tasks and 16 unseen test scenes comprised of 1k PointGoal navigation tasks. The environment accepts 4 actions: [Forward, Turn left, Turn right, Stop], where invoking the stop action ends an episode with an episode running to a maximum of 500 steps otherwise. The reward structure is similar to with a success providing a reward of 10; otherwise, the agent's reward is the change in geodesic distance between the agent and the target with an additional slack of λ = −0.01. In addition, we penalise for obstacle collision with a cost c = −0.01. This additional collision penalty is a desirable property for embodied agents . In Section 3, we discussed the negative impact a long rollout horizon has on the exploration efficiency. The context was in a setup which allowed two actions, and did not take into account the complexities of realistic environments (such as obstacles and more actions). Hence, to choose an appropriate rollout length for the Executor (given the chosen environment and sensory input), we perform a short experiment which analyses a random exploration policy within the proposed setup. We randomly choose 500 starting locations from the training scenes, with a different initial starting point for recurring scenes. The agent can take 3 actions: [Forward, Turn Left, Turn Right], where the "Stop" action is excluded so that the rollout length can be inspected without being shortened. As we increase the number of random actions the random policy takes (N =), we inspect two values: the geodesic distance between the starting position and the end position of the policy (Fig. 3a), and the geodesic distance normalised with the number of random actions taken by the policy (Fig. 3b). The geodesic distance normalised by policy actions indicates the average distance travelled per number of actions and is an indication of exploration efficiency. As such, for initial exploration, we would generally want this value to be high. Fig. 3b observes that as the rollout horizon of the random policy increases, the exploration efficiency begins to rapidly decline. Whilst this decline is not exponential as suggested by Proposition 1, it provides us with further motivation not to set N EX too high. Further, we need to consider a large enough N EX to enable the Executor explore its environment. Given Figs. 3a and 3b and given a egocentric map with a resolution of 0.5m per pixel, N EX = 10 appears to maintain a good balance between the two criteria we wish to impose on the Executor: a high probability of exploring more than a unit distance in the egocentric map, along with high exploration efficiency. Baselines We compare our approach to two baseline methods PPO LSTM and PPO SMT. The former refers to the method found in , and the latter is a recent approach found in. For comparison, we employ two variants of our PLEX framework: PLEX LSTM and PLEX SMT. This comparison allows a fair comparison regarding the benefits toward improved sample efficiency that our framework offers for both compared baselines. Evaluation Metrics For evaluating the performance on the PointGoal task, we examine the reward each method obtains and the success ratio of each method. A success for an episode is defined when the agent provides a stop action and the geodesic shortest path distance between the agent and its end goal is less than 0.2m. We do not use the Shortest Path Length (SPL) as a evaluation metric, The observed success rate of each model. In this case, a success is defined as the agent issuing a stop action when the geodesic shortest path distance between the agent and its goal is less than 0.2m. Note that across both reward and success rate curves, the baseline methods exhibit a slow down in learning at around 15M environment steps whilst our method remains relatively robust and is able to maintain a steady learning rate. as defined by since maximising on this metric as an objective can in agents which exhibit undesirable behaviours (such as approaching too closely and colliding with obstacles). Instead, we observe the reward which is a unitless measure and penalises undesirable behaviours such as obstacle collision and moving in the wrong direction. This metric, along with success rates, provides good indicators for assessing performance on this task . Quantitative Results In Figs. 4a and 4b, we show the respective reward and success ratios of each method. Similarly, in Table 1, we outline the mean and variance of the final rewards and success ratios for all the methods after 30M environment steps. Each experiment was repeated 10 times across all methods. Note that the LSTM variant of our method (PLEX LSTM) achieves a success rate of 0.81 which is only slightly higher than the PPO LSTM reported in. The key difference is the significant lower number of environment steps (approximately half) that our method required for achieving a similar . The key idea behind the ELI vector is to provide additional information to the Planner that may not be observed in the egocentric map. Hence, the ELI vector is a mechanism that can be used by the Executor to relay a compressed representation of its previous observations to the Planner; assisting it towards generating sub-goals. Since the ELI vector is an integration of previous observations outputted by the Executor's LSTM component, we refer to it as a summary of the Executor's rollout. We adapt a hierarchical framework by , where conveniently, we can modify the Q-learning approach to a policy-based approach. In this context, our Executor replaces the Performance Metrics PPO SMT PPO LSTM Table 1: Avg. Reward and Avg. Success across the baseline models and our method applied to each method. Note that whilst the performance difference between the two baselines is small, both of our models outperform the baselines by a significant margin. Specifically, our PLEX LSTM variant shows a significant improvement over both baselines, achieving a higher than the baseline PPO LSTM model trained on more than double the number of environments steps. The performance of our method compared with PPO LSTM on close and far subsets of the test set. In this case, close goals were selected when mean geodesic shortest path distance was less than 5.76m and were classified as far goals otherwise. "Controller" and our Planner serves as the "Meta Controller". This allows us to assess the effect of not providing the Planner with an ELI vector. Empirically, these are shown in Fig. 5a. We can see that when the ELI vector is not provided, the communication channel from the Executor to the Planner is removed and we observe a decline in performance. This observation aligns well with our framework and demonstrates the value of enabling communication from the Executor back to the Planner. Across both reward and success ratio curves, the two baseline methods gradually exhibit a slow down behaviour starting at around 15M timesteps. In contrast, our PLEX framework appears relatively robust, demonstrating a more consistent learning pace. This highlights a key difference between our hierarchical method compared to the baseline approaches. Both baselines and our method are able to successfully learn simpler tasks, where the goal is relatively close to the agent's spawn location. However, for tasks where the goal is further away, the need for a more structured approach is necessary. Our empirical illustrate a potential drawback of LSTM-like units (and by extension, GRU), where they may suffer when learning long time horizon tasks. We divide the test set into two subsets containing close and far goals using a dividing criteria which uses the mean geodesic shortest path between the agent's spawn location and its end goal. In this case, close goals were selected when mean distance was less than 5.76m and were classified as far goals otherwise. The for this experiment are shown in Fig. 5b where the PPO LSTM is unable to navigate to the far goals in the allocated number of environment steps. In contrast, our method is far more successful in this task and is able to achieve a higher score on reaching far goals due to the extra reward provided for navigating to further away targets. Although the PPO LSTM baseline does eventually learn to navigate to further targets, it requires a much larger number of training iterations and environment invocations. In this work, we present a hierarchical reinforcement learning approach for solving PointGoal navigation tasks. Our proposed approach uses a cooperative learning strategy in which two agents, an Executor and a Planner are jointly learned to solve this task. This is enabled through a two-way communication channel established between the two agents through the use of an Executor Latent Information vector provided by the Executor and sub-goals generated by the Planner. We motivate the use of this hierarchical approach both theoretically, as well as through empirical experiments which demonstrate a significant improvement in sampling efficiency of our approach, allowing our structured approach to perform significantly better on increasingly harder tasks when compared to baseline approaches. Given an embodied agent trajectory of length N with corresponding depth images {D n} N n=1 ∈ R H×W and relative camera poses {T n} N n=1 ∈ SE, the set of 3D points P n ∈ R HW ×3 for frame n are extracted as follow: where the camera intrinsic matrix is K ∈ R 3×3. We then define the global set of all points at the end of the trajectory as: M ∈ R HW N ×3. The set M starts empty and is iteratively updated by the following rule: M n = M n−1 ∪ P n As the set of all points M is built, the egocentric map can be derived by projecting all points in M to a plane (we lose the "height" dimension and points projected to the same slot are resolved by taking the highest point), cropping and aligning a box using the vector of the agent's facing direction which in an egocentric map. Proof. The moment generating function of S N is given by: The probability of the Bernoulli sum being greater then αN with α > 1 2 can be bounded using the Chernoff bound: Analytically solving this bound, we obtain θ * = log α 1−α. We are specifically interested in the case where α > 1 2, and as a θ * > 0. Substituting θ * into Eq. 5 and defining β ≡ log 1 1−α + α log α 1−α concludes the proof. Algorithm 1 A pseudo algorithm of Executor Policy Gradient; Actor-Critic variant N EX ← initialise Executor rollout length γ EX ← initialise Executor discount factor g P ← initialise Planner goal r P = 0 initialise Planner reward buf f ers[s b, a b, r b] ← initialise state, action, reward buffers for i = 1 to N EX do a i, e θ EX ∼ π θ EX (a i, e θ EX |s i−1, g P) Sample policy for action and latent information s i, t i ∼ P(s i, t i |s i−1, a i) Sample environment for state and terminal r i ∼ R(r i |s i−1, a i, g P) Sample reward given Planner goal accumulate r P ← r ∼ R(r|s i−1, a i, g) Sample reward given end goal update buf f ers ← s i−1, a i, r i end for π θ EX ← update(π θ EX, buf f ers, γ EX) (as in PPO ) return (s i, r P, t i, e θ EX)
We present a hierarchical learning framework for navigation within an embodied learning setting