PUTN: A Plane-fitting based Uneven Terrain Navigation Framework (IROS 2022)

Created on June 11, 2026

2026   ·   traversability   navigation   terrain   ·   paper-review

Item Details
Authors Zhuozhu Jian, Zihong Lu, Xiao Zhou, Bin Lan, Anxing Xiao, Xueqian Wang, Bin Liang (Tsinghua SIGS)
Venue IROS 2022 (IEEE/RSJ International Conference on Intelligent Robots and Systems)
Links arXiv · Code

One-line Summary

PUTN is a three-stage navigation framework that lets a ground robot drive safely over bumpy outdoor terrain by fitting local planes to the point cloud to evaluate traversability. The sampling-based planner PF-RRT*, with plane fitting built in, produces a sparse global path; Gaussian process regression (GPR) interpolates the traversability and uncertainty of the dense path; and a nonlinear MPC (NMPC) avoids real-time obstacles while automatically slowing down in risky segments. The key idea is lazy terrain evaluation, “analyze only where the tree will pass instead of pre-analyzing the whole map”, and the code is public.

PUTN sits at the intersection of two streams: sampling-based planning and terrain traversability evaluation.

  • Sampling-based planning: from LaValle and Kuffner’s kinodynamic RRT (2001) and Karaman and Frazzoli’s asymptotically optimal RRT* (2011), to Informed-RRT* (Gammell 2014), which samples only within an ellipsoidal region after finding an initial solution. PF-RRT* inherits the skeleton of Informed-RRT* as is.
  • Terrain traversability evaluation: it grew more refined from 2.5D elevation maps (Fankhauser 2018) to Bayesian generalized kernel inference (Shan 2018) to the CVaR-based risk-aware evaluation of STEP (Fan 2021). These are accurate, but because they pre-analyze the whole map, computation explodes as the environment grows. PUTN diverges by analyzing planes only at the points where the sampling tree expands, avoiding this cost.
  • Planning directly on point clouds: Krüsi’s “Driving on point clouds” (2017) built curvature- and continuity-constrained paths on point clouds without explicit surface reconstruction. PUTN chose the compromise of local plane fitting instead of surface reconstruction.

Regarding later trends, the note only records the circumstantial observation that “it appears to be frequently cited as a comparison baseline in uneven-terrain navigation research”, and the precise follow-up citation relations have not been confirmed.

Problem and Motivation

Autonomous driving in indoor 2D structured environments has matured, but two difficulties remain for outdoor 3D unstructured terrain.

  1. Representing and computing large-scale maps consumes time. Pre-analyzing the whole terrain breaks real-time performance as the environment grows.
  2. Uneven terrain and real-time obstacles disrupt path planning. A static global path alone cannot avoid puddles, bridge edges, or trees encountered while driving.

The problem is defined as follows. Given start and goal states \(x_{start}, x_{goal} \in X_{trav}\) within the traversable region \(X_{trav}\), find a control strategy \(\pi^*\) that (1) satisfies kinematic and dynamic constraints, (2) avoids collisions, (3) minimizes travel time, and (4) minimizes the risk of attitude instability (rollover).

Key Ideas and Method

To describe the big picture with an analogy, a person walking a mountain trail does not look at each individual stone to step on, but at “whether the ground around the foot is flat, tilted, or has a hole”. PUTN likewise looks at terrain at the level of local planes rather than individual landing points.

Plane fitting and the traversability index

Around a surface point \(\tilde{x}_i\), a cube of side \(l_s\) is cut out to collect the point set \(\Omega_i\), and SVD yields the local plane \(P_i\) and normal vector \(n_i\). A robot footprint frame (6D pose) is constructed on the plane. The traversability \(\tau \in [0,1]\) is a weighted sum of three metrics.

