A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles
---
paper_title: Handbook of Intelligent Vehicles

paper_content:

Traffic Statistics and Challenges.- Introduction of Relevant Vehicular Systems and Control Functions.- Overview of Intelligent Vehicle Systems and Approaches.- Sensing and Situational Awareness.- Sensory Requirements: External, Internal, Positioning and Condition Monitoring.- Driver Assistance.- Trip Planning, Navigation, and Trajectory Control.- Advanced Control and Decision Systems.- Safety and Comfort Systems.- Drowsy and Fatigue Driver Detection, Monitoring, and Warning.- Computer Vision Systems and Algorithms.- Vehicular Communications Systems.- Drive-By-Wire.- Fully Autonomous Driving.- A Look to the Future.
---
paper_title: Survey of Pedestrian Detection for Advanced Driver Assistance Systems

paper_content:

Advanced driver assistance systems (ADASs), and particularly pedestrian protection systems (PPSs), have become an active research area aimed at improving traffic safety. The major challenge of PPSs is the development of reliable on-board pedestrian detection systems. Due to the varying appearance of pedestrians (e.g., different clothes, changing size, aspect ratio, and dynamic shape) and the unstructured environment, it is very difficult to cope with the demanded robustness of this kind of system. Two problems arising in this research area are the lack of public benchmarks and the difficulty in reproducing many of the proposed methods, which makes it difficult to compare the approaches. As a result, surveying the literature by enumerating the proposals one--after-another is not the most useful way to provide a comparative point of view. Accordingly, we present a more convenient strategy to survey the different approaches. We divide the problem of detecting pedestrians from images into different processing steps, each with attached responsibilities. Then, the different proposed methods are analyzed and classified with respect to each processing stage, favoring a comparative viewpoint. Finally, discussion of the important topics is presented, putting special emphasis on the future needs and challenges.
---
paper_title: Critical Reasons for Crashes Investigated in the National Motor Vehicle Crash Causation Survey

paper_content:

The National Motor Vehicle Crash Causation Survey (NMVCCS), conducted from 2005 to 2007, was aimed at collecting on-scene information about the events and associated factors leading up to crashes involving light vehicles. Several facets of crash occurrence were investigated during data collection, namely the pre-crash movement, critical pre-crash event, critical reason, and the associated factors. A weighted sample of 5,470 crashes was investigated over a period of two and a half years, which represents an estimated 2,189,000 crashes nationwide. About 4,031,000 vehicles, 3,945,000 drivers, and 1,982,000 passengers were estimated to have been involved in these crashes. The critical reason, which is the last event in the crash causal chain, was assigned to the driver in 94 percent (±2.2%)† of the crashes. In about 2 percent (±0.7%) of the crashes, the critical reason was assigned to a vehicle component’s failure or degradation, and in 2 percent (±1.3%) of crashes, it was attributed to the environment (slick roads, weather, etc.). Among an estimated 2,046,000 drivers who were assigned critical reasons, recognition errors accounted for about 41 percent (±2.1%), decision errors 33 percent (±3.7%), and performance errors 11 percent (±2.7%) of the crashes.
---
paper_title: Vehicles Capable of Dynamic Vision

paper_content:

Survey of artificial intelligence applications to vehicular computer vision including aircraft and ground vehicles
---
paper_title: Model-Based Threat Assessment for Avoiding Arbitrary Vehicle Collisions

paper_content:

This paper presents a model-based algorithm that estimates how the driver of a vehicle can either steer, brake, or accelerate to avoid colliding with an arbitrary object. In this algorithm, the motion of the vehicle is described by a linear bicycle model, and the perimeter of the vehicle is represented by a rectangle. The estimated perimeter of the object is described by a polygon that is allowed to change size, shape, position, and orientation at sampled time instances. Potential evasive maneuvers are modeled, parameterized, and approximated such that an analytical expression can be derived to estimate the set of maneuvers that the driver can use to avoid a collision. This set of maneuvers is then assessed to determine if the driver needs immediate assistance to avoid or mitigate an accident. The proposed threat-assessment algorithm is evaluated using authentic data from both real traffic conditions and collision situations on a test track and by using simulations with a detailed vehicle model. The evaluations show that the algorithm outperforms conventional threat-assessment algorithms at rear-end collisions in terms of the timing of autonomous brake activation. This is crucial for increasing the performance of collision-avoidance systems and for decreasing the risk of unnecessary braking. Moreover, the algorithm is computationally efficient and can be used to assist the driver in avoiding or mitigating collisions with all types of road users in all kinds of traffic scenarios.
---
paper_title: The VisLab Intercontinental Autonomous Challenge: An Extensive Test for a Platoon of Intelligent Vehicles

paper_content:

This paper presents the VisLab Intercontinental Autonomous Challenge (VIAC), an autonomous vehicles test carried out from Parma to Shanghai between July and October 2010 by the VisLab team. The vehicle equipment is explained introducing the sensing systems which were tested during the journey. Trip details and the first statistics are presented as well.
---
paper_title: Vehicle dynamics and control

paper_content:

1. Introduction.- 2.Lateral Vehicle Dynamics.- 3. Steering Control For Automated Lane Keeping.- 4. Longitudinal Vehicle Dynamics.- 5. Introduction to Longitudinal Control.- 6. Adaptive Cruise Control.- 7. Longitudinal Control for Vehicle Platoons.- 8. Electronic Stability Control.- 9. Mean Value Modeling Of SI and Diesel Engines.- 10. Design and Analysis of Passive Automotive Suspensions.- 11. Active Automotive Suspensions.-12. Semi-Active Suspensions.- 13. Lateral and Longitudinal Tires Forces.- 14. Tire-Road Friction Measurement on Highway Vehicles.- 15. Roll Dynamics and Rollover Prevention.- 16. Dynamics and Control of Hybrid Gas Electric Vehicles.
---
paper_title: Cooperative Collision Avoidance at Intersections: Algorithms and Experiments

paper_content:

In this paper, we leverage vehicle-to-vehicle (V2V) communication technology to implement computationally efficient decentralized algorithms for two-vehicle cooperative collision avoidance at intersections. Our algorithms employ formal control theoretic methods to guarantee a collision-free (safe) system, whereas overrides are only applied when necessary to prevent a crash. Model uncertainty and communication delays are explicitly accounted for by the model and by the state estimation algorithm. The main contribution of this work is to provide an experimental validation of our method on two instrumented vehicles engaged in an intersection collision avoidance scenario in a test track.
---
paper_title: A UNIFIED APPROACH TO DRIVER ASSISTANCE SYSTEMS BASED ON ARTIFICIAL POTENTIAL FIELDS

paper_content:

This paper presents an approach to vehicle control based upon the paradigm of artificial potential fields. Using this method, the dynamics of the vehicle are coupled with the environment in a manner that ensures that the system exhibits safe motion in the absence of driver inputs. The driver remains in control of the vehicle, however, with the control systems presenting a predictable and safe set of dynamics. With the control approach presented here, integration of various assistance systems can be easily achieved through simple superposition of individual potential and damping functions. A simple example of a combined lanekeeping and stability system demonstrates how this can be accomplished. Preliminary simulation results suggest that both safety and driveability are achievable with such a system, prompting further investigation.
---
paper_title: PROUD—Public Road Urban Driverless-Car Test

paper_content:

This paper presents an autonomous driving test held in Parma on urban roads and freeways open to regular traffic. During this test, the vehicle not only performed simple maneuvers, but it had to cope with complex driving scenarios as well, including roundabouts, junctions, pedestrian crossings, freeway junctions, and traffic lights. The test demonstrated the ability of the current technology to manage real situations and not only the well-structured and predictable ones. A comparison of milestones, challenges, and key results in autonomous driving is presented to highlight the novelty and the specific purpose of the test. The whole system is described: the vehicle; the software architecture; details about high-, medium-, and low-level control; and details about perception algorithms. A conclusion highlights the achieved results and draws possible directions for future development.
---
paper_title: Making Bertha Drive—An Autonomous Journey on a Historic Route

paper_content:

125 years after Bertha Benz completed the first overland journey in automotive history, the Mercedes Benz S-Class S 500 INTELLIGENT DRIVE followed the same route from Mannheim to Pforzheim, Germany, in fully autonomous manner. The autonomous vehicle was equipped with close-to-production sensor hardware and relied solely on vision and radar sensors in combination with accurate digital maps to obtain a comprehensive understanding of complex traffic situations. The historic Bertha Benz Memorial Route is particularly challenging for autonomous driving. The course taken by the autonomous vehicle had a length of 103 km and covered rural roads, 23 small villages and major cities (e.g. downtown Mannheim and Heidelberg). The route posed a large variety of difficult traffic scenarios including intersections with and without traffic lights, roundabouts, and narrow passages with oncoming traffic. This paper gives an overview of the autonomous vehicle and presents details on vision and radar-based perception, digital road maps and video-based self-localization, as well as motion planning in complex urban scenarios.
---
paper_title: Classification of Highway Lane Change Behavior to Detect Dangerous Cut-in Maneuvers

paper_content:

Recognizing dangerous driver behavior is an essential part of predicting accurate vehicle trajectories in vehicle active safety systems. This paper proposes a lane change behavior classification approach to detect dangerous cut-in behaviors on highways. First, a probabilistic lane change behavior classifier is proposed based on Hidden Markov Models (HMMs). Then, time series data of lane changing vehicles from both normal and dangerous driving data sets are analyzed and compared to extract decisive features that are more likely to appear in dangerous lane change processes. A feature detection module is proposed specifically considering decisive features correlated to dangerous lane change. Furthermore, the feature detection module is integrated into the HMM classifier to enhance classification ability. The proposed classifier is verified with a separate test data set, and shows satisfactory results in reducing false negative rate of misclassification.
---
paper_title: Computer vision at the hyundai autonomous challenge

paper_content:

As interest on autonomous vehicles is growing worldwide, different approaches, based on different perception technologies and concepts, are being followed. This paper exposes the importance of the use of vision technology in most of these approaches, and presents the experience of the SNUCLE autonomous vehicle which successfully completed the Hyundai Autonomous Challenge in November 2010.
---
paper_title: Traffic congestion, driver stress, and driver aggression

paper_content:

Automobile drivers were interviewed over cellular telephones in high- and low-congestion conditions during a single commute. During each interview, state measures of driver stress and driver behaviors were obtained. Behavior responses were subdivided into 6 categories: aggressive, information seeking, planning, minor self-destructive, distraction, and relaxation techniques. Both state driver stress and aggression were greater in high- than in low-congestion conditions. No other behavior category differed between low and high congestion. Multiple regressions were calculated to determine predictors of state driver stress. In low congestion, time urgency predicted state driver stress, while aggression predicted driver stress in high congestion. In both conditions, a trait susceptibility toward viewing driving as stressful was predictive of state driver stress levels, further strengthening the use of the Driving Behaviour Inventory--General as a predictor of "trait" driver stress. Females and males did not differentiate on state stress or any behavior category.
---
paper_title: Parsimonious shooting heuristic for trajectory control of connected automated traffic part I: Theoretical analysis with generalized time geography

paper_content:

This paper studies a problem of controlling trajectories of a platoon of vehicles on a highway segment with connected and automated vehicles. This problem is complex because each vehicle trajectory is an infinite-dimensional object and neighboring trajectories have complex interactions (e.g., car-following behavior). A parsimonious shooting heuristic algorithm is proposed to construct vehicle trajectories on a signalized highway segment that comply with boundary conditions for vehicle arrivals, vehicle mechanical limits, traffic lights and vehicle following safety. This algorithm breaks each vehicle trajectory into a few sections and each is analytically solvable. This decomposes the original hard trajectory control problem to a simple constructive heuristic. Then we slightly adapt this shooting heuristic algorithm to efficiently solve a leading vehicle problem on an uninterrupted freeway. To study theoretical properties of the proposed algorithms, the time geography theory is generalized by considering finite accelerations. With this generalized theory, it is found that under mild conditions, these algorithms can always obtain a feasible solution to the original complex trajectory control problem. Further, we discover that the shooting heuristic solution is a generalization of the solution to the classic kinematic wave theory by incorporating finite accelerations. We identify the theoretical bounds to the difference between the shooting heuristic solution and the kinematic wave solution. Numerical experiments are conducted to verify the theoretical results and to draw additional insights into the potential of trajectory control in improving traffic performance. Building upon this foundation, an optimization framework will be presented in a following paper as Part II of this study.
---
paper_title: Provable Systemwide Safety in Intelligent Intersections

