NavTuner: Learning a Scene-Sensitive Family of Navigation Policies

One candidate approach to learning and navigation is to replace the traditionally engineered system with an end-to-end sensor to decision neural network [3, 5, 4, 6]. Empirical and limited benchmarking show some promise on this front. However, instead of directly solving the navigation problem itself, these methods solve some highly specific subset of it, typically equivalent to the local navigation problem. All argue for the need to integrate with existing hierarchical schemes, though few actually do so. Both [3, 7] show that reinforcement learning or reward-based approaches for local planning in a local-global hierarchical planner can work. Instead of mapping sensor input to navigation decisions directly, other learning based methods seek to map the sensor data to higher level information for decision making. Inverse reinforcement learning has been used to learn a reward function from RGB-D features and goal-directed trajectories [8]. As has learning a neural SLAM model to output necessary information for global and local policies to control a robot [9]. Learning-based perception can be combined with model-based control methods to navigate in partially observable, unknown environments [10].

Overall, there is no substantive benchmarking of learning based methods with traditional navigation schemes [6]. Thus, the assertions that learning can overcome sensitivity to environmental conditions and can outperform traditionally engineered systems remains unconfirmed. As a preliminary investigation, we implemented a couple methods and benchmarked them in simulated ROS/Gazebo environments, see Figure 1 (and §IV-A for more details). When compared to a traditional hierarchical navigation approach [2], learning-based navigation methods have lower performance and equivalent or higher sensitivity to the environment. The sensitivity can be seen by the drop in performance (e.g., higher slope) as the environment becomes denser in the success rate vs obstacle quantity graphs of the second row. Lastly, the variable performance across environments indicates poor generalization to world structure by the learning methods.

Tasks involving perception to action pipelines, such as visual navigation, can be implemented using end-to-end reinforcement learning (RL) based on deep convolutional neural network policy learners [11, 12, 13, 14, 15]. This is perhaps the most pervasive use of RL in vision-based navigation contexts. The learnt policy directly maps visual sensor input (laserscan, RGB image, or depth map) to actions, steering commands, or velocities [16, 12, 17]. Policy learning can be improved by using knowledge from previously learnt visual navigation tasks when learning new tasks [17]. Adding decision relevant auxiliary tasks can promote learning internal representations that support navigation [18], and improve the sample efficiency of RL while speeding up the training process[19]. In a similar vein, providing mid-level visual cues improves the learning, generalization, and performance of policies [20]. Also, learning subroutines instead of individual actions can boost the performance[21]. While navigation is a good task to demonstrate RL methods, in many cases the task focuses on navigation guidance more so than collision avoidance. Evaluation does not focus on embodied navigation nor realistic motion and collision models. Application of RL to robotics places more emphasis on the structure of the learning network [16, 22] and on the use of existing navigation methods to generate policy samples [22, 4, 23], and less on the policy learner.

Typical solutions for vision-based navigation rely on a combination of path planning and sensor-based world modeling to synthesize local paths through the world based on recovered structure. The most effective policies are hierarchical, with a global planner establishing potentially feasible paths based on an estimated map and a local planner for following as closely as possible the global path, subject to collision-avoidance constraints in response to sensed obstacles missing from the map [24, 25, 26]. Though exhibiting strong performance in Figure 1, the variable maximum success rates and downward trends of egoTEB [2] across the graphs indicates that traditional methods are not immune to variation in world structure. There is potential value in modifying them based on the local obstacle configuration space, i.e., in performing online parameter tuning for navigation.

The potentially negative impact of incorrect hyper-parameters or parameters is well established in machine learning. Hyper-parameter optimization improves learning outcomes without requiring major modifications to the underlying learning structure [27, 28, 29]. When feasible to implement, the additional computation needed is offset by the performance enhancement. Given that RL policies can exhibit high variability to the training process and parameter settings, the process of gradient-free, hyper-parameter and reward tuning is recommended when the additional computational resources are available [30].

There is prior work on automatic parameter tuning applied to motion planning and navigation. Motion planning algorithms can perform better with random or Bayesian based [31], and model based [32] automatic parameter tuning algorithms. The benefits also apply to safety constraints [33]. Parameter tuning can also be incorporated into the learning process of a learning-based motion planning algorithm to reduce sensitivity to manual tuning [34]. Adaptive planner parameters of a planner can be learnt through intervention [35], demonstration [36], and reinforcement learning [37].

The global planner recomputes the global path at a specified frequency to refresh its estimated best path based on data accumulated during navigation. Additionally, there are special events that trigger new plans (such as arriving at a dead-end). The tunable global planning frequency is upper bounded by the local planning frequency (or sensing rate) and the rate at which new global paths are generated. Other environmental events not part of the detect special events impact the need for new global plans. Sensory information accumulating in the local map may indicate that the current global path is no longer feasible and should be recomputed; or that an unavailable path option may now be feasible and should be considered.

The effect of changing $f_{\_}{\text{G}P}$ for a given environment and navigation goal is visually exemplified in Figure 2 (top-left). Table I quantifies its influence. The table reports the difference between the best performing and the worst performing outcomes in the Maze environment as a function of $f_{\_}{\text{G}P}$ across the different obstacle densities tested (50 repeated trials each). The difference is a measure of parameter sensitivity to environment changes. SR stands for success rate and PL stands for path length. In the environment with the most obstacles (least spacing) there are almost 20 more failures cases for the worst $f_{\_}{\text{G}P}$ setting versus the best. The path length increases by 7.68m which is rougly 14% of the average path length.