\[\tau = \alpha_1 \frac{s}{s_{crit}} + \alpha_2 \frac{f}{f_{crit}} + \alpha_3 \frac{\lambda}{\lambda_{crit}}, \quad \alpha_1+\alpha_2+\alpha_3 = 1\]
Metric Definition What it detects
Slope \(s\) Angle of the normal projected onto the world Z axis Inclination, rollover risk
Flatness \(f\) Mean fourth moment of the points’ deviation from the plane Degree of bumpiness
Sparsity \(\lambda\) Ratio of empty space within the plane and whether the empty points are concentrated Holes, puddles, pits

Each metric is normalized by the critical value \(s_{crit}, f_{crit}, \lambda_{crit}\) at which the robot can no longer move or would roll over. \(\tau=0\) means fully traversable and \(\tau=1\) means fully untraversable. The design ignores small-area noise such as gravel or clods of soil and focuses only on the large features of ground undulation, flatness, and holes.

PF-RRT*: sparse global path

On the Informed-RRT* skeleton, a tree node is defined not as a position \(x_i\) but as a pair of plane and traversability \(N_i = (T_{M\tilde{R}_i}, \tau_i)\). The core loop is as follows.

  1. Sample and extend in 2D to obtain a new point.
  2. Project it onto the ground surface point with ProjectToSurface.
  3. Fit a plane at that location with FitPlane and compute traversability.
  4. If the collision check passes, connect it to the tree and Rewire.

The cost of connecting two nodes is the distance multiplied by a traversability penalty.

\[f(N_1, N_2) = \Big(1 + \omega\big(\tfrac{1}{1-\tau_1} + \tfrac{1}{1-\tau_2} - 2\big)\Big) \cdot l_{1,2}\]

As \(\tau \to 1\) the cost explodes, so the tree automatically stops expanding in rough terrain. The spacing between adjacent nodes is constrained to \(l_{i,i+1} < l_s/2\) so that the planes connect into a continuous “strip”.

The authors emphasize two differentiators. First, instead of pre-analyzing the whole map, only the current location is analyzed during tree expansion (analysis during expansion), removing unnecessary analysis and speeding up the response. Second, the 3D map is used directly rather than a 2.5D elevation map, handling more complex 3D environments. The previous path is used as a heuristic to also secure attitude stability.

GPR: traversability interpolation for the dense path

The path produced by PF-RRT* is sparse, and the traversability within each plane is assumed constant, so it is coarse. Therefore the waypoints are densified by linear interpolation, and GPR predicts the traversability \(\tau\) and uncertainty (variance \(\sigma\)) of the interpolated points. The training set is the entire set of RRT tree nodes \(D = \{(\xi_i, \tau_i)\}\) and the test set is the interpolated path. An RBF kernel is used.

\[k(\xi, \xi') = \sigma_f^2 \exp\Big[-\frac{(\xi-\xi')^2}{2l^2}\Big]\]

Unlike interpolating the path alone, this exploits the information of the whole tree, so confidence (small variance) is higher where nodes are dense. An advantage of this design is that confidence can be raised by reducing the exploration step size.

NMPC: real-time local planning

An NMPC follows the dense global path while adding real-time LiDAR point-cloud obstacles as constraints. A collocation-based optimization is solved with CasADi, with N nodes over a 1-second horizon. The model is a differential-drive model on the local plane, reduced to a planar top-down (2D) problem for simplicity.

\[\min_{x_k, u_k} \sum_{k=0}^{N-1} \big(\|x_k - x_k^d\|_Q^2 + \lambda \|u_k\|_R^2\big)\]

The constraints are the dynamics, state and input bounds, and the obstacle safety distance \(\|x_k - x_i^{ob}\| \ge d_{safe}\). The clever part is the control-cost coefficient.

\[\lambda = \big((1 - t_{mean})(1 - \sigma_{mean})\big)^{-2}\]

\(t_{mean}, \sigma_{mean}\) are the mean traversability and uncertainty of the current local plane. When the mean traversability is poor or the estimation confidence is low, \(\lambda\) grows, the control input is suppressed, and the robot automatically slows down.

Experiments and Results