paper_content:

The automation of driving tasks is of increasing interest for highway traffic management. The emerging technologies of global positioning and intervehicular wireless communications, combined with in-vehicle computation and sensing capabilities, can potentially provide remarkable improvements in safety and efficiency. We address the problem of designing intelligent in-tersections, where traffic lights and stop signs are removed, and cars negotiate the intersection through an interaction of centralized and distributed decision making. Intelligent intersections are representative of complex hybrid systems that are increasingly of interest, where the challenge is to design tractable distributed algorithms that guarantee safety and provide good performance. Systems of automatically driven vehicles will need an under lying collision avoidance system with provable safety properties to be acceptable. This condition raises several challenges. We need to ensure perpetual collision avoidance so that cars do not get into future problematic positions to avoid an immediate collision. The architecture needs to allow distributed freedom of action to cars yet should guard against worst-case behavior of other cars to guarantee collision avoidance. The algorithms should be tractable both computationally and in information requirements and robust to uncertainties in sensing and communication. To address these challenges, we propose a hybrid architecture with an appropriate interplay between centralized coordination and distributed freedom of action. The approach is built around a core where each car has an infinite horizon contingency plan, which is updated at each sampling instant and distributed by the cars, in a computationally tractable manner. We also define a dynamically changing partial-order relation between cars, which specifies, for each car, a set of cars whose worst-case behaviors it should guard against. The architecture is hybrid, involving a centralized component that coordinates intersection traversals. We prove the safety and liveness of the overall scheme. The mathematical challenge of accurately quantifying performance remains as a difficult challenge; therefore, we conduct a simulation study that shows the benefits over stop signs and traffic lights. It is hoped that our effort can provide methodologies for the design of tractable solutions for complex distributed systems that require safety and liveness guarantees.
---
paper_title: Polling-systems-based control of high-performance provably-safe autonomous intersections

paper_content:

The rapid development of autonomous vehicles spurred a careful investigation of the potential benefits of all-autonomous transportation networks. Most studies conclude that autonomous systems can enable drastic improvements in performance. A widely studied concept is all-autonomous, collision-free intersections, where vehicles arriving in a traffic intersection with no traffic light adjust their speeds to cross through the intersection as quickly as possible. In this paper, we propose a coordination control algorithm for this problem, assuming stochastic models for the arrival times of the vehicles. The proposed algorithm provides provable guarantees on safety and performance. More precisely, it is shown that no collisions occur surely, and moreover a rigorous upper bound is provided for the expected wait time. The algorithm is also demonstrated in simulations. The proposed algorithms are inspired by polling systems. In fact, the problem studied in this paper leads to a new polling system where customers are subject to differential constraints, which may be interesting in its own right.
---
paper_title: Dynamic monocular machine vision

paper_content:

A new approach to real-time machine vision in dynamic scenes is presented based on special hardware and methods for feature extraction and information processing. Using integral spatio-temporal models, it by-passes the nonunique inversion of the perspective projection by applying recursive least squares filtering. By prediction error feedback methods similar to those used in modern control theory, all spatial state variables including the velocity components are estimated. Only the last image of the sequence needs to be evaluated, thereby alleviating the real-time image sequence processing task.
---
paper_title: Research advances in intelligent collision avoidance and adaptive cruise control

paper_content:

This paper looks into recent developments and research trends in collision avoidance/warning systems and automation of vehicle longitudinal/lateral control tasks. It is an attempt to provide a bigger picture of the very diverse, detailed and highly multidisciplinary research in this area. Based on diversely selected research, this paper explains the initiatives for automation in different levels of transportation system with a specific emphasis on the vehicle-level automation. Human factor studies and legal issues are analyzed as well as control algorithms. Drivers' comfort and well being, increased safety, and increased highway capacity are among the most important initiatives counted for automation. However, sometimes these are contradictory requirements. Relying on an analytical survey of the published research, we will try to provide a more clear understanding of the impact of automation/warning systems on each of the above-mentioned factors. The discussion of sensory issues requires a dedicated paper due to its broad range and is not addressed in this paper.
---
paper_title: The 2005 DARPA Grand Challenge: The Great Robot Race

paper_content:

The DARPA Grand Challenge was a landmark in the field of robotics: a race by autonomous vehicles through 132 miles of rough, cross-country Nevada terrain that showcased exciting and unprecedented capabilities in robotic perception, navigation, and control. The event took place in October 2005, and drew teams of competitors from academia and industry, and many garage hobbyists. This book presents fifteen technical papers that are written at a level that makes them easily accessible to a broad technical audience, describing the technology behind most of the robotic vehicles that participated in this famous race. The papers describe each team's driverless vehicle, race strategy, and insights. As a whole, they present the state of the art in autonomous vehicle technology, and offer a glimpse of future technology for tomorrows driverless cars. This book will serve as an authoritative, archival source for the DARPA Grand Challenge and a must have for robotics students and researchers, since it describes the state of the art in perception, planning and control.
---
paper_title: Exact Routing in Large Road Networks Using Contraction Hierarchies

paper_content:

Contraction hierarchies are a simple approach for fast routing in road networks. Our algorithm calculates exact shortest paths and handles road networks of whole continents. During a preprocessing step, we exploit the inherent hierarchical structure of road networks by adding shortcut edges. A subsequent modified bidirectional Dijkstra algorithm can then find a shortest path in a fraction of a millisecond, visiting only a few hundred nodes. This small search space makes it suitable to implement it on a mobile device. We present a mobile implementation that also handles changes in the road network, like traffic jams, and that allows instantaneous routing without noticeable delay for the user. Also, an algorithm to calculate large distance tables is currently the fastest if based on contraction hierarchies.
---
paper_title: Route Planning in Transportation Networks

paper_content:

We survey recent advances in algorithms for route planning in transportation networks. For road networks, we show that one can compute driving directions in milliseconds or less even at continental scale. A variety of techniques provide different trade-offs between preprocessing effort, space requirements, and query time. Some algorithms can answer queries in a fraction of a microsecond, while others can deal efficiently with real-time traffic. Journey planning on public transportation systems, although conceptually similar, is a significantly harder problem due to its inherent time-dependent and multicriteria nature. Although exact algorithms are fast enough for interactive queries on metropolitan transit systems, dealing with continent-sized instances requires simplifications or heavy preprocessing. The multimodal route planning problem, which seeks journeys combining schedule-based transportation (buses, trains) with unrestricted modes (walking, driving), is even harder, relying on approximate solutions even for metropolitan inputs.
---
paper_title: Computing the shortest path: A search meets graph theory

paper_content:

We propose shortest path algorithms that use A* search in combination with a new graph-theoretic lower-bounding technique based on landmarks and the triangle inequality. Our algorithms compute optimal shortest paths and work on any directed graph. We give experimental results showing that the most efficient of our new algorithms outperforms previous algorithms, in particular A* search with Euclidean bounds, by a wide margin on road networks and on some synthetic problem families.
---
paper_title: Intention-Aware Motion Planning

paper_content:

As robots venture into new application domains as autonomous vehicles on the road or as domestic helpers at home, they must recognize human intentions and behaviors in order to operate effectively. This paper investigates a new class of motion planning problems with uncertainty in human intention. We propose a method for constructing a practical model by assuming a finite set of unknown intentions. We first construct a motion model for each intention in the set and then combine these models together into a single Mixed Observability Markov Decision Process (MOMDP), which is a structured variant of the more common Partially Observable Markov Decision Process (POMDP). By leveraging the latest advances in POMDP/MOMDP approximation algorithms, we can construct and solve moderately complex models for interesting robotic tasks. Experiments in simulation and with an autonomous vehicle show that the proposed method outperforms common alternatives because of its ability in recognizing intentions and using the information effectively for decision making.
---
paper_title: Probabilistic MDP-behavior planning for cars

paper_content:

This paper presents a method for high-level decision making in traffic environments. In contrast to the usual approach of modeling decision policies by hand, a Markov Decision Process (MDP) is employed to plan the optimal policy by assessing the outcomes of actions. Using probability theory, decisions are deduced automatically from the knowledge about how road users behave over time. This approach does neither depend on an explicit situation recognition nor is it limited to only a variety of situations or types of descriptions. Hence it is versatile and powerful. The contribution of this paper is a mathematical framework to derive abstract symbolic states from complex continuous temporal models encoded as Dynamic Bayesian Networks (DBN). For this purpose discrete MDP states are interpreted by random variables. To make computation feasible this space grows adaptively during planning and according to the problem to be solved.
---
paper_title: Probabilistic online POMDP decision making for lane changes in fully automated driving

paper_content:

The Stadtpilot project aims at fully automated driving on Braunschweig's inner city ring road. The TU Braunschweig's research vehicle “Leonie” is one of the first vehicles having the ability of fully automated driving in real urban traffic scenarios. This paper shows our decision making approach for performing lane changes while driving fully automated in urban environments. We apply an online Partially Observable Markov Decision Process (POMDP) to accommodate inevitable sensor noise to be faced in urban traffic scenarios. In this paper we propose a two step algorithm to keep the complexity of the POMDP low enough for real-time decision making while driving. The presented approach has been integrated in our vehicle and was evaluated in real urban traffic.
---
paper_title: Discrete and Continuous, Probabilistic Anticipation for Autonomous Robots in Urban Environments

paper_content:

This paper develops a probabilistic anticipation algorithm for dynamic objects observed by an autonomous robot in an urban environment. Predictive Gaussian mixture models are used due to their ability to probabilistically capture continuous and discrete obstacle decisions and behaviors; the predictive system uses the probabilistic output (state estimate and covariance) of a tracking system and map of the environment to compute the probability distribution over future obstacle states for a specified anticipation horizon. A Gaussian splitting method is proposed based on the sigma-point transform and the nonlinear dynamics function, which enables increased accuracy as the number of mixands grows. An approach to caching elements of this optimal splitting method is proposed, in order to enable real-time implementation. Simulation results and evaluations on data from the research community demonstrate that the proposed algorithm can accurately anticipate the probability distributions over future states of nonlinear systems.
---
paper_title: Modelling of traffic situations at urban intersections with probabilistic non-parametric regression

paper_content:

Driving intention recognition and trajectory prediction of moving vehicles are two important requirements of future advanced driver assistance systems (ADAS) for urban intersections. In this paper, we present a consistent framework for solving these two problems. The key idea is to model the spatio-temporal dependencies of traffic situations with a two-dimensional Gaussian process regression. With this representation the driving intention can be recognized by evaluating the data likelihood for each individual regression model. For the trajectory prediction purpose, we transform these regression models into the corresponding dynamical models and combine them with Unscented Kalman Filters (UKF) to overcome the non-linear issue. We evaluate our framework with data collected from real traffic scenarios and show that our approach can be used for recognition of different driving intentions and for long-term trajectory prediction of traffic situations occurring at urban intersections.
---
paper_title: Generalized innovation and inference algorithms for hidden mode switched linear stochastic systems with unknown inputs

paper_content:

In this paper, we propose inference algorithms for simultaneously estimating the mode, input and state of hidden mode switched linear stochastic systems with unknown inputs. First, we define the generalized innovation for the recently proposed optimal filter for simultaneous input and state estimation [1] and show that the sequence is a Gaussian white noise. Then, we utilize this whiteness property of the generalized innovation, which reflects the estimation quality to form the likelihood function of the system model. Consequently, we employ the multiple model (MM) approach based on the likelihood function for inferring the hidden mode of switched linear stochastic systems. Algorithms for both static and dynamic MM estimation are presented and compared using a simulation example of vehicles at an intersection with switching driver intentions.
---
paper_title: Nonholonomic motion planning: Steering using sinusoids

paper_content:

Methods for steering systems with nonholonomic c.onstraints between arbitrary configurations are investigated. Suboptimal trajectories are derived for systems that are not in canonical form. Systems in which it takes more than one level of bracketing to achieve controllability are considered. The trajectories use sinusoids at integrally related frequencies to achieve motion at a given bracketing level. A class of systems that can be steered using sinusoids (claimed systems) is defined. Conditions under which a class of two-input systems can be converted into this form are given. >
---
paper_title: Vehicles Capable of Dynamic Vision

paper_content:

Survey of artificial intelligence applications to vehicular computer vision including aircraft and ground vehicles
---
paper_title: Vehicle dynamics and control

paper_content:

