Thanks to Tom Mitchell, Leslie Kaelbling, Reid Simmons, Drew Bagnell, Aaron Courville, Mike Montemerlo and Joelle Pineau for useful comments and insight into this work. Nicholas Roy was funded by the National Science Foundation under ITR grant # IIS-0121426. Geoffrey Gordon was funded by AFRL contract F30602-01-C-0219, DARPA's MICA program, and by AFRL contract F30602-98-2-0137, DARPA's CoABS program.