Platform: Scout 2.0 four-wheel-drive UGV, Ouster OS0-128 LiDAR, Intel NUC (i5 2.4GHz, 16GB). The SLAM can be swapped between A-LOAM and LeGO-LOAM. The NMPC uses CasADi, and the GPR was implemented with a C++ library instead of Python for speed.

Four real-world scenarios: steep slope, flat bridge, forest, and arch bridge. The arch bridge was traversed with start and goal on either side using real-time map and global-path updates, and the other three scenarios were also validated qualitatively.

Comparative experiments: PF-RRT* was compared against (a) RRT* on a plain grid map and (b) RRT* on a pre-analyzed grid map. Same start and goal, same point-cloud analysis method, statistics over 100 runs per scenario. The metrics are the time to reach an initial solution and the optimization time to reach the same cost.

The three key results are as follows.

  1. PF-RRT* adds almost no terrain-analysis cost. If RRT* on a pre-analyzed map is the “minimum time without analysis”, attaching terrain analysis to plain RRT* increases the time greatly, whereas PF-RRT* does not. This is because only the terrain the robot will pass is analyzed, and it is the empirical proof of the authors’ core claim. The larger the grid-map resolution, the faster PF-RRT* was in comparison.
  2. The traversability term in the NMPC works as actual deceleration. In segments where the traversability index rises (risky), the linear velocity automatically decreases, passing bumpy ground or riverbanks more smoothly.
  3. Autonomous navigation succeeded in the four outdoor scenarios. The colors of the RRT tree nodes show the local-plane traversability, and the behavior of expanding freely on flat ground and stopping at trees or bridge edges is confirmed.

However, there is no direct quantitative comparison with other SOTA frameworks (STEP, elevation-map based, etc.); the comparison targets are limited to RRT* variants.

Conclusion and Significance

PUTN’s contribution lies in capturing both real-time performance and driving safety with the idea of “performing terrain analysis lazily, only along the sampled path”. By bundling interpretable plane-level metrics of slope, flatness, and sparsity, GPR uncertainty, and NMPC deceleration into a three-stage safety mechanism released as open source, it provided a reproducible baseline for subsequent uneven-terrain planning research.

From a robotics practice perspective, the takeaways are as follows.

  • Where it can be used: when a global and local planning stack that runs on CPU only, without a GPU, is needed for unstructured outdoor terrain driving. Since it is not a deep-learning model, no trained weights are needed, and two Gazebo simulation environments and a real-robot launch are provided, so simulation reproduction is relatively easy.
  • Reproduction difficulty is moderate: it depends on ROS1 (Ubuntu 16.04/18.04) and an A-LOAM build, and the real vehicle requires the Scout and LiDAR hardware plus calibration. The license is GPLv3, so derivative works also carry GPL obligations, requiring care when productizing.
  • Limits of the plane-fitting assumption: robustness on stairs, rocks, sharply non-planar terrain, or where vegetation disturbs the point cloud is unclear. Because local planning is reduced to 2D differential drive, rollover due to pitch and roll is handled only indirectly through the \(\tau\) penalty, not as an explicit dynamic constraint.
  • Scaling and tuning: as the number of tree nodes grows, the \(O(N^3)\) burden of GPR increases, and scalability on large maps is unverified. There is also little discussion of how much manual tuning the thresholds \(s_{crit}, f_{crit}, \lambda_{crit}\) and the weights \(\alpha\) require per terrain and robot.

References

  • Paper: arXiv 2203.04541 · Code: github.com/jianzhuozhuTHU/putn
  • Gammell et al., Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic (2014)
  • Karaman & Frazzoli, Sampling-based Algorithms for Optimal Motion Planning (2011)
  • Fan et al., STEP: Stochastic Traversability Evaluation and Planning for Risky Off-road Navigation (2021)
  • Krüsi et al., Driving on Point Clouds (2017)
  • Fankhauser et al., Probabilistic Terrain Mapping for Mobile Robots with Uncertain Localization (2018)