This content is not included in your SAE MOBILUS subscription, or you are not logged in.
APEX: Autonomous Vehicle Plan Verification and Execution
ISSN: 0148-7191, e-ISSN: 2688-3627
Published April 05, 2016 by SAE International in United States
Annotation ability available
Autonomous vehicles (AVs) have already driven millions of miles on public roads, but even the simplest scenarios have not been certified for safety. Current methodologies for the verification of AV’s decision and control systems attempt to divorce the lower level, short-term trajectory planning and trajectory tracking functions from the behavioral rules-based framework that governs mid-term actions. Such analysis is typically predicated on the discretization of the state space and has several limitations. First, it requires that a conservative buffer be added around obstacles such that many feasible plans are classified as unsafe. Second, the discretized controllers modeled in this analysis require several refinement steps before being implementable on an actual AV, and typically do not allow the specification of comfort-related properties on the trajectories. Consumer-ready AVs use motion planning algorithms that generate smooth trajectories. While viable algorithms exist for the generation of smooth trajectories originating from a single state, analysis should consider that the AV faces state estimation errors and disturbances. Verification is restricted to a discretized state space with fixed-size cells; this assumption can artificially limit the set of available trajectories if the discretization is too coarse. Conversely, too fine of a discretization renders the problem intractable for automated analysis. This work presents a new verification tool, APEX, which investigates the combined action of a behavioral planner and state lattice-based motion planner to guarantee a safe vehicle trajectory is chosen. In APEX, decisions made at the behavioral layer can be traced through to the spatio-temporal evolution of the AV and verified. Thus, there is no need to create abstractions of the AV’s controllers, and aggressive trajectories required for evasive maneuvers can be accurately investigated.
|Research Report||Unsettled Topics Concerning Sensors for Automated Road Vehicles|
|Magazine Issue||Automotive Engineering International 2013-04-02|
|Technical Paper||Reducing the Verification Effort for Interfaces of Automotive Infotainment Software|
CitationO'Kelly, M., Abbas, H., Gao, S., Kato, S. et al., "APEX: Autonomous Vehicle Plan Verification and Execution," SAE Technical Paper 2016-01-0019, 2016, https://doi.org/10.4271/2016-01-0019.
- Waldrop M. Mitchell. Autonomous vehicles: No drivers required. Nature, 518(7537): 20-23, feb 2015. doi: 10.1038/518020a. URL http://dx.doi.org/10.1038/518020a.
- Volvo press release: US urged to establish nationwide federal guidelines for autonomous driving. 2015.
- Humphrey Laura R, Wolff Eric M, and Topcu Ufuk. Formal specification and synthesis of mission plans for unmanned aerial vehicles. In AAAI Spring Symposium Series, 2014.
- Kato Shinpei, Takeuchi Eijiro, Ishiguro Yoshio, Ninomiya Yoshiki, Takeda Kazuya, and Hamada Tsuyoshi. An open approach to autonomous vehicles. Micro, IEEE, 35(6):60-68, Nov 2015. ISSN 0272-1732. doi: 10.1109/MM.2015.133.
- Alur Rajeev, Feder Tomas, and Henzinger Thomas A.. The benefits of relaxing punctuality. In Symposium on Principles of Distributed Computing, pages 139-152, 1991.
- Fletcher Luke, Teller Seth, Olson Edwin, Moore David, Kuwata Yoshiaki, How Jonathan, Leonard John, Miller Isaac, Campbell Mark, Huttenlocher Dan et al. The mit- cornell collision and why it happened. Journal of Field Robotics, 25(10):775-807, 2008.
- Urmson Chris, Anhalt Joshua, Bagnell Drew, Baker Christopher, Bittner Robert, Clark MN, Dolan John, Duggins Dave, Galatali Tugrul, Geyer Chris, et al. Autonomous driving in urban environments: Boss and the urban challenge. Journal of Field Robotics, 25(8):425-466, 2008.
- Wongpiromsarn Tichakorn, Topcu Ufuk, and Murray Richard M.. Receding horizon control for temporal logic specifications. In Proceedings of the 13th ACM International Conference on Hybrid Systems: Computation and Control, HSCC ’10, pages 101-110, New York, NY, USA, 2010. ACM. ISBN 978-1-60558-955-8. doi: 10.1145/1755952.1755968. URL http://doi.acm.org/10.1145/1755952.1755968.
- Nilsson Petter, Hussien Omar, Balkan Ayca, Chen Yuxiao, Ames Aaron D, Grizzle Jessy W, Ozay Necmiye, Peng Huei, and Tabuada Paulo. Correct-by-construction adaptive cruise control: Two approaches.
- Althoff Matthias and Dolan John M. Reachability computation of low-order models for the safety verification of high-order road vehicle models. In American Control Conference (ACC), 2012, pages 3559-3566. IEEE, 2012.
- Gat Erann. On three-layer architectures. In Artificial Intelligence and Mobile Robots. MIT Press, 1998.
- Kong Soonho, Gao Sicun, Chen Wei, and Clarke Edmund M.. dreach: Delta-reachability analysis for hybrid systems. In Tools and Algorithms for the Construction and Analysis of Systems - 21st International Conference, TACAS 2015, pages 200-205, 2015.
- Gao Sicun, Kong Soonho, Chen Wei, and Clarke Edmund. Delta-complete analysis for bounded reachability of hybrid systems. arXiv preprint arXiv:1404.7171, 2014.
- Rajamani Rajesh. Vehicle dynamics and control. Springer Science & Business Media, 2011.
- Althoff M. and Dolan J.M.. Online verification of automated road vehicles using reachability analysis. Robotics, IEEE Transactions on, 30(4):903-918, Aug 2014. ISSN 1552-3098. doi: 10.1109/TRO.2014.2312453.
- Snider Jarrod M. Automatic steering methods for autonomous automobile path tracking. Robotics Institute, Pittsburgh, PA, Tech. Rep. CMU-RITR-09-08, 2009.
- McNaughton Matthew. Parallel Algorithms for Real-time Motion Planning. PhD thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, July 2011.
- Nagy Bryan and Kelly Alonzo. Trajectory generation for car-like robots using cubic curvature polynomials. Field and Service Robots, 11, 2001.