Enable faster and smoother spatio-temporal trajectory planning for autonomous vehicles in constrained dynamic environment

Abstract

Trajectory planning is of vital importance to decision-making for autonomous vehicles. Currently, there are three popular classes of cost-based trajectory planning methods: sampling-based, graph-search-based, and optimization-based. However, each of them has its own shortcomings, for example, high computational expense for sampling-based methods, low resolution for graph-search-based methods, and lack of global awareness for optimization-based methods. It leads to one of the challenges for trajectory planning for autonomous vehicles, which is improving planning efficiency while guaranteeing model feasibility. Therefore, this paper proposes a hybrid planning framework composed of two modules, which preserves the strength of both graph-search-based methods and optimization-based methods, thus enabling faster and smoother spatio-temporal trajectory planning in constrained dynamic environment. The proposed method first constructs spatio-temporal driving space based on directed acyclic graph and efficiently searches a spatio-temporal trajectory using the improved A* algorithm. Then taking the search result as reference, locally convex feasible driving area is designed and model predictive control is applied to further optimize the trajectory with a comprehensive consideration of vehicle kinematics and moving obstacles. Results simulated in four different scenarios all demonstrated feasible trajectories without emergency stop or abrupt steering change, which is kinematic-smooth to follow. Moreover, the average planning time was 31 ms, which only took 59.05%, 18.87%, and 0.69%, respectively, of that consumed by other state-of-the-art trajectory planning methods, namely, maximum interaction defensive policy, sampling-based method with iterative optimizations, and Graph-search-based method with Dynamic Programming.

Keywords

Spatio-temporal trajectory planning directed acyclic graph convex feasible set autonomous driving dynamic environment

Get full access to this article

View all access options for this article.

References

Xiang

. Robust control in diagonal move steer mode and experiment on an X-by-wire UGV. IEEE/ASME T Mech 2019; 24: 572–584.

Biao

Eben

Yougang

, et al. Distributed conflict-free cooperation for multiple connected vehicles at unsignalized intersections. Transport Res C: Emer 2018; 93: 322–334.

Liu

Hedrick

. Measurement dissemination-based distributed Bayesian filter using the latest-in-and-full-out exchange protocol for networked unmanned vehicles. IEEE T Ind Electron 2017; 64: 8756–8766.

Zhou

, et al. Robust path following control at driving/handling limits of an autonomous electric racecar. IEEE T Veh Technol 2019; 68: 5518–5526.

Guo

, et al. Performance enhanced predictive control for adaptive cruise control system considering road elevation information. IEEE T Intell Veh 2017; 2: 150–160.

Wang

, et al. Relaxed static stability for four-wheel independently actuated ground vehicle. Mech Syst Signal Pr 2019; 127: 35–49.

Gao

, et al. Robust longitudinal control of multi-vehicle systems—a distributed H-infinity method. IEEE T Intell Transp 2017; 19: 2779–2788.

, et al. Kalman filter-based tracking of moving objects using linear ultrasonic sensor array for road vehicles. Mech Syst Signal Pr 2018; 98: 173–189.

Frazzoli

Dahleh

Feron

. Real-time motion planning for agile autonomous vehicles. J Guid Control Dynam 2002; 25: 116–129.

10.

LaValle

. Rapidly-exploring random trees: a new tool for path planning. Technical report, TR98-11, 1998. Ames: Iowa State University (Department of Computer Science).

11.

Kuwata

Teo

Fiore

, et al. Real-time motion planning with applications to autonomous urban driving. IEEE T Contr Syst T 2009; 17: 1105–1118.

12.

Macfarlane

Croft

. Jerk-bounded manipulator trajectory planning: design for real-time applications. IEEE T Robotic Autom 2003; 19: 42–52.

13.

Dolan

Lee

. Automated tactical maneuver discovery, reasoning and trajectory planning for autonomous driving. In: Proceedings of the 2016 IEEE/RSJ international conference on intelligent robots and systems, Daejeon, South Korea, 9–14 October 2016, pp.5474–5480. New York: IEEE.

14.

Pivtoraiko

Knepper

Kelly

. Differentially constrained mobile robot motion planning in state lattices. J Field Robot 2009; 26: 308–333.

15.

Kushleyev

Likhachev

. Time-bounded lattice for efficient planning in dynamic environments. In: Proceedings of the 2009 IEEE international conference on robotics and automation, Kobe, Japan, 12–17 May 2009, pp.1662–1668. New York: IEEE.

