Motion Planning for Muliple Autonomous Vehicles

Can’t afford a driver while feel lazy to drive yourself? Have one, but fed up of the daily excuses and bad driving? Your holiday could have been too exciting but wasted worrying about the road, traffic and parking rather than the scenic stuff? Too scared to drive at those rapid highways? Find travelling too sleepy to be driving carefully?

Well autonomous vehicles are coming to your rescue. This series gives you an insight into the technology and what all you could expect in the future. See for yourself if these vehicles can be smarter than you to quarrel with your competitors on road, navigate the most unmaintained and poorly structured roads and drive the hard Indian way!

Quick Links

Chapter 1 Introduction

Chapter 2 Literature Review

Chapters 3-6: Trajectory Generation

Key Contributions

• Various aspects of unorganized traffic (operating without lanes) are studied.
• The problem of trajectory planning for unorganized traffic in a diverse multi-vehicle scenario is studied, while the literature is largely focussed on the study of the organized counterpart.
• The algorithm framework is generalized to the cases in which traffic intermingles on both sides of a dual carriageway (or the vehicles partly occupy the wrong side) for higher traffic efficiency (usually implying overtaking).
• A new coordinate axis system called the road coordinate axis system is designed for enhanced performance with curved and variable width roads.

Part I: With Communication

Part II: Without Communication

Trajectory Generation with Communication

Chapter 3.2 Genetic Algorithm

Key Contributions:

• The design of a GA which gives results within low computational times for traffic scenarios.
• Employment of the developed GA for constant path adaptation to overcome actuation uncertainties. The GA assesses the current scenario and takes the best measures for rapid trajectory generation.
• The use of traffic rules as heuristics to coordinate between vehicles.
• The use of heuristics for constant adaptation of the plan to favour overtaking, once initiated, but to cancel it whenever infeasible.
• The approach is tested for a number of diverse behaviours including obstacle avoidance, blockage, overtaking and vehicle following.

Chapter 3.3: Rapidly-exploring Random Trees

Key Contributions:

• Inspired by the general motion of vehicles in traffic, a planning strategy is proposed which is biased towards a vehicle’s current lateral position. This enables better tree expansion and connectivity checks.
• RRT generation is integrated with spline based curve generation for curve smoothing.
• The approach is designed and tested for many and complex obstacles in the presence of multiple vehicles.

Chapter 3.4: Rapidly-exploring Random Trees Connect

Key Contributions:

• The planning algorithm can be used with very low computational requirements for very simple behaviours, while higher computation may enable near-optimal performance.
• A decision making module is proposed for choosing between vehicle following and overtaking behaviours. The module relies on a fast planning lookup.
• The algorithm uses the notion of first building an approximate path and then optimizing it which induces an iterative nature to the algorithm, unlike the standard RRT approaches which invest computation to build a precise path.
• The algorithm uses multiple RRT instances to be assured of being near global optima, which is largely possible due to the fast approximate path construction.

Chapter 4.2-4.3: Multi-Layer Planning

Key Contributions:

• To propose a general planning hierarchy in an assumed complex modelling scenario, where any algorithm may be used at any level of hierarchy.
• To use simple heuristics such as separation maximization, vehicle following and overtaking, to plan the trajectories of multiple vehicles in real time.
• An emphasis is placed on the width of feasible roads as an important factor in the decision making process.
• The developed coordination strategy is largely cooperative, at the same time ensuring near-completeness of the resultant approach and being near-optimal for most practical scenarios.

Chapter 4.4-4.6: Dynamic Distributed Lanes

Key Contributions:

• The generalized notion of lanes is defined.
• The generalized notion is used for planning and coordination of multiple vehicles.
• A pseudo centralized coordination technique is designed which uses the concepts of decentralized coordination for iteratively planning different vehicles but empowers a vehicle to move around the other vehicles. The coordination is hence better in terms of optimality and completeness than most approaches (discussed so far) while being somewhat computationally expensive in the worst cases.
• The concept of one vehicle waiting for another vehicle coming from the other direction is introduced, when there may be space enough for only one vehicle to pass.
• Heuristics are used for pruning the expansions of states, which result in a significant computational efficiency while leading to a slight loss of optimality.

Trajectory Generation without Communication

Chapter 5.1: Fuzzy Logic

Key Contributions:

• Design of a Fuzzy Inference System for the problem.
• Design of a decision making module for deciding the feasibility of overtaking purely based on the vehicle distances and speeds.
• Design of an evolutionary technique for optimization of such a fuzzy system.
• Using the designed fuzzy system enabling vehicles to travel through a crossing by introducing a virtual barricade.

Chapter 5.2: Lateral Potentials

Key Contributions:

• Modelling of lateral potentials suited for road scenarios to eliminate the known problems associated with the potential approaches.
• Modelling of potentials based on the principles of time to collision and cooperation apart from the distance measures for lateral planning of the vehicles.
• Use of obstacle and vehicle avoidance strategy parameters for higher order planning.
• Heuristic decision making in deciding these strategy parameters for real time planning.

Chapter 5.3: Elastic Strip

Key Contributions:

• Design of a method to quickly compute the optimal strategy for obstacle and vehicle avoidance, and the associated trajectory.
• Real-time optimization of the trajectory as the vehicle moves, making the resultant plan near-optimal.
• Using heuristics to ensure the travel plan is near-complete.
• Making the coordination strategy cooperative between vehicles.

Chapter 6: Logic-based Planning

Key Contributions:

• Vehicle behaviours in unorganized traffic are studied and identified.
• Each behaviour is modelled in an algorithm used for the motion of autonomous vehicles in unorganized traffic.
• In particular the complex behaviour of single lane overtaking is studied wherein a driver slips into the wrong lane to complete the overtake. The cases of initiation, cancelation and successful completion of the behaviour are studied.
• Driver aggression is studied and modelled as an algorithmic parameter in such traffic.

Chapters 3-6: Results

Chapters 7-8: Intelligent Management of the Transportation System

Key Contributions

• The study is based upon the notion of diversities, which may be speed based diversity or task based diversity.
• Both recurrent and non-recurrent traffic is studied to overcome congestion avoidance which means applicability to any region depending upon its dynamics.
• The different models studied vary from being mostly semi-autonomous to mostly non semi-autonomous, which covers all the stages of the evolution of traffic.
• Different traffic elements including traffic lights, lane changes and routing are incorporated in the study.

Chapter 7.2: Semi-Autonomous Intelligent Transportation System

Key Contributions:

• The approach presents an integrated study of an intelligent transportation system covering all the various concepts which are separately studied in the literature.
• The study proposes architecture of the transportation systems of the future covering both decentralized vehicle control and a centralized management control.
• The approach is designed for diverse semi-autonomous vehicles operating in a scalable environment, which is the likely future of the transportation system.
• The approach is a positive step towards creation of a traffic simulation tool for diverse and unorganized traffic.

Chapter 7.3: Congestion Avoidance in City Traffic

Key Contributions:

• Proposing city traffic as a scenario to study traffic congestion.
• Proposing the importance of considering traffic lights in decision making regarding routes.
• Proposing a simple routing algorithm that eliminates the high density of traffic and hence minimizes congestion.
• Stressing frequent short term re-planning of the vehicle in place of long term (complete) infrequent re-planning.

Chapter 8.2-8.3: Reaching Destination before Deadline with Intelligent Transportation Systems

Key Contributions:

• Decentralized agents at the intersections are proposed which record the traffic speeds and variations along with time. The use of centralized agents (or single agent systems) for such an approach is common, which is however not a scalable approach. The use of decentralized agents for traffic speeds is also common. Here recording an extra deviation factor helps in answering the user query.
• A new problem of start time prediction is studied, where a user may adapt the algorithm based on the penalty of late arrival. A single factor governs the performance. Guidelines enable a user to set the parameter.
• Using the existent notion of advanced driver information system, the twin problems of start time prediction and routing are solved.
• A graph search method is proposed to compute the route and the start time for the vehicle. The algorithm attempts to select a route which is the shortest in length, has a high reliability and gives the latest starting time.

Chapter 8.4-8.5: Reaching Destination before Deadline with Cooperative Intelligent Transportation Systems

Key Contributions:

• The notion of cooperative traffic lights is introduced which is biased to allow vehicles which are running late to pass through.
• The concept of cooperative lane changes is introduced by which a lane change attempts to minimize some vehicle from running late.
• Different states of a vehicle which desires to be on time are designed which include being comfortable on time, running a little late (may still reach even without cooperation), running very late (difficult to reach without cooperation) and impossible to reach (given up).
• A cost metric is designed which maps the different states of a vehicle running late to a consciousness of being late, used for decision making regarding all cooperative measures.

Chapter 9: Conclusions