Sensing, Actuation, and Computation
6-17 August 2007, University of Vaasa, Finland
Instructor: Steve LaValle, University of Illinois (UIUC)


Interaction with the physical world through our machines becomes increasingly important as we expand the frontiers of computer science, the Internet, and information technology. We are faced with new challenges as we design engineering systems to solve problems such as environmental monitoring, security sweeping and surveillance, automated transportation, and even household maintenance.

In such cyber-physical systems, information arrives directly from sensors. Furthermore, physical devices may be commanded to move around to improve information gathering capabilities or accomplish physical tasks. Successful design and deployment of such systems depends on understanding the interplay between sensing, actuation, and computation. By considering these together, one central theme emerges: Understand the information requirements of a particular task so that the complexity of the overall system can be reduced. This offers many benefits, such as improving robustness and reducing costs.

This course provides fundamental concepts for reasoning about the information spaces that arise in these systems. Inferences are made from sensing and actuation information in combination with geometric, topological, or statistical models. This leads to approaches that do not require full state estimation. They instead work by directly manipulating information states. In many cases, the sensing requirements may be dramatically reduced. This leads sensor-based algorithms and even theoretical computation models that depart from standard Turing machines.


Sensor models, visibility sensors, sensor networks, inference problems, information spaces, actuation models, minimalist planning, visual sweeps, searching with limited information, pursuit-evasion games, sensor-based navigation tasks, coordinate-free models, stochastic models, nontraditional communication models, sensor-centric models of computation, decidability and complexity for actuated sensor systems.

Daily Schedule (Mon-Fri):
09:15-10:30 : Lecture (Part 1)
10:45-12:00 : Lecture (Part 2)
15:15-16:30 : Discussion

Lecture 1 Lecture 2 Lecture 3 Lecture 4 Lecture 5
Lecture 6 Lecture 7 Lecture 8 Lecture 9 Lecture 10
Lecture 11 Lecture 12 Lecture 13 Lecture 14 Lecture 15
Lecture 16 Lecture 17
Discussion 1 Discussion 2 Discussion 3 Discussion 4 Discussion 5
Discussion 6 Discussion 7 Discussion 8 Discussion 9

Lectures: (tentative)
Date Lecture Topics Sources
Week 1
  6 Aug  Overview, physical sensors  
  7 Aug  Abstract sensing models, configuration spaces, state spaces  
  8 Aug  Time, sensor histories, inference problems  
  9 Aug  Inference problems, introducing actuation  
10 Aug  Exploring grids and graphs  
Week 2
13 Aug  General I-space concepts  
14 Aug  Visibility problems, pursuit-evasion  
15 Aug  Landmark-based navigation, on-line problems  
16 Aug  Decidability, dominance, complexity  
17 Aug  Probabilistic I-spaces  

Related Textbook: Planning Algorithms, S. M. LaValle, Cambridge University Press, 2006. Also available for free download at