16.

Bohren

Foote

Keller

, et al. Little Ben: the Ben Franklin racing team’s entry in the 2007 DARPA urban challenge. J Field Robot 2008; 25: 598–614.

17.

Montemerlo

Becker

Bhat

, et al. Junior: the Stanford entry in the urban challenge. J Field Robot 2008; 25: 569–597

18.

Ferguson

Howard

Likhachev

. Motion planning in urban environments. J Field Robot 2008; 25: 939–960.

19.

Rufli

Siegwart

. On the application of the D* search algorithm to time-based planning on lattice graphs. In: Proceedings of the 4th European conference on mobile robotics, Mlini/Dubrovnik, Croatia, 23–25 September 2009, pp.105–110. Zürich: Eidgenössische Technische Hochschule.

20.

Koenig

Likhachev

. Fast replanning for navigation in unknown terrain. IEEE T Robot 2005; 21: 354–363.

21.

Ziegler

Stiller

. Spatiotemporal state lattices for fast trajectory planning in dynamic on-road driving scenarios. In: Proceedings of the 2009 IEEE/RSJ international conference on intelligent robots and systems, St. Louis, MO, 11–15 October 2009, pp.1879–1884. New York: IEEE.

22.

. Improved trajectory planning for on-road self-driving vehicles via combined graph search, optimization & topology analysis. PhD Thesis, Carnegie Mellon University, Pittsburgh, PA, 2017.

23.

Shibata

Sugiyama

Wada

Collision avoidance control with steering using velocity potential field. In: Proceedings of the 2014 IEEE intelligent vehicles symposium, Dearborn, MI, 8–11 June 2014, pp.438–443. New York: IEEE.

24.

Keller

Hoffmann

Hass

, et al. Planning of optimal collision avoidance trajectories with timed elastic bands. IFAC Proc Vol 2014; 47: 9822–9827.

25.

Gao

Lin

Borrelli

, et al. Predictive control of autonomous ground vehicles with obstacle avoidance on slippery roads. In: Proceedings of the ASME 2010 dynamic systems and control conference, pp.265–272. New York: American Society of Mechanical Engineers.

26.

Karampiperis

Sampson

Adaptive instructional planning using ontologies. In: Proceedings of the 2004 IEEE international conference on advanced learning technologies, Joensuu, 30 August–1 September 2004, vol. 1, Cambridge, MA, 12–15 September 2010, pp.126–130. New York: IEEE.

27.

Xin

Wang

Chan

, et al. Intention-aware long horizon trajectory prediction of surrounding vehicles using dual LSTM networks. In: Proceedings of the 2018 21st international conference on intelligent transportation systems, Maui, HI, 4–7 November 2018, pp.1441–1446. New York: IEEE.

28.

Duchoň

Babinec

Kajan

, et al. Path planning with modified a star algorithm for a mobile robot. Procedia Engineer 2014; 96: 59–69.

29.

Xiang

. Envelope control for four-wheel independently actuated autonomous ground vehicle through AFS/DYC integrated control. IEEE T Veh Technol 2017; 66: 9712–9726.

30.

Liu

Lin

Tomizuka

. The convex feasible set algorithm for real time optimization in motion planning. SIAM J Control Optim 2018; 56: 2712–2733.

31.

Liu

Lin

Wang

, et al. Convex feasible set algorithm for constrained trajectory smoothing. In: Proceedings of the 2017 American control conference, Seattle, WA, 24–26 May 2017, pp.4177–4182. New York: IEEE.

32.

Bing

Gang

Jiang

, et al. A route planning method based on improved artificial potential field algorithm. In: Proceedings of the 2011 IEEE 3rd international conference on communication software and networks, Xi’an, China, 27–29 May 2011, pp.550–554. New York: IEEE.

33.

Chen

Tang

Xin

, et al. Continuous decision making for on-road autonomous driving under uncertain and interactive environments. In: Proceedings of the 2018 IEEE intelligent vehicles symposium, vol. 68, Changshu, China, 26–30 June 2018, pp.1651–1658. New York: IEEE.

34.

Wei

Dolan

, et al. A real-time motion planner with trajectory optimization for autonomous vehicles. In: Proceedings of the 2012 IEEE international conference on robotics and automation, Saint Paul, MN, 14–18 May 2012, pp.2061–2067. New York: IEEE.