Cognition
From Princeton Autonomous Vehicle Engineering
Cognition takes data from Perception about the environment, from State Estimation the current pose of the vehicle (x, y, theta, v etc.) and, given the vehicle's goal pose, plan a near-optimal obstacle-free path/trajectory from the current pose to the goal pose. The generated trajectory is then passed on to Actuation.
Team Lead: Tony
Contents |
Recent News
Overview
Our general cognition framework follows closely to that of Stanford and CMU's entry to the Urban Challenge, because it is the most robust to uncertainties and unexpected scenarios in the environment. One of the reasons for this is that the system is very modular, and each piece of the puzzle can be separately changed and tested, making it easy to understand how specific parts of the algorithm affect the behavior of the vehicle. The different modules are listed below. The basic idea is to use a graph search algorithm to search through the configuration space (basically an n-dimensional space where each point describes a different pose of the vehicle). Before we start the search, we need to be smart about how to construct this graph, because we want to take into account the kinodynamic constraints, i.e. minimum turn radius, inertia, etc. Therefore the nodes of the graph should be connected by paths that the car can follow, rather than just straight edges. The final piece of the puzzle is how to optimally construct the environmental map to deal with uncertainties and such. Here are some papers that detail similar approaches.
To get a general idea about how navigation systems fit in with everything, read these
- Tartan Racing: A Multi-Modal Approach to the DARPA Urban Challenge CMU's tech paper for the Urban Challenge
- Boss - a reasoning framework for autonomous urban driving Also about CMU's entry, describes how the cognition system fits in with everything
- Stanford's tech paper for Urban Challenge
Ok, now for more details describing the same platform, in a 2 part paper
- Motion Planning in Urban Environments: Part I
- Motion Planning in Urban Environments: Part II
- Planning Long Dynamically-Feasible Maneuvers for Autonomous Vehicles Basically the same stuff as above. The authors must have been trying to squeeze as much juice as this thing as possible.
- Practical Search Techniques in Path Planning for Autonomous Driving Ok this one is details for Stanford's entry
- fast and feasible deliberative motion planner for dynamic environments Navigation for Mars rover, but similar design
- Finally Google cache of a page with a bunch of links to courses and other motion planning resources.
One final note: There's actually two separate but equally important parts to local navigation. We have unstructured navigation, which is what I wrote about above, that takes place in for example parking lots, messy intersections, off-roads, pulling into a small side road, parallel parking etc. Then we have structured navigation, where road lanes basically gives you your desired path, and all you have to do is follow it. Because unstructured navigation basically encompasses all the components of structured navigation, we'll begin by focusing on unstructed nav. Structured nav will almost come for free (hopefully!)
Sub-Projects
Graph Search
This is the most important part! This is the algorithm that actually finds the path you want. Also, this may be the right place to deal with dynamic obstacles. Currently, we have a completed but untested and somewhat optimized version of Anytime D*, which work pretty well. This is based on the A* algorithm, so if you don't know A*, this is a simple introduction. Then read about the D* lite algorithm, before tackling the first paper. Here is a paper of CMU's actual implementation.
An alternative is using RRT trees (Random Rapidly-expanding Trees), which is a probabilistic algorithm. A fast, anytime version is the Anytime Dynamic RRT, created by the same guys who created the Anytime D*. As far as I know, these are pretty much the only two algorithm that has a chance of doing anything useful in real time. There are a lot of resources online about RRTs and Probabilistic Roadmaps. I only know of one authoritative work on planning algorithms in general, which is a thick ass book called Planning Algorithms. Very tough read, very theoretical (it uses differential geometry and Lagrangian mechanics throughout), but builds up from the very basics. But the chapters are somewhat independent, so you can pick and choose what you want to read.
Trajectory Generation
The simplest thing to implement, and what you should probably do first if you want to take up this project is the Reed-Shepp paths.
- The original paper for the Reed-Shepp path
- For a good overview of things, read the beginning of this paper. A very good lit review starting on the second page! Of course, then read the rest.
- From Reeds and Shepp's to Continuous-Curvature Paths A 2004 recent paper that fixes the curvature discontinuities of RS paths. Not too difficult paper.
- Nonlinear Trajectory Generation from Caltech There's a NTG library from caltech that may be useful
- Reactive Nonholonomic Trajectory Generation via Parametric Optimal Control Ahh too much control theory! This may be an improvement over the previous paper, but I don't know enough control theory/math to understand it.
- A more general control-theoretic approach uses the idea of "differential flatness". I don't have any links though unfortunately.
- Cubic curvature polynomials
Lattice construction
This project is about creating a good representation of the graph whose edges is a set of trajectories generated above. The goal is to use a minimal set of trajectories to construct the full lattice. You should also think about how to make multi-resolution lattices, because we care most about our immediate surroundings and reducing the resolution would give a HUGE speed-up to the search, whatever algorithm we use.
- Optimal, Smooth, Nonholonomic Mobile Robot Motion Planning in State Lattices
- Differentially Constrained Mobile Robot Motion Planning in State Lattices
Map Representation
I haven't looked into this too much. Some information is in Stanfords Darpa paper (the second one listed). This should be a relatively short project, but you will still learn a lot of stuff doing it like Voronoi diagrams. You will also design the actual data structures that hold the map for efficient access. This may be another place to deal with dynamic obstacles.
Path Tracking
To be added
To Do
- Consult with the Perception team to determine what data they are capable of giving us.
- Develop a specific means of interfacing with Perception.
- Develop a specific means of interfacing with Actuation
- Create internal communication API's. Decide if we want multi-threading. '
- Figure out exactly how to integrate everything.