1. Introduction.- 2.Lateral Vehicle Dynamics.- 3. Steering Control For Automated Lane Keeping.- 4. Longitudinal Vehicle Dynamics.- 5. Introduction to Longitudinal Control.- 6. Adaptive Cruise Control.- 7. Longitudinal Control for Vehicle Platoons.- 8. Electronic Stability Control.- 9. Mean Value Modeling Of SI and Diesel Engines.- 10. Design and Analysis of Passive Automotive Suspensions.- 11. Active Automotive Suspensions.-12. Semi-Active Suspensions.- 13. Lateral and Longitudinal Tires Forces.- 14. Tire-Road Friction Measurement on Highway Vehicles.- 15. Roll Dynamics and Rollover Prevention.- 16. Dynamics and Control of Hybrid Gas Electric Vehicles.
---
paper_title: Control of chained systems application to path following and time-varying point-stabilization of mobile robots

paper_content:

Chain form systems have recently been introduced to model the kinematics of a class of nonholonomic mechanical systems. The first part of the study is centered on control design and analysis for nonlinear systems which can be converted to the chain form. Solutions to various control problems (open-loop steering, partial or complete state feedback stabilization) are either recalled, generalized, or developed. In particular, globally stabilizing time-varying feedbacks are derived, and a discussion of their convergence properties is provided. Application to the control of nonholonomic wheeled mobile robots is described in the second part of the study by considering the case of a car pulling trailers. >
---
paper_title: Tyre Modelling for Use in Vehicle Dynamics Studies

paper_content:

A new way of representing tyre data obtained from measurements in pure cornering and pure braking conditions has been developed in order to further improve the Dynamic Safety of vehicles. The method makes use of a formula with coefficients which describe some of the typifying quantities of a tyre, such as slip stiffnesses at zero slip and force and torque peak values. The formula is capable of describing the characteristics of side force, brake force and self aligning torque with great accuracy. This mathematical representation is limited to steady-state conditions during either pure cornering or pure braking and forms the basis for a model describing tyre behaviour during combined braking and cornering.
---
paper_title: Minimum Time vs Maximum Exit Velocity Path Optimization During Cornering

paper_content:

Numerical optimization has been used as an extension of vehicle dynamics simulation in order to repro- duce trajectories and driving techniques used by expert race drivers and investigate the effects of several vehicle param- eters in the stability limit operation of the vehicle. In this work we investigate how different race-driving techniques may be reproduced by considering different optimization cost functions. We introduce a bicycle model with suspension dynamics and study the role of the longitudinal load transfer in limit vehicle operation, i.e., when the tires operate at the adhesion limit. Finally we demonstrate that for certain vehicle configurations the optimal trajectory may include large slip angles (drifting), which matches the techniques used by rally-race drivers. I. INTRODUCTION
---
paper_title: Real-Time Motion Planning With Applications to Autonomous Urban Driving

paper_content:

This paper describes a real-time motion planning algorithm, based on the rapidly-exploring random tree (RRT) approach, applicable to autonomous vehicles operating in an urban environment. Extensions to the standard RRT are predominantly motivated by: 1) the need to generate dynamically feasible plans in real-time; 2) safety requirements; 3) the constraints dictated by the uncertain operating (urban) environment. The primary novelty is in the use of closed-loop prediction in the framework of RRT. The proposed algorithm was at the core of the planning and control software for Team MIT's entry for the 2007 DARPA Urban Challenge, where the vehicle demonstrated the ability to complete a 60 mile simulated military supply mission, while safely interacting with other autonomous and human driven vehicles.
---
paper_title: Computing minimum lap-time trajectories for a single-track car with load transfer

paper_content:

In this paper we address the minimum lap-time problem for a single-track rigid car which includes tire models and load transfer. Given a planar track including lane boundaries, our goal is to find a trajectory of the car minimizing the lap time subject to tire and steering limits. By using a new set of coordinates, the time-dependent system is transformed into a “space-dependent” (and space-variant) system. The choice of a suitable set of coordinates and the partition of the dynamics into a “longitudinal” one and a “transverse” one, allows us to convert the minimum time problem into a fixed horizon constrained optimal control problem. Based on a projection operator nonlinear optimal control technique, we propose a minimum lap-time strategy to push the rigid car to the limit of its handling capabilities. Finally, we provide numerical computations that: (i) show the effectiveness of the proposed strategy, and (ii) allow us to highlight important features of minimum lap-time trajectories.
---
paper_title: Nonholonomic motion planning: Steering using sinusoids

paper_content:

Methods for steering systems with nonholonomic c.onstraints between arbitrary configurations are investigated. Suboptimal trajectories are derived for systems that are not in canonical form. Systems in which it takes more than one level of bracketing to achieve controllability are considered. The trajectories use sinusoids at integrally related frequencies to achieve motion at a given bracketing level. A class of systems that can be steered using sinusoids (claimed systems) is defined. Conditions under which a class of two-input systems can be converted into this form are given. >
---
paper_title: Optimal paths for a car that goes both forwards and backwards

paper_content:

The path taken by a car with a given minimum turning radius has a lower bound on its radius of curvature at each point, but the path has cusps if the car shifts into or out of reverse gear. What is the shortest such path a car can travel between two points if its starting and ending directions are specified? One need consider only paths with at most 2 cusps or reversals
---
paper_title: New methods for computing visibility graphs

paper_content:

Let S be a set of n non-intersecting line segments in the plane. The visibility graph G S of S is the graph that has the endpoints of the segments in S as nodes and in which two nodes are adjacent whenever they can “see” each other (i.e., the open line segment joining them is disjoint from all segments or is contained in a segment). Two new methods are presented to construct G S . Both methods are very simple to implement. The first method is based on a new solution to the following problem: given a set of points, for each point sort the other points around it by angle. It runs in time O( n 2 ). The second method uses the fact that visibility graphs often are sparse and runs in time O( m log n ) where m is the number of edges in G S . Both methods use only Ogr;( n ) storage.
---
paper_title: Kinodynamic motion planning: connecting exploration trees using trajectory optimization Methods

paper_content:

Motion planning for complex dynamic systems as well as kinodynamic motion planning are still problems difficult to solve in their generic formulation. For systems for which no steering method is known, the only existing algorithms consist in building an exploration tree in the configuration space by exploring the input space of the system. The main drawback of this type of methods is that they never reach exactly the goal but stops the search when a small neighborhood of the goal has been reached. If the neighborhood is small, the exploration method needs to produce a lot of nodes. In this paper, we propose a solution to cope with this complexity issue. We run a tree exploration method with a big neighborhood and then we locally modify the trajectory in order to make it reach exactly the goal. Our solution is based on a trajectory optimization method we have developed earlier in a mobile robot context and that we have adapted for the problem raised here. The method is generic and can be applied to any dynamic system. A few experimental results are given at the end of the paper.
---
paper_title: Optimal paths for a car that goes both forwards and backwards

paper_content:

The path taken by a car with a given minimum turning radius has a lower bound on its radius of curvature at each point, but the path has cusps if the car shifts into or out of reverse gear. What is the shortest such path a car can travel between two points if its starting and ending directions are specified? One need consider only paths with at most 2 cusps or reversals
---
paper_title: Complexity of the mover's problem and generalizations

paper_content:

This paper concerns the problem of moving a polyhedron through Euclidean space while avoiding polyhedral obstacles.
---
paper_title: Motion planning in the presence of moving obstacles

paper_content:

This paper investigates the computational complexity of planning the motion of a body B in 2-D or 3-D space, so as to avoid collision with moving obstacles of known, easily computed, trajectories. Dynamic movement problems are of fundamental importance to robotics, but their computational complexity has not previously been investigated. We provide evidence that the 3-D dynamic movement problem is intractable even if B has only a constant number of degrees of freedom of movement. In particular, we prove the problem is PSPACE-hard if B is given a velocity modulus bound on its movements and is NP hard even if B has no velocity modulus bound, where in both cases B has 6 degrees of freedom. To prove these results we use a unique method of simulation of a Turing machine which uses time to encode configurations (whereas previous lower bound proofs in robotics used the system position to encode configurations and so required unbounded number of degrees of freedom). We also investigate a natural class of dynamic problems which we call asteroid avoidance problems: B, the object we wish to move, is a convex polyhedron which is free to move by translation with bounded velocity modulus, and the polyhedral obstacles have known translational trajectories but cannot rotate. This problem has many applications to robot, automobile, and aircraft collision avoidance. Our main positive results are polynomial time algorithms for the 2-D asteroid avoidance problem with bounded number of obstacles as well as single exponential time and nO(log n) space algorithms for the 3-D asteroid avoidance problem with an unbounded number of obstacles. Our techniques for solving these asteroid avoidance problems are novel in the sense that they are completely unrelated to previous algorithms for planning movement in the case of static obstacles. We also give some additional positive results for various other dynamic movers problems, and in particular give polynomial time algorithms for the case in which B has no velocity bounds and the movements of obstacles are algebraic in space-time.
---
paper_title: Computing minimum lap-time trajectories for a single-track car with load transfer

paper_content:

In this paper we address the minimum lap-time problem for a single-track rigid car which includes tire models and load transfer. Given a planar track including lane boundaries, our goal is to find a trajectory of the car minimizing the lap time subject to tire and steering limits. By using a new set of coordinates, the time-dependent system is transformed into a “space-dependent” (and space-variant) system. The choice of a suitable set of coordinates and the partition of the dynamics into a “longitudinal” one and a “transverse” one, allows us to convert the minimum time problem into a fixed horizon constrained optimal control problem. Based on a projection operator nonlinear optimal control technique, we propose a minimum lap-time strategy to push the rigid car to the limit of its handling capabilities. Finally, we provide numerical computations that: (i) show the effectiveness of the proposed strategy, and (ii) allow us to highlight important features of minimum lap-time trajectories.
---
paper_title: A Conjugate Gradient-Based BPTT-Like Optimal Control Algorithm With Vehicle Dynamics Control Application

paper_content:

The paper presents a conjugate gradient-based numerical algorithm for optimal control of nonlinear multivariable systems with control and state vectors constraints. The algorithm has a backward-in-time recurrent structure similar to the backpropagation-through-time (BPTT) algorithm. The emphasis is on implementation and testing of various conjugate gradient methods. A vehicle dynamics control example demonstrates that the use of conjugate gradient algorithms leads to substantial reduction of computational time when compared to the standard gradient algorithm with a constant learning rate.
---
paper_title: An hp-adaptive pseudospectral method for solving optimal control problems

paper_content:

SUMMARY An hp-adaptive pseudospectral method is presented for numerically solving optimal control problems. The method presented in this paper iteratively determines the number of segments, the width of each segment, and the polynomial degree required in each segment in order to obtain a solution to a userspecified accuracy. Starting with a global pseudospectral approximation for the state, on each iteration the method determines locations for the segment breaks and the polynomial degree in each segment for use on the next iteration. The number of segments and the degree of the polynomial on each segment continue to be updated until a user-specified tolerance is met. The terminology ‘hp’ is used because the segment widths (denoted h) and the polynomial degree (denoted p) in each segment are determined simultaneously. It is found that the method developed in this paper leads to higher accuracy solutions with less computational effort and memory than is required in a global pseudospectral method. Consequently, the method makes it possible to solve complex optimal control problems using pseudospectral methods in cases where a global pseudospectral method would be computationally intractable. Finally, the utility of the method is demonstrated on a variety of problems of varying complexity. Copyright 2010 John Wiley & Sons, Ltd.
---
paper_title: Making Bertha Drive—An Autonomous Journey on a Historic Route

paper_content:

125 years after Bertha Benz completed the first overland journey in automotive history, the Mercedes Benz S-Class S 500 INTELLIGENT DRIVE followed the same route from Mannheim to Pforzheim, Germany, in fully autonomous manner. The autonomous vehicle was equipped with close-to-production sensor hardware and relied solely on vision and radar sensors in combination with accurate digital maps to obtain a comprehensive understanding of complex traffic situations. The historic Bertha Benz Memorial Route is particularly challenging for autonomous driving. The course taken by the autonomous vehicle had a length of 103 km and covered rural roads, 23 small villages and major cities (e.g. downtown Mannheim and Heidelberg). The route posed a large variety of difficult traffic scenarios including intersections with and without traffic lights, roundabouts, and narrow passages with oncoming traffic. This paper gives an overview of the autonomous vehicle and presents details on vision and radar-based perception, digital road maps and video-based self-localization, as well as motion planning in complex urban scenarios.
---
paper_title: Control-limited differential dynamic programming

paper_content:

