Hierarchial Framework: Combination of Planners
In the previous article, the five types of planners were explained. In practice, it is very rare to use a single planner type for complex environments. This page introduces several examples of their combinations in recent papers. Most of the combinations consist of global planning and local planning.
1. Roadmap as Topological Guide
Although paths on a roadmap are too coarse and jerk to be directly tracked with a controller, they are good measures of possible topology until a goal. Based on this, multiple combinations are found in the search.
Roadmap + Sampling planner
Sampling-based planners might have difficulty with passing a narrow passage. The proposed planning in [1] builds a structured roadmap first and sampling only along a guide path, drastically reducing computation time at the cost of global optimality.
Roadmap + Search planner
Instead of relying on search based planner (Hybrid A*) to solve a path until a global goal, [2] reduces search complexity by solving multiple times to pursuit the intermediate goal obtained from the visibility graph. Similar to the previous combination, this can impair global optimality, as strictly passing through waypoints can be inefficient in a global sense.
Roadmap + Optimization
As pointed out here, the optimization planners are very sensitive to an initial guess. The gradient-based method will converge to local minimum around the initial guess. In many cases, the set of local minima can be associated with the set of different topologies until the goal, where the topological family can be estimated from a roadmap. Observing this intuition, [3] (car) and [4] (drone) solves multiple nonlinear optimizations for possible roads until the goal, and the best is selected as a good approximate of the global optimal. Refer the below figure [3].
2. Sampling Planners as Shortest Distance Guide
Relying on sampling based planners such as RRT* for high dimension systems can be inefficient as steering between two states might not be computed fast enough if we consider dynamics. The authors of [5] dealt with quadrotor system which is originally high-dimension problem. Instead of solving the entire problem in a single RRT* with kinematic steering, they proposed two steps: simple RRT* with the straight line steering + quadratic programming on polynomial coefficients.
In this figure, (a) depicts the result when RRT* is used with polynomial steering. That is, the entire path was computed using only RRT*. (b) -> (c) is the pipeline proposed, where a RRT* is first solved for the simplest steering and polynomial post-processing finalizes the trajectory. According to the paper [5], the former approach took more than 50 times than the latter.
3. Search Planners as Geometric Guide
Maybe this family is the most common combination, where search based planners gives a frontend geometric output and the optimization computes a feasible trajectory (time parameterized, dynamics considered).
Search Planners (Constraint) + Quadratic Programming
The paper [6] uses a simple A* algorithm to obtain a grid path toward goal. Then, a safe corridor (sequence of boxes) is computed by expanding boxes along the grid path. The next step is to generate a feasible trajectory confined to the boxes.
In general, a quadrotor can follow a polynomial trajectory if its high-order derivatives are small (jerk or snap minimization, source code (opens in a new tab)). If we represent the flight path with the polynomial, constraint of safe boxes and minimizing high order derivatives can be formulated into the quadratic programming w.r.t polynomial coefficients, which is known to be stably converged to the global optimal.
Search Planners (Objective) + Quadratic Programming
In addition to a safe region, search-based planners can provide a sequence of guiding points. The topic of my paper [7] was chasing a moving target with optimal visibility.
When some of the motion objectives are complex and their evaluation is expensive, we can first reflect them in high-quality waypoints and the remainder of objectives is further considered in the following numerical optimization.
In my paper, it was expensive to compute a good vantage point for observing two targets, as multiple factors should be considered simultaneously (see the left part of the figure). I used the Dijkstra algorithm to pick a good point for each discrete time step and then optimize polynomial trajectory to pursue the points while remaining in a corridor.
Here is a tutorial video of my paper.
Search Planners (Initial Guess) + Nonlinear Optimization
When solving complex motion for non-holonomic systems such as cars, one of the most common approaches is to mix hybrid A* (frontend) and nonlinear optimization for optimal control. The frontend determines motion phases such as when to move backward or forward. Then the discrete phases are tracked by dynamically feasible optimization. As an application, parking among complex obstacles can be solved by this approach as [9] and [10].
The original paper of Hybrid A* [11] post-processed the output of hybrid A* for further smoothing. As the path of Hybrid A* consists of discrete choices of steering, it can look jerky. Authors of [11] adopted the conjugate gradient method for smoothing and safety (see below figure).
4. Motion Primitive Library as Final Follower
To use the fifth type planner, a local goal over a short horizon is required, rather than using the global goal directly. As the below video shows, the primitive library planner for the car-like kinematics was used to track the path from a global planner.
The below video demonstrates a similar approach in 3D domains with other motion primitives.
[1] Seegmiller, Neal, et al. "The Maverick planner: An efficient hierarchical planner for autonomous vehicles in unstructured environments." 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2017.
[2] Sedighi, Saeid, Duong-Van Nguyen, and Klaus-Dieter Kuhnert. "Guided hybrid A-star path planning algorithm for valet parking applications." 2019 5th international conference on control, automation and robotics (ICCAR). IEEE, 2019.
[3] Rösmann, Christoph, Frank Hoffmann, and Torsten Bertram. "Integrated online trajectory planning and optimization in distinctive topologies." Robotics and Autonomous Systems 88 (2017): 142-153.
[4] Zhou, Boyu, et al. "Raptor: Robust and perception-aware trajectory replanning for quadrotor fast flight." IEEE Transactions on Robotics 37.6 (2021): 1992-2009.
[5] Richter, Charles, Adam Bry, and Nicholas Roy. "Polynomial trajectory planning for aggressive quadrotor flight in dense indoor environments." Robotics Research. Springer, Cham, 2016. 649-666.
[6] Chen, Jing, Tianbo Liu, and Shaojie Shen. "Online generation of collision-free trajectories for quadrotor flight in unknown cluttered environments." 2016 IEEE international conference on robotics and automation (ICRA). IEEE, 2016.
[7] B. Jeon, Y. Lee and H. J. Kim, "Integrated Motion Planner for Real-time Aerial Videography with a Drone in a Dense Environment," 2020 IEEE International Conference on Robotics and Automation (ICRA), Paris, France, 2020, pp. 1243-1249, doi: 10.1109/ICRA40945.2020.9196703.
[8] B. F. Jeon, Y. Lee, J. Choi, J. Park and H. J. Kim, "Autonomous Aerial Dual-Target Following Among Obstacles," in IEEE Access, vol. 9, pp. 143104-143120, 2021, doi: 10.1109/ACCESS.2021.3117314.
[9] Li, Bai, et al. "Optimization-based trajectory planning for autonomous parking with irregularly placed obstacles: A lightweight iterative framework." IEEE Transactions on Intelligent Transportation Systems 23.8 (2021): 11970-11981.
[10] Han, Zhichao, et al. "Differential flatness-based trajectory planning for autonomous vehicles." arXiv preprint arXiv:2208.13160 (2022).
[11] Dolgov, Dmitri, et al. "Path planning for autonomous vehicles in unknown semi-structured environments." The international journal of robotics research 29.5 (2010): 485-501.