Planning Algorithms

Cambridge University Press, 2006, 842 pages.
To buy a hard copy: Cambridge Amazon Barnes&Noble Kinokuniya
See the Planning Algorithms page to download a FREE COPY.
Now available in Chinese!

This book presents a unified treatment of many different kinds of planning algorithms. The subject lies at the crossroads between robotics, control theory, artificial intelligence, algorithms, and computer graphics. The particular subjects covered include motion planning, discrete planning, planning under uncertainty, sensor-based planning, visibility, decision-theoretic planning, game theory, information spaces, reinforcement learning, nonlinear systems, trajectory planning, nonholonomic planning, and kinodynamic planning. The material grew from courses I taught at UIUC, Stanford, and Iowa State.

You are welcome to download and print out the whole manuscript for your own use.


Sensing and Filtering:

A Fresh Perspective Based on Preimages and Information Spaces

Now Publishers Inc., 2012, 134 pages.
To buy a hard copy: Now Publishers Amazon Barnes&Noble
Here is a full, FREE draft.

Where do robots get their information? For a given task, what information is actually necessary? What is even meant by "information"? These questions lie at the heart of robotics and fall under the realm of sensing and filtering. In Sensing and Filtering, the author presents an unusual view of these subjects by characterizing the uncertainty due to the many-to-one mappings between the world and sensor readings. This is independent of noise-based uncertainty and reveals critical structure about the possible problems that can be solved using specific sensors. The set of all sensor models is arranged into a lattice that enables them to be compared for purposes of interchangeability. Filters, which combine sensor observations, are expressed in terms of information states (not information theory), a concept that was introduced in decision and control theory. Sensing and Filtering provides the reader with modeling tools and concepts for developing robotic systems that accomplish their tasks while carefully avoiding the reconstruction of unnecessary state information. This is in contrast to the approach usually taken in planning and control, which is to fully reconstruct and maintain the state at all times. The new approach may enable simple, robust, and inexpensive solutions to tasks such as navigation, topological mapping, coverage, patrolling, tracking, and pursuit-evasion.

Note: This short monograph is a precursor to a larger, broader book that LaValle is writing on sensing and filtering, which will include the main material from the monograph as well as coverage of powerful, existing models and methods such as Bayesian filtering, particle filtering.