Trajectory optimizers are a powerful class of methods for generating goal-directed robot motion. Differential Dynamic Programming (DDP) is an indirect method which optimizes only over the unconstrained control-space and is therefore fast enough to allow real-time control of a full humanoid robot on modern computers. Although indirect methods automatically take into account state constraints, control limits pose a difficulty. This is particularly problematic when an expensive robot is strong enough to break itself. In this paper, we demonstrate that simple heuristics used to enforce limits (clamping and penalizing) are not efficient in general. We then propose a generalization of DDP which accommodates box inequality constraints on the controls, without significantly sacrificing convergence quality or computational effort. We apply our algorithm to three simulated problems, including the 36-DoF HRP-2 robot. A movie of our results can be found here goo.gl/eeiMnn
---
paper_title: An historical survey of computational methods in optimal control.

paper_content:

The last twenty years have seen a great flourishing in optimal control theory. In this paper, we shall highlight some of the salient theoretical developments in the specific area of algorithms.The first algorithms for optimal control were aimed at unconstrained problems and were derived by using first and second variation methods of the calculus of variations. These methods have subsequently been recognized as gradient, Newton–Raphson, or Gauss–Newton methods in function space. A much more recent addition to the arsenal of unconstrained optimal control algorithms are several variations of conjugate gradient methods.At first, constrained optimal control problems could only be solved by exterior penalty function methods. Later algorithms specifically designed for constrained problems have appeared. Among these we find methods for solving the unconstrained linear quadratic regulator problem as well as certain constrained minimum time and minimum energy problems. Differential-dynamic programming was developed...
---
paper_title: The complexity of robot motion planning

paper_content:

The Complexity of Robot Motion Planning makes original contributions both to robotics and to the analysis of algorithms. In this groundbreaking monograph John Canny resolves long-standing problems concerning the complexity of motion planning and, for the central problem of finding a collision free path for a jointed robot in the presence of obstacles, obtains exponential speedups over existing algorithms by applying high-powered new mathematical techniques.Canny's new algorithm for this "generalized movers' problem," the most-studied and basic robot motion planning problem, has a single exponential running time, and is polynomial for any given robot. The algorithm has an optimal running time exponent and is based on the notion of roadmaps - one-dimensional subsets of the robot's configuration space. In deriving the single exponential bound, Canny introduces and reveals the power of two tools that have not been previously used in geometric algorithms: the generalized (multivariable) resultant for a system of polynomials and Whitney's notion of stratified sets. He has also developed a novel representation of object orientation based on unnormalized quaternions which reduces the complexity of the algorithms and enhances their practical applicability.After dealing with the movers' problem, the book next attacks and derives several lower bounds on extensions of the problem: finding the shortest path among polyhedral obstacles, planning with velocity limits, and compliant motion planning with uncertainty. It introduces a clever technique, "path encoding," that allows a proof of NP-hardness for the first two problems and then shows that the general form of compliant motion planning, a problem that is the focus of a great deal of recent work in robotics, is non-deterministic exponential time hard. Canny proves this result using a highly original construction.John Canny received his doctorate from MIT And is an assistant professor in the Computer Science Division at the University of California, Berkeley. The Complexity of Robot Motion Planning is the winner of the 1987 ACM Doctoral Dissertation Award.
---
paper_title: Sampling-based algorithms for optimal motion planning

paper_content:

United States. Air Force Office of Scientific Research (Michigan/AFRL Collaborative Center in Control Science Grant FA 8650-07-2-3744)
---
paper_title: Aggressive maneuvers on loose surfaces: Data analysis and input parametrization

paper_content:

In this work we initiate a mathematical analysis of rally racing techniques. An empirical description of trail-braking (TB) and pendulum-turn (PT) cornering, two of the most common rally racing maneuvers, is provided via analysis of data collected during execution of these maneuvers by an expert rally driver. Trail-Braking and Pendulum-Turn maneuvering techniques are reproduced using numerical optimization as special cases of the minimum time cornering problem with specific boundary conditions. We show that a simple parametrization of the control inputs can be used to reproduce these maneuvers using a high fidelity full-car model.
---
paper_title: Motion planning in a plane using generalized Voronoi diagrams

paper_content:

An algorithm for planning a collision-free path for a rectangle in a planar workspace populated with polygonal obstacles is presented. Heuristic techniques are used to plan the motion along a nominal path obtained from a generalized Voronoi diagram (GVD). The algorithm was demonstrated to be quite fast with execution times comparable to, or exceeding, those of the freeway method. Unlike the freeway method, the GVD technique can be successfully applied to difficult problems which arise in cluttered workspaces. The planned paths stay well away from the obstacles when possible and are somewhat shorter than the freeway paths due to parabolic arcs around corners. Furthermore, motion along the paths is smooth in the sense that rotations are performed during translation, not just at isolated points in the workspace. >
---
paper_title: Real-time robot motion planning using rasterizing computer graphics hardware

paper_content:

We present a real-time robot motion planner that is fast and complete to a resolution. The technique is guaranteed to find a path if one exists at the resolution, and all paths returned are safe. The planner can handle any polyhedral geometry of robot and obstacles, including disjoint and highly concave unions of polyhedra.The planner uses standard graphics hardware to rasterize configuration space obstacles into a series of bitmap slices, and then uses dynamic programming to create a navigation function (a discrete vector-valued function) and to calculate paths in this rasterized space. The motion paths which the planner produces are minimal with respect to an L1 (Manhattan) distance metric that includes rotation as well as translation.Several examples are shown illustrating the competence of the planner at generating planar rotational and translational plans for complex two and three dimensional robots. Dynamic motion sequences, including complicated and non-obvious backtracking solutions, can be executed in real time.
---
paper_title: Finding curvature-constrained paths that avoid polygonal obstacles

paper_content:

We describe an algorithm to find a unit-curvature path between specified configurations in an arbitrary polygonal domain. Whenever such a path exists, the algorithm returns an explicit description of one such path in time that is polynomial in n (the number of features of the domain), m (the precision of the input) and k (the number of segments on the simplest obstacle-free Dubins path connecting the specified configurations). Our algorithm is based on a new normal form for unit-curvature paths and a dynamic path filtering argument that exploits a separation bound for distinct paths in this normal form.The best result known for the feasibility of bounded-curvature motion in the presence of arbitrary polygonal obstacles involves a reduction to the first-order theory of the reals. It just determines if a feasible path exists (it does not return a path) and requires exponential time and space.
---
paper_title: Optimal motion planning with the half-car dynamical model for autonomous high-speed driving

paper_content:

We discuss an implementation of the RRT* optimal motion planning algorithm for the half-car dynamical model to enable autonomous high-speed driving. To develop fast solutions of the associated local steering problem, we observe that the motion of a special point (namely, the front center of oscillation) can be modeled as a double integrator augmented with fictitious inputs. We first map the constraints on tire friction forces to constraints on these augmented inputs, which provides instantaneous, state-dependent bounds on the curvature of geometric paths feasibly traversable by the front center of oscillation. Next, we map the vehicle's actual inputs to the augmented inputs. The local steering problem for the half-car dynamical model can then be transformed to a simpler steering problem for the front center of oscillation, which we solve efficiently by first constructing a curvature-bounded geometric path and then imposing a suitable speed profile on this geometric path. Finally, we demonstrate the efficacy of the proposed motion planner via numerical simulation results.
---
paper_title: Safe motion planning in dynamic environments

paper_content:

This paper addresses the problem of motion planning (MP) in dynamic environments. It is first argued that dynamic environments impose a real-time constraint upon MP: it has a limited time only to compute a motion, the time available being a function of the dynamicity of the environment. Now, given the intrinsic complexity of MP, computing a complete motion to the goal within the time available is impossible to achieve in most real situations. Partial motion planning (PMP) is the answer to this problem proposed in this paper. PMP is a motion planning scheme with an anytime flavor: when the time available is over, PMP returns the best partial motion to the goal computed so far. Like reactive navigation scheme, PMP faces a safety issue: what guarantee is there that the system will never end up in a critical situation yielding an inevitable collision? The answer proposed in this paper to this safety issue relies upon the concept of inevitable collision states (ICS). ICS takes into account the dynamics of both the system and the moving obstacles. By computing ICS-free partial motion, the system safety can be guaranteed. Application of PMP to the case of a car-like system in a dynamic environment is presented.
---
paper_title: Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions

paper_content:

In this paper we present a novel probabilistic sampling-based motion planning algorithm called the Fast Marching Tree algorithm (FMT*). The algorithm is specifically aimed at solving complex motion planning problems in high-dimensional configuration spaces. This algorithm is proven to be asymptotically optimal and is shown to converge to an optimal solution faster than its state-of-the-art counterparts, chiefly PRM* and RRT*. The FMT* algorithm performs a "lazy" dynamic programming recursion on a predetermined number of probabilistically-drawn samples to grow a tree of paths, which moves steadily outward in cost-to-arrive space. As such, this algorithm combines features of both single-query algorithms (chiefly RRT) and multiple-query algorithms (chiefly PRM), and is reminiscent of the Fast Marching Method for the solution of Eikonal equations. As a departure from previous analysis approaches that are based on the notion of almost sure convergence, the FMT* algorithm is analyzed under the notion of convergence in probability: the extra mathematical flexibility of this approach allows for convergence rate bounds-the first in the field of optimal sampling-based motion planning. Specifically, for a certain selection of tuning parameters and configuration spaces, we obtain a convergence rate bound of order O(n-1/d+ρ), where n is the number of sampled points, d is the dimension of the configuration space, and ρ is an arbitrarily small constant. We go on to demonstrate asymptotic optimality for a number of variations on FMT*, namely when the configuration space is sampled non-uniformly, when the cost is not arc length, and when connections are made based on the number of nearest neighbors instead of a fixed connection radius. Numerical experiments over a range of dimensions and obstacle configurations confirm our the-oretical and heuristic arguments by showing that FMT*, for a given execution time, returns substantially better solutions than either PRM* or RRT*, especially in high-dimensional configuration spaces and in scenarios where collision-checking is expensive.
---
paper_title: Optimal sampling-based motion planning under differential constraints: The driftless case

paper_content:

Motion planning under differential constraints is a classic problem in robotics. To date, the state of the art is represented by sampling-based techniques, with the Rapidly-exploring Random Tree algorithm as a leading example. Yet, the problem is still open in many aspects, including guarantees on the quality of the obtained solution. In this paper we provide a thorough theoretical framework to assess optimality guarantees of sampling-based algorithms for planning under differential constraints. We exploit this framework to design and analyze two novel sampling-based algorithms that are guaranteed to converge, as the number of samples increases, to an optimal solution (namely, the Differential Probabilistic RoadMap algorithm and the Differential Fast Marching Tree algorithm). Our focus is on driftless control-affine dynamical models, which accurately model a large class of robotic systems. In this paper we use the notion of convergence in probability (as opposed to convergence almost surely): the extra mathematical flexibility of this approach yields convergence rate bounds — a first in the field of optimal sampling-based motion planning under differential constraints. Numerical experiments corroborating our theoretical results are presented and discussed.
---
paper_title: A “retraction” method for planning the motion of a disc

paper_content:

Abstract A new approach to certain motion-planning problems in robotics is introduced. This approach is based on the use of a generalized Voronoi diagram, and reduces the search for a collision-free continuous motion to a search for a connected path along the edges of such a diagram. This approach yields an O ( n log n ) algorithm for planning an obstacle-avoiding motion of a single circular disc amid polygonal obstacles. Later papers will show that extensions of the approach can solve other motion-planning problems, including those of moving a straight line segment or several coordinated discs in the plane amid polygonal obstacles.
---
paper_title: On the Relationship between Classical Grid Search and Probabilistic Roadmaps

paper_content:

We present, implement, and analyze a spectrum of closely-related planners, designed to gain insight into the relationship between classical grid search and probabilistic roadmaps (PRMs). Building on the quasi-Monte Carlo sampling literature, we have developed deterministic variants of the PRM that use low-discrepancy and low-dispersion samples, including lattices. Classical grid search is extended using subsampling for collision detection and also the dispersion-optimal Sukharev grid, which can be considered as a kind of lattice-based roadmap to complete the spectrum. Our experimental results show that the deterministic variants of the PRM offer performance advantages in comparison to the original, multiple-query PRM and the single-query, lazy PRM. Surprisingly, even some forms of grid search yield performance that is comparable to the original PRM. Our theoretical analysis shows that all of our deterministic PRM variants are resolution complete and achieve the best possible asymptotic convergence rate, which is shown to be superior to that obtained by random sampling. Thus, in surprising contrast to recent trends, there is both experimental and theoretical evidence that the randomization used in the original PRM is not advantageous.
---
paper_title: Robot Motion Planning

