A decision tree learning hyper-heuristic for decision-making in simulated self-driving cars.

Abstract

This document describes a feasible way of implementing hyper-heuristics into self-driving cars for decision-making. Hyper-heuristics techniques are used as an automated procedure for selecting or generating among a set of low-level heuristics when solving a particular type of problem. This project aims to contribute and bridging the gap between the fields of self-driving cars and hyper-heuristics since there is not any known approach linking them together to date. The decision-making process for self-driving cars has been a trend in recent years. Thus, there exist a variety of techniques applied to path planning at the moment, such as A*, Dijkstra, Artificial Potential Field, Probabilistic Roadmap, Ant Colony, Particle Swarm Optimization, etc. However, since there is no information of the complete environment at the beginning of the trip and also fast dynamic measurements of the surroundings are obtained while a decision plan is raised, selection or combination among various low-level heuristics such as the path planning techniques mentioned above could be helpful, or perhaps to create new heuristics and this way build another branch for decision-making of autonomous vehicles as a path planning method. Hyper-Heuristic approach with the help of Machine learning techniques harnesses the past driving experience of a self-driving car, which results in an improvement of the decision-making of the vehicle to different kind of scenarios. This thesis proposes a hyper-heuristic approach for decision-making of a self-driving car on a highway with different types of traffic and real-life constraints. The hyper-heuristics model introduced is of a generative type; thus, it creates a most suitable heuristic to drive the car on the road based on previously existing heuristic methods. Information is obtained by the vehicle through different onboard sensors such as Radar, Camera, LIDAR, Stereo-vision, GPS and IMU that combined establish a sensor fusion approach. Experimental study of the algorithms is performed in a simulation environment for self-driving cars built on a Unity platform. The generation hyper-heuristic proposed has a Decision Tree classifier as a high-level heuristic, which will be in charge of generating a new heuristic from the low-level heuristics presented. The Decision Tree classifier is defined with the optimal hyper-parameters obtained by a Grid-search method. In this work, there is also an explanation of the simulator's setup environment since it has evolved from a robotics' building-from-scratch level to a self-driving car platform modified from an open source resource. Thus, creating a framework suitable for extraction of instances and implementation of hyper-heuristic results to a self-driving car. Finally, the result of the hyper-heuristic performance is compared against a Finite state machine defined with greedy instructions based on the current state of the car, three heuristics built for the project: left heuristic, center heuristic, right heuristic, and a human driver.