Conflict detection and resolution for autonomous vehicles
Van Daalen, Corne Edwin · 2010
Autonomous vehicles have recently received much attention from researchers. The prospect of safe and reliable autonomous vehicles for general, unregulated environments promises several advantages over human-controlled vehicles, including increased efficiency, reliability and capability with the associated decrease in danger to humans and reduction in operating costs. A critical requirement for the safe operation of fully autonomous vehicles is their ability to avoid collisions with obstacles and other vehicles. In addition, they are often required to maintain a minimum separation from obstacles and other vehicles, which is called conflict avoidance. The research presented in thesis focuses on methods for effective conflict avoidance. Existing conflict avoidance methods either make limiting assumptions or cannot execute in real-time due to computational complexity. This thesis proposes methods for real-time conflict avoidance in uncertain, cluttered and dynamic environments. These methods fall into the category of non-cooperative conflict avoidance. They allow very general vehicle and environment models, with the only notable assumption being that the position and velocity states of the vehicle and obstacles have a jointly Gaussian probability distribution. Conflict avoidance for fully autonomous vehicles consists of three functions, namely modelling and identification of the environment, conflict detection and conflict resolution. We present an architecture for such a system that ensures stable operation. The first part of this thesis comprises the development of a novel and efficient probabilistic conflict detection method. This method processes the predicted vehicle and environment states to compute the probability of conflict for the prediction period. During the method derivation, we introduce the concept of the flow of probability through the boundary of the conflict region, which enables us to significantly reduce the complexity of the problem. The method also assumes Gaussian distributed states and defines a tight upper bound to the conflict probability, both of which further reduce the problem complexity, and then uses adaptive numerical integration for efficient evaluation. We present the results of two simulation examples which show that the proposed method can calculate in real-time the probability of conflict for complex and cluttered environments and complex vehicle maneuvers, offering a significant improvement over existing methods. The second part of this thesis adapts existing kinodynamic motion planning algorithms for conflict resolution in uncertain, dynamic and cluttered environments. We use probabilistic roadmap methods and suggest three changes to them, namely using probabilistic conflict detection methods, sampling the state-time space instead of the state space and batch generation of samples. In addition, we propose a robust and adaptive way to choose the size of the sampling space using a maximum least connection cost bound. We then put all these changes together in a proposed motion planner for conflict resolution. We present the results of two simulation examples which show that the proposed motion planner can only find a feasible path in real-time for simple and uncluttered environments. However, the manner in which we handle uncertainty and the sampling space bounds offer significant contributions to the conflict resolution field.