paper_content:

1 Introduction and Overview.- 2 Configuration Space of a Rigid Object.- 3 Obstacles in Configuration Space.- 4 Roadmap Methods.- 5 Exact Cell Decomposition.- 6 Approximate Cell Decomposition.- 7 Potential Field Methods.- 8 Multiple Moving Objects.- 9 Kinematic Constraints.- 10 Dealing with Uncertainty.- 11 Movable Objects.- Prospects.- Appendix A Basic Mathematics.- Appendix B Computational Complexity.- Appendix C Graph Searching.- Appendix D Sweep-Line Algorithm.- References.
---
paper_title: Planning smooth paths for mobile robots

paper_content:

The authors consider the problem of planning paths for a robot which has a minimum turning radius. This is a first step towards accurately modeling a robot with the kinematics of a car. The technique used is to define a set of canonical trajectories which satisfy the nonholonomic constraints imposed. A configuration space can be constructed for these trajectories in which there is a simple characterization of the boundaries of the obstacles generated by the workspace obstacles. The authors describe a graph search algorithm which divides the configuration space into sample trajectories. The characterization of the boundaries makes it possible to calculate an approximate path in time O(n/sup 3// delta log n+Alog (n/ delta )), where n is the number of obstacle vertices in the environment, A is the number of free trajectories, and delta describes the robustness of the generated path and the closeness of the approximation. The authors also describe a plane sweep for computing the configuration space obstacle for a trajectory segment. They use this to generate robust paths using a quadtree based algorithm in time O(n/sup 4/log n+(n/ delta /sup 2/)). >
---
paper_title: Primitives for smoothing mobile robot trajectories

paper_content:

The problem of smoothing mobile robot motions when cusps, i.e. changes of motion direction along the trajectory, are imposed is treated. The authors pinpoint some special curves, called anticlothoids, and it is shown how they can be used together with clothoids to smooth a predefined trajectory.<<ETX>>
---
paper_title: Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces

paper_content:

A new motion planning method for robots in static workspaces is presented. This method proceeds in two phases: a learning phase and a query phase. In the learning phase, a probabilistic roadmap is constructed and stored as a graph whose nodes correspond to collision-free configurations and whose edges correspond to feasible paths between these configurations. These paths are computed using a simple and fast local planner. In the query phase, any given start and goal configurations of the robot are connected to two nodes of the roadmap; the roadmap is then searched for a path joining these two nodes. The method is general and easy to implement. It can be applied to virtually any type of holonomic robot. It requires selecting certain parameters (e.g., the duration of the learning phase) whose values depend on the scene, that is the robot and its workspace. But these values turn out to be relatively easy to choose, Increased efficiency can also be achieved by tailoring some components of the method (e.g., the local planner) to the considered robots. In this paper the method is applied to planar articulated robots with many degrees of freedom. Experimental results show that path planning can be done in a fraction of a second on a contemporary workstation (/spl ap/150 MIPS), after learning for relatively short periods of time (a few dozen seconds).
---
paper_title: A quadratic regulator-based heuristic for rapidly exploring state space

paper_content:

Kinodynamic planning algorithms like Rapidly-Exploring Randomized Trees (RRTs) hold the promise of finding feasible trajectories for rich dynamical systems with complex, nonconvex constraints. In practice, these algorithms perform very well on configuration space planning, but struggle to grow efficiently in systems with dynamics or differential constraints. This is due in part to the fact that the conventional distance metric, Euclidean distance, does not take into account system dynamics and constraints when identifying which node in the existing tree is capable of producing children closest to a given point in state space. We show that an affine quadratic regulator (AQR) design can be used to approximate the exact minimum-time distance pseudometric at a reasonable computational cost. We demonstrate improved exploration of the state spaces of the double integrator and simple pendulum when using this pseudometric within the RRT framework, but this improvement drops off as systems' nonlinearity and complexity increase. Future work includes exploring methods for approximating the exact minimum-time distance pseudometric that can reason about dynamics with higher-order terms.
---
paper_title: Optimal paths for a car that goes both forwards and backwards

paper_content:

The path taken by a car with a given minimum turning radius has a lower bound on its radius of curvature at each point, but the path has cusps if the car shifts into or out of reverse gear. What is the shortest such path a car can travel between two points if its starting and ending directions are specified? One need consider only paths with at most 2 cusps or reversals
---
paper_title: A Formal Basis for the Heuristic Determination of Minimum Cost Paths

paper_content:

Although the problem of determining the minimum cost path through a graph arises naturally in a number of interesting applications, there has been no underlying theory to guide the development of efficient search procedures. Moreover, there is no adequate conceptual framework within which the various ad hoc search strategies proposed to date can be compared. This paper describes how heuristic information from the problem domain can be incorporated into a formal mathematical theory of graph searching and demonstrates an optimality property of a class of search strategies.
---
paper_title: Optimal and efficient path planning for partially-known environments

paper_content:

The task of planning trajectories for a mobile robot has received considerable attention in the research literature. Most of the work assumes the robot has a complete and accurate model of its environment before it begins to move; less attention has been paid to the problem of partially known environments. This situation occurs for an exploratory robot or one that must move to a goal location without the benefit of a floorplan or terrain map. Existing approaches plan an initial path based on known information and then modify the plan locally or replan the entire path as the robot discovers obstacles with its sensors, sacrificing optimality or computational efficiency respectively. This paper introduces a new algorithm, D*, capable of planning paths in unknown, partially known, and changing environments in an efficient, optimal, and complete manner. >
---
paper_title: Fast replanning for navigation in unknown terrain

paper_content:

Mobile robots often operate in domains that are only incompletely known, for example, when they have to move from given start coordinates to given goal coordinates in unknown terrain. In this case, they need to be able to replan quickly as their knowledge of the terrain changes. Stentz' Focussed Dynamic A/sup */ (D/sup */) is a heuristic search method that repeatedly determines a shortest path from the current robot coordinates to the goal coordinates while the robot moves along the path. It is able to replan faster than planning from scratch since it modifies its previous search results locally. Consequently, it has been extensively used in mobile robotics. In this article, we introduce an alternative to D/sup */ that determines the same paths and thus moves the robot in the same way but is algorithmically different. D/sup */ Lite is simple, can be rigorously analyzed, extendible in multiple ways, and is at least as efficient as D/sup */. We believe that our results will make D/sup */-like replanning methods even more popular and enable robotics researchers to adapt them to additional applications.
---
paper_title: ARA*: Anytime A* with Provable Bounds on Sub-Optimality

paper_content:

In real world planning problems, time for deliberation is often limited. Anytime planners are well suited for these problems: they find a feasible solution quickly and then continually work on improving it until time runs out. In this paper we propose an anytime heuristic search, ARA*, which tunes its performance bound based on available search time. It starts by finding a suboptimal solution quickly using a loose bound, then tightens the bound progressively as time allows. Given enough time it finds a provably optimal solution. While improving its bound, ARA* reuses previous search efforts and, as a result, is significantly more efficient than other anytime search methods. In addition to our theoretical analysis, we demonstrate the practical utility of ARA* with experiments on a simulated robot kinematic arm and a dynamic path planning problem for an outdoor rover.
---
paper_title: The Focussed D* Algorithm for Real-Time Replanning

paper_content:

Finding the lowest-cost path through a graph is central to many problems including route planning for a mobile robot If arc costs change during the traverse then the remainder of the path may need to be replanned. This is the case for a sensor-equipped mobile robot with imperfect information about its environment. As the robot acquires additional information via its sensors it can revise its plan to reduce the total cost of the traverse. If the prior information is grossly incomplete the robot may discover useful information in every piece of sensor data. During replanning, the robot must either wait for the new path to be computed or move in the wrong direction therefore rapid replanning is essential The D* algorithm (Dynamic A*) plans optimal traverses ID real-time by incrementally repairing paths to the robots state as new information is discovered. This paper describes an extension to D* that focusses the repairs to significantly reduce the total time required for the initial path calculation and subsequent replanning operations. This extension completes the development of the D* algorithm as a full generalizatin of A* for dynamic environments where arc costs can change during the traverse of the solution path.
---
paper_title: Anytime Dynamic A*: An Anytime, Replanning Algorithm

paper_content:

We present a graph-based planning and replanning algorithm able to produce bounded suboptimal solutions in an anytime fashion. Our algorithm tunes the quality of its solution based on available search time, at every step reusing previous search efforts. When updated information regarding the underlying graph is received, the algorithm incrementally repairs its previous solution. The result is an approach that combines the benefits of anytime and incremental planners to provide efficient solutions to complex, dynamic search problems. We present theoretical analysis of the algorithm, experimental results on a simulated robot kinematic arm, and two current applications in dynamic path planning for outdoor mobile robots.
---
paper_title: Anytime Heuristic Search

paper_content:

We describe how to convert the heuristic search algorithm A* into an anytime algorithm that finds a sequence of improved solutions and eventually converges to an optimal solution. The approach we adopt uses weighted heuristic search to find an approximate solution quickly, and then continues the weighted search to find improved solutions as well as to improve a bound on the suboptimality of the current solution. When the time available to solve a search problem is limited or uncertain, this creates an anytime heuristic search algorithm that allows a flexible tradeoff between search time and solution quality. We analyze the properties of the resulting Anytime A* algorithm, and consider its performance in three domains; sliding-tile puzzles, STRIPS planning, and multiple sequence alignment. To illustrate the generality of this approach, we also describe how to transform the memory-efficient search algorithm Recursive Best-First Search (RBFS) into an anytime algorithm.
---
paper_title: Optimal kinodynamic motion planning using incremental sampling-based methods

paper_content:

Sampling-based algorithms such as the Rapidly-exploring Random Tree (RRT) have been recently proposed as an effective approach to computationally hard motion planning problem. However, while the RRT algorithm is known to be able to find a feasible solution quickly, there are no guarantees on the quality of such solution, e.g., with respect to a given cost functional. To address this limitation, the authors recently proposed a new algorithm, called RRT*, which ensures asymptotic optimality, i.e., almost sure convergence of the solution returned by the algorithm to an optimal solution, while maintaining the same properties of the standard RRT algorithm, both in terms of computation of feasible solutions, and of computational complexity. In this paper, the RRT* algorithm is extended to deal with differential constraints. A sufficient condition for asymptotic optimality is provided. It is shown that the RRT* algorithm equipped with any local steering procedure that satisfies this condition converges to an optimal solution almost surely. In particular, simple local steering procedures are provided for a Dubins' vehicle as well as a double integrator. Simulation examples are also provided for these systems comparing the RRT and the RRT* algorithms.
---
paper_title: Sampling-based algorithms for optimal motion planning

paper_content:

United States. Air Force Office of Scientific Research (Michigan/AFRL Collaborative Center in Control Science Grant FA 8650-07-2-3744)
---
paper_title: Randomized Kinodynamic Motion Planning with Moving Obstacles

paper_content:

This paper presents a novel randomized motion planner for robots that must achieve a specified goal under kinematic and/or dynamic motion constraints while avoiding collision with moving obstacles with known trajectories. The planner encodes the motion constraints on the robot with a control system and samples the robot's state × time space by picking control inputs at random and integrating its equations of motion. The result is a probabilistic roadmap of sampled state ×time points, called milestones, connected by short admissible trajectories. The planner does not precompute the roadmap; instead, for each planning query, it generates a new roadmap to connect an initial and a goal state×time point. The paper presents a detailed analysis of the planner's convergence rate. It shows that, if the state×time space satisfies a geometric property called expansiveness, then a slightly idealized version of our implemented planner is guaranteed to find a trajectory when one exists, with probability quickly converg...
---
paper_title: Sparse Methods for Efficient Asymptotically Optimal Kinodynamic Planning

paper_content:

This work describes STABLE SPARSE RRT (SST), an algorithm that (a) provably provides asymptotic (near-)optimality for kinodynamic planning without access to a steering function, (b) maintains only a sparse set of samples, (c) converges fast to high-quality paths and (d) achieves competitive running time to RRT, which provides only probabilistic completeness. SST addresses the limitation of RRT \(^*\), which requires a steering function for asymptotic optimality . This issue has motivated recent variations of RRT \(^*\), which either work for a limiting set of systems or exhibit increased computational cost. This paper provides formal arguments for the properties of the proposed algorithm. To the best of the authors’ knowledge, this is the first sparse data structure that provides such desirable guarantees for a wide set of systems under a reasonable set of assumptions. Simulations for a variety of benchmarks, including physically simulated ones, confirm the argued properties of the approach.
---
paper_title: Kinodynamic RRT*: Asymptotically optimal motion planning for robots with linear dynamics

paper_content:

We present Kinodynamic RRT*, an incremental sampling-based approach for asymptotically optimal motion planning for robots with linear dynamics. Our approach extends RRT*, which was introduced for holonomic robots [10], by using a fixed-final-state-free-final-time controller that optimally connects any pair of states, where the cost function is expressed as a trade-off between the duration of a trajectory and the expended control effort. Our approach generalizes earlier work on RRT* for kinodynamic systems, as it guarantees asymptotic optimality for any system with controllable linear dynamics, in state spaces of any dimension. In addition, we show that for the rich subclass of systems with a nilpotent dynamics matrix, closed-form solutions for optimal trajectories can be derived, which keeps the computational overhead of our algorithm compared to traditional RRT* at a minimum. We demonstrate the potential of our approach by computing asymptotically optimal trajectories in three challenging motion planning scenarios: (i) a planar robot with a 4-D state space and double integrator dynamics, (ii) an aerial vehicle with a 10-D state space and linearized quadrotor dynamics, and (iii) a car-like robot with a 5-D state space and non-linear dynamics.
---
paper_title: PATH PLANNING IN EXPANSIVE CONFIGURATION SPACES

paper_content:

We introduce the notion of expansiveness to characterize a family of robot configuration spaces whose connectivity can be effectively captured by a roadmap of randomly-sampled milestones. The analysis of expansive configuration spaces has inspired us to develop a new randomized planning algorithm. This new algorithm tries to sample only the portion of the configuration space that is relevant to the current query, avoiding the cost of precomputing a roadmap for the entire configuration space. Thus, it is well-suited for problems where only a single query is submitted for a given environment. The algorithm has been implemented and successfully applied to complex assembly maintainability problems from the automotive industry.
---
paper_title: Randomized kinodynamic planning

paper_content:

The paper presents a state-space perspective on the kinodynamic planning problem, and introduces a randomized path planning technique that computes collision-free kinodynamic trajectories for high degree-of-freedom problems. By using a state space formulation, the kinodynamic planning problem is treated as a 2n-dimensional nonholonomic planning problem, derived from an n-dimensional configuration space. The state space serves the same role as the configuration space for basic path planning. The bases for the approach is the construction of a tree that attempts to rapidly and uniformly explore the state space, offering benefits that are similar to those obtained by successful randomized planning methods, but applies to a much broader class of problems. Some preliminary results are discussed for an implementation that determines the kinodynamic trajectories for hovercrafts and satellites in cluttered environments resulting in state spaces of up to twelve dimensions.
---
paper_title: $${\mathrm {RRT^{X}}}$$ RRT X : Real-Time Motion Planning/Replanning for Environments with Unpredictable Obstacles

paper_content:

We present \({\mathrm {RRT^{X}}}\), the first asymptotically optimal sampling-based motion planning algorithm for real-time navigation in dynamic environments (containing obstacles that unpredictably appear, disappear, and move). Whenever obstacle changes are observed, e.g., by onboard sensors, a graph rewiring cascade quickly updates the search-graph and repairs its shortest-path -to-goal subtree. Both graph and tree are built directly in the robot’s state space, respect the kinematics of the robot, and continue to improve during navigation. \({\mathrm {RRT^{X}}}\) is also competitive in static environments—where it has the same amortized per iteration runtime as RRT and RRT* \(\varTheta \left( \log {n}\right) \) and is faster than RRT# \(\omega \left( \log ^2{n}\right) \). In order to achieve \(O\left( \log {n}\right) \) iteration time, each node maintains a set of \(O\left( \log {n}\right) \) expected neighbors, and the search graph maintains \(\epsilon \)-consistency for a predefined \(\epsilon \).
---
paper_title: LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics

paper_content:

The RRT* algorithm has recently been proposed as an optimal extension to the standard RRT algorithm [1]. However, like RRT, RRT* is difficult to apply in problems with complicated or underactuated dynamics because it requires the design of a two domain-specific extension heuristics: a distance metric and node extension method. We propose automatically deriving these two heuristics for RRT* by locally linearizing the domain dynamics and applying linear quadratic regulation (LQR). The resulting algorithm, LQR-RRT*, finds optimal plans in domains with complex or underactuated dynamics without requiring domain-specific design choices. We demonstrate its application in domains that are successively torque-limited, underactuated, and in belief space.
---
paper_title: Sampling-based optimal motion planning for non-holonomic dynamical systems

paper_content:

Sampling-based motion planning algorithms, such as the Probabilistic RoadMap (PRM) and the Rapidly-exploring Random Tree (RRT), have received a large and growing amount of attention during the past decade. Most recently, sampling-based algorithms, such as the PRM* and RRT*, that guarantee asymptotic optimality, i.e., almost-sure convergence towards optimal solutions, have been proposed. Despite the experimental success of asymptotically-optimal sampling-based algorithms, their extensions to handle complex non-holonomic dynamical systems remains largely an open problem. In this paper, with the help of results from differential geometry, we extend the RRT* algorithm to handle a large class of non-holonomic dynamical systems. We demonstrate the performance of the algorithm in computational experiments involving the Dubins' car dynamics.
---
paper_title: Kinodynamic RRTs with Fixed Time Step and Best-Input Extension Are Not Probabilistically Complete

paper_content:

RRTs are a popular method for kinodynamic planning that many consider to be probabilistically complete. However, different variations of the RRT algorithm exist and not all of them are probabilistically complete. The tree can be extended using a fixed or variable time step. The input can be chosen randomly or the best input can be chosen such that the new child node is as close as possible to the sampled state according to the used distance metric. It has been shown that for finite input sets an RRT using a fixed step size with a randomly selected input is probabilistically complete. However, this variant is uncommon since it is less efficient. We prove that the most common variant of choosing the best input in combination with a fixed time step is not probabilistically complete.
---
paper_title: Autonomous driving in urban environments: Boss and the Urban Challenge

paper_content:

Boss is an autonomous vehicle that uses on-board sensors (global positioning system, lasers, radars, and cameras) to track other vehicles, detect static obstacles, and localize itself relative to a road model. A three-layer planning system combines mission, behavioral, and motion planning to drive in urban environments. The mission planning layer considers which street to take to achieve a mission goal. The behavioral layer determines when to change lanes and precedence at intersections and performs error recovery maneuvers. The motion planning layer selects actions to avoid obstacles while making progress toward local goals. The system was developed from the ground up to address the requirements of the DARPA Urban Challenge using a spiral system development process with a heavy emphasis on regular, regressive system testing. During the National Qualification Event and the 85-km Urban Challenge Final Event, Boss demonstrated some of its capabilities, qualifying first and winning the challenge. © 2008 Wiley Periodicals, Inc.
---
paper_title: Trajectory-Tracking and Path-Following of Underactuated Autonomous Vehicles With Parametric Modeling Uncertainty

paper_content:

We address the problem of position trajectory-tracking and path-following control design for underactuated autonomous vehicles in the presence of possibly large modeling parametric uncertainty. For a general class of vehicles moving in either 2- or 3-D space, we demonstrate how adaptive switching supervisory control can be combined with a nonlinear Lyapunov-based tracking control law to solve the problem of global boundedness and convergence of the position tracking error to a neighborhood of the origin that can be made arbitrarily small. The desired trajectory does not need to be of a particular type (e.g., trimming trajectories) and can be any sufficiently smooth bounded curve parameterized by time. We also show how these results can be applied to solve the path-following problem, in which the vehicle is required to converge to and follow a path, without a specific temporal specification. We illustrate our design procedures through two vehicle control applications: a hovercraft (moving on a planar surface) and an underwater vehicle (moving in 3-D space). Simulations results are presented and discussed.
---
paper_title: Path-following for nonminimum phase systems removes performance limitations

paper_content:

We highlight an essential difference between path-following and reference-tracking for nonminimum phase systems. It is well known that in the reference-tracking, for nonminimum phase systems, there exists a fundamental performance limitation in terms of a lower bound on the L/sub 2/-norm of the tracking error, even when the control effort is free. We show that this is not the case for the less stringent path-following problem, where the control objective is to force the output to follow a geometric path without a timing law assigned to it. Furthermore, the same is true even when an additional desired speed assignment is imposed.
---
paper_title: Odin: Team VictorTango's entry in the DARPA Urban Challenge

paper_content:

The DARPA Urban Challenge required robotic vehicles to travel more than 90 km through an urban environment without human intervention and included situations such as stop intersections, traffic merges, parking, and roadblocks. Team VictorTango separated the problem into three parts: base vehicle, perception, and planning. A Ford Escape outfitted with a custom drive-by-wire system and computers formed the basis for Odin. Perception used laser scanners, global positioning system, and a priori knowledge to identify obstacles, cars, and roads. Planning relied on a hybrid deliberative-reactive architecture to analyze the situation, select the appropriate behavior, and plan a safe path. All vehicle modules communicated using the JAUS (Joint Architecture for Unmanned Systems) standard. The performance of these components in the Urban Challenge is discussed and successes noted. The result of VictorTango's work was successful completion of the Urban Challenge and a third-place finish. © 2008 Wiley Periodicals, Inc.
---
paper_title: Integrated Mobile Robot Control

paper_content:

This paper describes the strucwre implementation and operation of a real-time mobile robot controller which integrates capabilities such as: position estimation path specification and hacking human interfaces fast communication and multiple client support The benefits of such high-level capabilities in a low-level controller was shown by its implementation for the Naviab autonomous vehicle. In addition performance results from positioning and tracking systems are reported and analyzed.© (1991) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Autonomous ground vehicle path tracking

paper_content:

Autonomous ground vehicle navigation requires the integration of many technologies such as path planning, position and orientation sensing, vehicle control, and obstacle avoidance. The work presented here focuses on the control of a nonholonomic ground vehicle as it tracks a given path. A new path tracking technique called “vector pursuit” is presented. This new technique is based on the theory of screws, which was developed by Sir Robert Ball in 1900. It generates a desired vehicle turning radius based on the vehicle's current position and orientation relative to the position of a point ahead on the planned path and the desired orientation along the path at that point. The vector pursuit algorithm is compared to other geometrical approaches, and it is shown to be more robust, resulting in more accurate path tracking. © 2004 Wiley Periodicals, Inc.
---
paper_title: Autonomous path-planning navigation system for site characterization

paper_content:

The location and removal of buried munitions is an important yet hazardous task. Current development is aimed at performing both the ordnance location and removal tasks autonomously. An autonomous survey vehicle (ASV) named the Gator has been developed at the Center for Intelligent Machines and Robotics, under the direction of Wright Laboratory, Tyndall Air Force Base, Florida, and the Navy Explosive Ordnance Disposal Technology Division, Indian Head, Maryland. The primary task of the survey vehicle is to autonomously traverse an off-road site, towing behind it a trailer containing a sensor package capable of characterizing the sub-surface contents. Achieving 00 percent coverage of the site is critical to fully characterizing the site. This paper presents a strategy for planning efficient paths for the survey vehicle that guarantees near-complete coverage of a site. A small library of three in-house developed path planners are reviewed. A strategy is also presented to keep the trailer on-path and to calculate the percent of coverage of a site with a resolution of 0.01 m2. All of the algorithms discussed in this paper were initially developed in simulation on a Silicon Graphics computer and subsequently implemented on the survey vehicle.© (1996) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: The 2005 DARPA Grand Challenge: The Great Robot Race

paper_content:

The DARPA Grand Challenge was a landmark in the field of robotics: a race by autonomous vehicles through 132 miles of rough, cross-country Nevada terrain that showcased exciting and unprecedented capabilities in robotic perception, navigation, and control. The event took place in October 2005, and drew teams of competitors from academia and industry, and many garage hobbyists. This book presents fifteen technical papers that are written at a level that makes them easily accessible to a broad technical audience, describing the technology behind most of the robotic vehicles that participated in this famous race. The papers describe each team's driverless vehicle, race strategy, and insights. As a whole, they present the state of the art in autonomous vehicle technology, and offer a glimpse of future technology for tomorrows driverless cars. This book will serve as an authoritative, archival source for the DARPA Grand Challenge and a must have for robotics students and researchers, since it describes the state of the art in perception, planning and control.
---
paper_title: Vehicle dynamics and control

paper_content:

1. Introduction.- 2.Lateral Vehicle Dynamics.- 3. Steering Control For Automated Lane Keeping.- 4. Longitudinal Vehicle Dynamics.- 5. Introduction to Longitudinal Control.- 6. Adaptive Cruise Control.- 7. Longitudinal Control for Vehicle Platoons.- 8. Electronic Stability Control.- 9. Mean Value Modeling Of SI and Diesel Engines.- 10. Design and Analysis of Passive Automotive Suspensions.- 11. Active Automotive Suspensions.-12. Semi-Active Suspensions.- 13. Lateral and Longitudinal Tires Forces.- 14. Tire-Road Friction Measurement on Highway Vehicles.- 15. Roll Dynamics and Rollover Prevention.- 16. Dynamics and Control of Hybrid Gas Electric Vehicles.
---
paper_title: Cooperative Collision Avoidance at Intersections: Algorithms and Experiments

paper_content:

In this paper, we leverage vehicle-to-vehicle (V2V) communication technology to implement computationally efficient decentralized algorithms for two-vehicle cooperative collision avoidance at intersections. Our algorithms employ formal control theoretic methods to guarantee a collision-free (safe) system, whereas overrides are only applied when necessary to prevent a crash. Model uncertainty and communication delays are explicitly accounted for by the model and by the state estimation algorithm. The main contribution of this work is to provide an experimental validation of our method on two instrumented vehicles engaged in an intersection collision avoidance scenario in a test track.
---
paper_title: PROUD—Public Road Urban Driverless-Car Test

paper_content:

This paper presents an autonomous driving test held in Parma on urban roads and freeways open to regular traffic. During this test, the vehicle not only performed simple maneuvers, but it had to cope with complex driving scenarios as well, including roundabouts, junctions, pedestrian crossings, freeway junctions, and traffic lights. The test demonstrated the ability of the current technology to manage real situations and not only the well-structured and predictable ones. A comparison of milestones, challenges, and key results in autonomous driving is presented to highlight the novelty and the specific purpose of the test. The whole system is described: the vehicle; the software architecture; details about high-, medium-, and low-level control; and details about perception algorithms. A conclusion highlights the achieved results and draws possible directions for future development.
---
paper_title: Control of chained systems application to path following and time-varying point-stabilization of mobile robots

paper_content:

Chain form systems have recently been introduced to model the kinematics of a class of nonholonomic mechanical systems. The first part of the study is centered on control design and analysis for nonlinear systems which can be converted to the chain form. Solutions to various control problems (open-loop steering, partial or complete state feedback stabilization) are either recalled, generalized, or developed. In particular, globally stabilizing time-varying feedbacks are derived, and a discussion of their convergence properties is provided. Application to the control of nonholonomic wheeled mobile robots is described in the second part of the study by considering the case of a car pulling trailers. >
---
paper_title: The 2005 DARPA Grand Challenge: The Great Robot Race

paper_content:

The DARPA Grand Challenge was a landmark in the field of robotics: a race by autonomous vehicles through 132 miles of rough, cross-country Nevada terrain that showcased exciting and unprecedented capabilities in robotic perception, navigation, and control. The event took place in October 2005, and drew teams of competitors from academia and industry, and many garage hobbyists. This book presents fifteen technical papers that are written at a level that makes them easily accessible to a broad technical audience, describing the technology behind most of the robotic vehicles that participated in this famous race. The papers describe each team's driverless vehicle, race strategy, and insights. As a whole, they present the state of the art in autonomous vehicle technology, and offer a glimpse of future technology for tomorrows driverless cars. This book will serve as an authoritative, archival source for the DARPA Grand Challenge and a must have for robotics students and researchers, since it describes the state of the art in perception, planning and control.
---
paper_title: Handbook of Intelligent Vehicles

paper_content:

Traffic Statistics and Challenges.- Introduction of Relevant Vehicular Systems and Control Functions.- Overview of Intelligent Vehicle Systems and Approaches.- Sensing and Situational Awareness.- Sensory Requirements: External, Internal, Positioning and Condition Monitoring.- Driver Assistance.- Trip Planning, Navigation, and Trajectory Control.- Advanced Control and Decision Systems.- Safety and Comfort Systems.- Drowsy and Fatigue Driver Detection, Monitoring, and Warning.- Computer Vision Systems and Algorithms.- Vehicular Communications Systems.- Drive-By-Wire.- Fully Autonomous Driving.- A Look to the Future.
---
paper_title: Tracking Control of Mobile Robots: A Case Study in Backstepping

paper_content:

A tracking control methodology via time-varying state feedback based on the backstepping technique is proposed for both a kinematic and simplified dynamic model of a two-degrees-of-freedom mobile robot. We first address the local tracking problem where initial tracking errors are sufficiently small. Then, under additional conditions on the desired velocities, we treat the global tracking problem where initial tracking errors are arbitrary. Simulation results are provided to validate and analyse our theoretical results.
---
paper_title: A stable tracking control method for an autonomous mobile robot

paper_content:

A stable tracking control rule is proposed for nonholonomic vehicles. The stability of the rule is proved through the use of a Liapunov function. Inputs to the vehicle are a reference posture (x/sub r/, y/sub r/, theta /sub r/)/sup t/ and reference velocities ( nu /sub r/, omega /sub r/)/sup t/. The major objective of this study is to propose a control rule to find reasonable target linear and rotational velocities ( nu , omega )/sup t/. Linearizing the system's differential equation is useful for deciding parameters for critical dumping for a small disturbance. In order to avoid slippage, a velocity/acceleration limitation scheme is introduced. Several simulation results are presented with or without the velocity/acceleration limiter. The control rule and limiting method proposed are robot independent and hence can be applied to various kinds of mobile robots with a dead reckoning ability. This method was implemented on the autonomous mobile robot Yamabico-11. Experimental results obtained are close to the results with the velocity/acceleration limiter.<<ETX>>
---
paper_title: Parsimonious shooting heuristic for trajectory control of connected automated traffic part I: Theoretical analysis with generalized time geography

paper_content:

This paper studies a problem of controlling trajectories of a platoon of vehicles on a highway segment with connected and automated vehicles. This problem is complex because each vehicle trajectory is an infinite-dimensional object and neighboring trajectories have complex interactions (e.g., car-following behavior). A parsimonious shooting heuristic algorithm is proposed to construct vehicle trajectories on a signalized highway segment that comply with boundary conditions for vehicle arrivals, vehicle mechanical limits, traffic lights and vehicle following safety. This algorithm breaks each vehicle trajectory into a few sections and each is analytically solvable. This decomposes the original hard trajectory control problem to a simple constructive heuristic. Then we slightly adapt this shooting heuristic algorithm to efficiently solve a leading vehicle problem on an uninterrupted freeway. To study theoretical properties of the proposed algorithms, the time geography theory is generalized by considering finite accelerations. With this generalized theory, it is found that under mild conditions, these algorithms can always obtain a feasible solution to the original complex trajectory control problem. Further, we discover that the shooting heuristic solution is a generalization of the solution to the classic kinematic wave theory by incorporating finite accelerations. We identify the theoretical bounds to the difference between the shooting heuristic solution and the kinematic wave solution. Numerical experiments are conducted to verify the theoretical results and to draw additional insights into the potential of trajectory control in improving traffic performance. Building upon this foundation, an optimization framework will be presented in a following paper as Part II of this study.
---
paper_title: The 2005 DARPA Grand Challenge: The Great Robot Race

paper_content:

The DARPA Grand Challenge was a landmark in the field of robotics: a race by autonomous vehicles through 132 miles of rough, cross-country Nevada terrain that showcased exciting and unprecedented capabilities in robotic perception, navigation, and control. The event took place in October 2005, and drew teams of competitors from academia and industry, and many garage hobbyists. This book presents fifteen technical papers that are written at a level that makes them easily accessible to a broad technical audience, describing the technology behind most of the robotic vehicles that participated in this famous race. The papers describe each team's driverless vehicle, race strategy, and insights. As a whole, they present the state of the art in autonomous vehicle technology, and offer a glimpse of future technology for tomorrows driverless cars. This book will serve as an authoritative, archival source for the DARPA Grand Challenge and a must have for robotics students and researchers, since it describes the state of the art in perception, planning and control.
---
paper_title: Model-predictive active steering and obstacle avoidance for autonomous ground vehicles

paper_content:

This paper presents a model-predictive approach for trajectory generation of unmanned ground vehicles (UGVs) combined with a tire model. An optimal tracking problem while avoiding collision with obstacles is formulated in terms of cost minimization under constraints. Information on obstacles is incorporated online in the nonlinear model-predictive framework as they are sensed within a limited sensing range. The overall problem is solved online with nonlinear programming. For the local path regeneration upon detecting new obstacles, the cost function is augmented using the obstacle information in two methods. The first method uses the distance from the UGV to the nearest detected obstacle, and the second method uses the parallax information from the vehicle about the detected obstacles. Simulation results in cluttered and dynamic environments show that the modified parallax method effectively reflects the threat of the obstacles to the UGV considering the dimension and state variables of the vehicle, showing clear improvements over the distance-based methods.
---
paper_title: Model predictive control: Theory and practice - A survey

paper_content:

Abstract We refer to Model Predictive Control (MPC) as that family of controllers in which there is a direct use of an explicit and separately identifiable model. Control design methods based on the MPC concept have found wide acceptance in industrial applications and have been studied by academia. The reason for such popularity is the ability of MPC designs to yield high performance control systems capable of operating without expert intervention for long periods of time. In this paper the issues of importance that any control system should address are stated. MPC techniques are then reviewed in the light of these issues in order to point out their advantages in design and implementation. A number of design techniques emanating from MPC, namely Dynamic Matrix Control, Model Algorithmic Control, Inferential Control and Internal Model Control, are put in perspective with respect to each other and the relation to more traditional methods like Linear Quadratic Control is examined. The flexible constraint handling capabilities of MPC are shown to be a significant advantage in the context of the overall operating objectives of the process industries and the 1-, 2-, and ∞-norm formulations of the performance objective are discussed. The application of MPC to non-linear systems is examined and it is shown that its main attractions carry over. Finally, it is explained that though MPC is not inherently more or less robust than classical feedback, it can be adjusted more easily for robustness.
---
paper_title: A Predictive Controller for Autonomous Vehicle Path Tracking

paper_content:

This paper presents a model predictive controller (MPC) structure for solving the path-tracking problem of terrestrial autonomous vehicles. To achieve the desired performance during high-speed driving, the controller architecture considers both the kinematic and the dynamic control in a cascade structure. Our study contains a comparative study between two kinematic linear predictive control strategies: The first strategy is based on the successive linearization concept, and the other strategy combines a local reference frame with an approaching path strategy. Our goal is to search for the strategy that best comprises the performance and hardware-cost criteria. For the dynamic controller, a decentralized predictive controller based on a linearized model of the vehicle is used. Practical experiments obtained using an autonomous ldquoMini-Bajardquo vehicle equipped with an embedded computing system are presented. These results confirm that the proposed MPC structure is the solution that better matches the target criteria.
---
paper_title: Predictive path tracking of mobile robots. Application to the CMU NavLab

paper_content:

Presents a new path tracking method and its application to an autonomous vehicle, the NavLab (road-worthy truck modified for research in outdoor navigation). The method applies predictive control theory to obtain the appropriated steering angle taking into account the vehicle velocity. The authors consider both the single-input single output case and the multivariable formulation of the predictive control problem. Moreover they describe the implementation of the NavLab controller. >
---
paper_title: Linear time-varying model predictive control and its application to active steering systems: Stability analysis and experimental validation

paper_content:

A Model Predictive Control (MPC) approach for controlling an Active Front Steering (AFS) system in an autonomous vehicle is presented. At each time step a trajectory is assumed to be known over a finite horizon, and an MPC controller computes the front steering angle in order to best follow the desired trajectory on slippery roads at the highest possible entry speed. We start from the results presented in [2], [6] and formulate the MPC problem based on successive on-line linearization of the nonlinear vehicle model (LTV MPC). We present a sufficient stability conditions for such LTV MPC scheme. The condition is derived for a general class of nonlinear discrete time systems and results into an additional convex constraint to be included in the LTV MPC design. For the AFS control problem, we compare the proposed LTV MPC scheme against the LTV MPC scheme in [6] where stability has been enforced with an ad-hoc constraint. Simulation and experimental tests up to 21 m/s on icy roads show the effectiveness of the LTV MPC formulation.
---
paper_title: Model predictive control strategy for smooth path tracking of autonomous vehicles with steering actuator dynamics

paper_content:

Path tracking control is one of the most important functions for autonomous driving. In path tracking control, high accuracy and smooth tracking are required for safe and comfort driving. In order to meet these requirements, model predictive control approaches, which can obtain an optimized solution with respect to a predefined path, have been widely studied. Conventional predictive controllers have been studied based on a simple bicycle model. However, the conventional predictive controllers have a performance limitation in practical challenges due to the difference between the simple bicycle model and the actual vehicle. To overcome this limitation, the actuator dynamics of the steering system should be incorporated into the control design. In this paper, we propose a model predictive control based path tracking control algorithm to achieve the accurate and smooth tracking by incorporating the dynamic characteristics of the steering actuation system. In the proposed control algorithm, an optimal trajectory of the steering command is calculated by applying a quadratic programming optimization method. The proposed controller was verified by computer simulation with various driving scenarios. The simulation results show that the proposed controller can improve the tracking performance.
---
paper_title: Predictive Active Steering Control for Autonomous Vehicle Systems

paper_content:

In this paper, a model predictive control (MPC) approach for controlling an active front steering system in an autonomous vehicle is presented. At each time step, a trajectory is assumed to be known over a finite horizon, and an MPC controller computes the front steering angle in order to follow the trajectory on slippery roads at the highest possible entry speed. We present two approaches with different computational complexities. In the first approach, we formulate the MPC problem by using a nonlinear vehicle model. The second approach is based on successive online linearization of the vehicle model. Discussions on computational complexity and performance of the two schemes are presented. The effectiveness of the proposed MPC formulation is demonstrated by simulation and experimental tests up to 21 m/s on icy roads
---
paper_title: Linear time-varying model predictive control and its application to active steering systems: Stability analysis and experimental validation

paper_content:

A Model Predictive Control (MPC) approach for controlling an Active Front Steering (AFS) system in an autonomous vehicle is presented. At each time step a trajectory is assumed to be known over a finite horizon, and an MPC controller computes the front steering angle in order to best follow the desired trajectory on slippery roads at the highest possible entry speed. We start from the results presented in [2], [6] and formulate the MPC problem based on successive on-line linearization of the nonlinear vehicle model (LTV MPC). We present a sufficient stability conditions for such LTV MPC scheme. The condition is derived for a general class of nonlinear discrete time systems and results into an additional convex constraint to be included in the LTV MPC design. For the AFS control problem, we compare the proposed LTV MPC scheme against the LTV MPC scheme in [6] where stability has been enforced with an ad-hoc constraint. Simulation and experimental tests up to 21 m/s on icy roads show the effectiveness of the LTV MPC formulation.
---
paper_title: Predictive Active Steering Control for Autonomous Vehicle Systems

paper_content:

In this paper, a model predictive control (MPC) approach for controlling an active front steering system in an autonomous vehicle is presented. At each time step, a trajectory is assumed to be known over a finite horizon, and an MPC controller computes the front steering angle in order to follow the trajectory on slippery roads at the highest possible entry speed. We present two approaches with different computational complexities. In the first approach, we formulate the MPC problem by using a nonlinear vehicle model. The second approach is based on successive online linearization of the vehicle model. Discussions on computational complexity and performance of the two schemes are presented. The effectiveness of the proposed MPC formulation is demonstrated by simulation and experimental tests up to 21 m/s on icy roads
---
paper_title: LPV design of fault-tolerant control for road vehicles

paper_content:

The aim of the paper is to present a supervisory decentralized architecture for the design and development of reconfgurable and fault-tolerant control systems in road vehicles. The performance specifcations are guaranteed by the local controllers, while the coordination of these components is provided by the supervisor. Since monitoring components and the FDI flters provide the supervisor with information about the various vehicle maneuvers and the different fault operations, it is able to make decisions about the necessary interventions into the vehicle motions and guarantee the re-confgurable and fault-tolerant operation of the vehicle. The design of the proposed reconfgurable and fault-tolerant control is based on an LPV method that uses monitored scheduling variables during the operation of the vehicle.
---
paper_title: Integrated vehicle dynamics control via coordination of active front steering and rear braking

paper_content:

This paper investigates the coordination of active front steering and rear braking in a driver-assist system for vehicle yaw control. The proposed control system aims at stabilizing the vehicle while achieving a desired yaw rate. During normal driving situations, active steering control is involved for steerability enhancement. However, when the vehicle reaches the handling limits, both steering and braking collaborate together to ensure vehicle stability. The coordination of these actuators is achieved through a suitable gain scheduled LPV (Linear Parameter Varying) controller. The controller is synthesized within the LMI (Linear Matrix Inequalities) framework, while warranting robust H1 performances. Time and frequency simulation results show the effectiveness of the proposed control scheme when the vehicle is subject to various critical driving situations.
---
paper_title: Vehicle dynamics and control

paper_content:

1. Introduction.- 2.Lateral Vehicle Dynamics.- 3. Steering Control For Automated Lane Keeping.- 4. Longitudinal Vehicle Dynamics.- 5. Introduction to Longitudinal Control.- 6. Adaptive Cruise Control.- 7. Longitudinal Control for Vehicle Platoons.- 8. Electronic Stability Control.- 9. Mean Value Modeling Of SI and Diesel Engines.- 10. Design and Analysis of Passive Automotive Suspensions.- 11. Active Automotive Suspensions.-12. Semi-Active Suspensions.- 13. Lateral and Longitudinal Tires Forces.- 14. Tire-Road Friction Measurement on Highway Vehicles.- 15. Roll Dynamics and Rollover Prevention.- 16. Dynamics and Control of Hybrid Gas Electric Vehicles.
---
paper_title: The Design of an Integrated Control System in Heavy Vehicles Based on an LPV Method

paper_content:

In this paper an integrated control structure with individual active control mechanisms, i.e. active anti-roll bars, active suspensions, and an active brake mechanism, is proposed. Its purpose is to improve rollover prevention, passenger comfort, road holding and guarantee the suspension working space. In the control design the performance specifications both for rollover and suspension problems, and the model uncertainties are taken into consideration. In the weighting strategy of control design fault information is also taken into consideration. The design of the control system is based on an H ∞ Linear Parameter Varying (LPV) method. To enhance the performance of the controlled system, the control mechanism is extended with a prediction procedure, in which an observer-based prediction algorithm is proposed.
---
paper_title: Gain-scheduled integrated active steering and differential control for vehicle handling improvement

paper_content:

This paper presents a gain-scheduled active steering control and active differential design method to preserve vehicle stability in extreme handling situations. A new formulation of the bicycle model in which tyre slip angles, longitudinal slips and vehicle forward speed appear as varying vehicle parameters is introduced. Such a model happens to be useful in the design of vehicle dynamics controllers scheduled by vehicle parameters: after having expressed the parametric bicycle model in the parametric descriptor form, gain-scheduled active steering and differential controllers are designed to improve vehicle handling at ‘large’ driver-commanded steering angles. Simulations reveal the efficiency of the selected modelling and controller design methodology in enhancing vehicle handling capacity during cornering on roads with varying adhesion coefficient and under variable speed operation.
---
paper_title: Autonomous vehicle steering using explicit LPV-MPC

paper_content:

In this paper a novel control approach for Active Steering of automotives is presented. Explicit LPV-MPC is employed to derive a controller which requires only little online computations. The achieved control performance is compared to nonlinear MPC and explicit linear MPC in a double lane-change maneuver at different driving speeds.
---
paper_title: Toward global chassis control by integrating the brake and suspension systems

paper_content:

A control structure that integrates active suspensions and an active brake is proposed to improve the safety of vehicles. The design is based on an Hinf control synthesis extended to LPV systems and uses a parameter dependent Lyapunov function. In an emergency, such as an imminent rollover, the safety requirement overwrites the passenger comfort demand by tuning the performance weighting functions associated with the suspension systems. If the emergency persists active braking is applied to reduce the effects of the lateral load transfers and thus the rollover risk. The solution is facilitated by using the actual values of the so-called normalized lateral load transfer as a scheduling variable of the integrated control design. The applicability of the method is demonstrated through a complex simulation example containing vehicle maneuvers.
---
paper_title: A new semi-active suspension control strategy through LPV technique

paper_content:

This paper is concerned with the design and the analysis of a semi-active suspension controller. In the recent years different kinds of semi-active control strategies, like two-state Skyhook, LQ-clipped or model-predictive control, have already been developed in the literature. In this paper, a new semi-active suspension control strategy that a priori satisfies the principal limitations of a semi-active suspension actuator (dissipative constraint and force bounds) is introduced using the tools of the linear parameter varying (LPV) theory. This new approach exhibits some interesting advantages (implementation, performance flexibility, robustness, etc.) compared to already existing methods. Both industrial criterion based evaluation and simulations on a nonlinear quarter vehicle model are performed to show the efficiency of the method and to validate the theoretical approach.
---
paper_title: Hybrid Parameter-Varying Model Predictive Control for lateral vehicle stabilization

paper_content:

In this paper the concept of Hybrid Parameter-Varying Model Predictive Control (HPV-MPC) is applied for lateral vehicle stabilization. Parameter-varying in the MPC context means that a prediction model with non-constant, parameter-varying system matrices is employed. In the investigated scenario, the displacement of a car on an icy road under a side wind gust shall be mitigated. In order to explore a possible reduction of online computations and the inherent degradation of control performance, the nonlinear model of the lateral dynamics is approximated in various ways. A comparison between controllers using prediction models varying from the full nonlinear model, as an indication for the maximal achievable performance, to a linear model has been performed. Particular emphasis was put on the hybrid parameter-varying prediction model, to investigate their potential in terms of computational effort and control performance.
---

Title: A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles

Section 1: INTRODUCTION
Description 1: Discuss the historical background, societal motivations, and recent progress of autonomous vehicle research.

Section 2: OVERVIEW OF THE DECISION-MAKING HIERARCHY USED IN DRIVERLESS CARS
Description 2: Describe the decision-making architecture for self-driving cars, listing the responsibilities of each hierarchical component.

Section 3: Route Planning
Description 3: Discuss the methods for route planning in self-driving vehicles, focusing on finding an optimal path through a road network.

Section 4: Behavioral Decision Making
Description 4: Explore the behavioral layer responsible for making decisions based on the perceived environment and driving rules.

Section 5: Motion Planning
Description 5: Discuss how the motion planning system translates driving behaviors into feasible paths or trajectories.

Section 6: Vehicle Control
Description 6: Explain feedback control methods used to adjust vehicle actuators and correct tracking errors of the vehicle.

Section 7: MODELING FOR PLANNING AND CONTROL
Description 7: Survey different modeling techniques for vehicle behavior used in motion planning and control systems.

Section 8: MOTION PLANNING
Description 8: Provide a comprehensive review of motion planning algorithms, focusing on path and trajectory planning.

Section 9: Path Planning
Description 9: Define the problem of path planning, its complexity, and survey different methodologies including variational, graph search, and incremental approaches.

Section 10: Trajectory Planning
Description 10: Discuss trajectory planning approach needed for dynamic environments and complex constraints.

Section 11: Variational Methods
Description 11: Explore direct and indirect trajectory optimization methods used for path and trajectory planning.

Section 12: Graph Search Methods
Description 12: Review graph search strategies, including lane graphs, geometric methods, and sampling-based methods for path planning.

Section 13: Incremental Search Techniques
Description 13: Explain incremental motion planning methods, including tree-based exploration strategies for finding feasible paths.

Section 14: Practical Deployments
Description 14: Highlight practical motion planning techniques used in real-world autonomous vehicle systems.

Section 15: Path Stabilization for the Kinematic Model
Description 15: Survey different path stabilization control methods specifically for the kinematic vehicle model.

Section 16: Trajectory Tracking Control for the Kinematic Model
Description 16: Discuss control approaches for tracking a reference trajectory in a kinematic vehicle model.

Section 17: Predictive Control Approaches
Description 17: Analyze model predictive control techniques applicable to both path and trajectory stabilization in different vehicle models.

Section 18: Linear Parameter Varying Controllers
Description 18: Review linear parameter varying control methods, including robust control and gain scheduling techniques.

Section 19: CONCLUSION
Description 19: Summarize the state of the art in driverless vehicle control and motion planning, and identify areas for future research.