EgoTEB relies on the egocircle, an egocentric polar obstacle data structure, similar to a 1D laserscan, that operates as a local map. It retains multiple measurements per scan entry and complements available sensory information. For example, when the egocircle has a finer resolution than the actual onboard sensor, it has obstacle readings not captured by the sensor at the current time but captured at an earlier time. This data structure is parsed by egoTEB to establish navigation gaps between obstacles through which the robot may traverse. The gaps represent different path opportunities to take to the goal state.

Gap processing uses $d_{\_}{\text{L}A}$ to define a look-ahead distance cut-off when detecting gaps. Measurements beyond $d_{\_}{\text{L}A}$ are ”ignored” in simulation of a shorter distance scanner. Local paths generated as part of egoTEB will not extend beyond this radius. $d_{\_}{\text{L}A}$ limits the quantity of gaps detected since only nearby obstacles are considered, which reduces the quantity of candidate paths generated and tested. Figure 2 depicts the local map information and the detected gaps based on three different $d_{\_}{\text{L}A}$ values. The parameter determines the spatial extent of the local map, which ultimately influences several parts of the local navigation strategy. The impact of $d_{\_}{\text{L}A}$ on navigation is evident in Table I.

Several network models were chosen for the batch learning approach. They include: a linear network, a neural network (w/ReLu), and a convolutional neural network (w/ReLu). Two output structures are tested for each, a classifier structure over discretized values and a regression model for continuous prediction (trained with the discretized values). Training is performed by collecting the performance statistics of constant parameter value runs across a sweep of each discretized parameter individually.

The reinforcement learning model is a deep Q network (DQN) [39] with an action branching structure for multi-dimensional output [40], depicted in Figure 3. The reward structure uses knowledge of the shortest path between the start and goal. For each training run the reference shortest path is obtained from the $D^{*}$-Lite algorithm. During navigation, the reward is the negative of the distance between the agent’s current position and the nearest point on the shortest path. This reward is passed to the agent every 2 seconds for a policy update. The agent will also update at the end of a training run with the following terminal reward:

based on the the Success Weighted by Path Length [41], where $l$ and $l_{\_}{min}$ are the lengths of the actual path taken by the robot and the reference shortest path, respectively.

To define navigation scenarios for which there is always a valid path between any random start and goal poses, we designed a maze environment consisting of maze walls placed within a $20m\times 20m$ square room. The maze walls are composed of $0.5m\times 0.5m$ blocks placed on a Manhattan grid within the maze free space. Several different wall configurations for the mazes exist. The occupancy map of these different mazes are used as the initial global occupancy map for the robot.

During a trial, the initial map provided for the maze will be incorrect because of the randomized placement of obstacle cyclinders with a radius of $0.15m$ within the world. There are two random placement strategies, uniform density and non-uniform density. A non-uniform placement density is achieved by dividing the environment into $5\times 5$ sub-regions and assigning each region a random uniform density. The density specification for a maze region is given by a minimum inter-obstacle distance from the discrete set $\{0.75,1.0,1.25,1.5\}\,m$.

To generate training data for the supervised methods, we performed a single coordinate parameter sweep over the uniform density and robot configuration and ran each configuration 50 times with valid random start and goal poses lead. The result was a a total of $50\times 5\times 4=1000$ runs for $f_{\_}{\text{G}P}$ and $50\times 10\times 4=2000$ runs for $d_{\_}{\text{L}A}$. The robot navigation data of the robot is recorded, including the egoTEB processed collision-space scan data and the navigation performance data of the runs, such as whether a run succeeded, the path length, and the runtime.

The binary success data provides a success rate for the navigation parameter and density pairing combination. For each density we choose the hyper-parameter value that maximizes the success rate. The average path length is used as a tie breaker (then the average runtime in the case of another tie). The best value versus the density $\rho$ defines the selection functions $f_{\_}{\text{G}P}(\rho)$ and $d_{\_}{\text{L}A}(\rho)$, which are depicted in Fig. 4.

The classifiers were trained with cross entropy loss and the regressors were trained with mean squared error loss, both using the SGD optimizer. The known densities of the mazes and the best hyper-parameter values for said densities, plus the recorded laser scan readings during the navigation scenarios provide the training data.

Since training for reinforcement learning requires evaluating rollouts, it involves a different process. The DQN was trained in a non-uniform environment using $\epsilon$-greedy with the reward function described in Section II-C2, either from scratch or with a warm start using the collected batch data.

The model trained from scratch is trained for 1000 runs, and the warm started one is trained for 800 runs after first training with behavior cloning using the chosen best hyper-params for 200 runs. We compare the two models to see how previous knowledge acquired from experiments in uniform environments will influence model performance.

Experiments are conducted in the four environments: maze, sector (dense), campus (dense), and office (dense). The last three are benchmark environments from [38]. The maze environment has two sets of evaluation experiments: with the same maze and with a maze different from the training maze. Chaging the maze tests whether the network models have learned the specific maze wall setup instead of the local obstacle distribution.

To vary from the training data, we generate 4 different types of random obstacles, including 0.3m$\times$0.3m and 0.15m$\times$0.15m boxes, and cylinders with diameters of 0.3m and 0.1m. The maximum number of obstacles are 200 for the maze and sector environments, and 500 for the campus and office environments. In each environment, we run the 5 experiment configurations, consisting of 0, 25%, 50%, 75%, and 100% of the maximum number of obstacles.

For each run, the performance data collected is the success rate, the path length, and the runtime. For the maze environment, we also run experiments where the parameters are updated based on the best value curves (Figure 4), using the known density. It represents an oracle version.