Advanced Lecture and Project
Suggested Topics and
The following are recent papers in cognitive robotics recommended by many of the key researchers in the field. We recommend that you draw upon this reading list during the development of your advanced lecture and course project. This page is not definitive, and may be refined over the semester.
Note that many of these references are only partial, but they should offer clues as to where to look. Also take ample advantage of the web's search capabilities. Most authors these days post their recent papers. In addition, the LCS reading room on the first floor of NE43, has copies of many Journals and Conferences in Artificial Intelligence.
In many fields high quality technical papers appear in journals. In the field of artificial intelligence you’ll find most of the cutting edge research in conferences, most of which are considered journal quality. Conferences relevant to intelligent embedded systems include the National Conference on Artificial Intelligence (AAAI), International Joint Conference on Artificial Intelligence (IJCAI), Autonomous Agents (AA), Artificial Intelligence in Planning and Scheduling (AIPS), Reasoning Under Uncertainty (UAI), Knowledge Representation and Reasoning (KRR), Machine Learning (ML), and Hybrid Systems (HS).
There are many parallel journals, including the venerable Artificial Intelligence Journal (AIJ), and the more hip, online Journal of Artificial Intelligence Research (JAIR), Machine Learning and the Journal of Constraint Systems.
The following suggested papers and URLs are provided thanks to:
Craig Boutilier, Adnan Darwiche, Vineet Gupta, Leslie Kaelbling, Henry Kautz, Pandu Nayak, Judea Pearl, Bart Selman, Dave Smith, Manuela Veloso, Dan Weld and Feng Zhao.
Asada and Kitano (eds.), RoboCup-98: Robot Soccer World Cup II, , Springer Verlag, 1999.
Manuela Veloso, Michael Bowling, Sorin Achim, Kwun Han and Peter Stone. The CMUnited-98 Champion Small Robot Team, in Asada and Kitano (eds.) 77-92.
Autonomous Space Probes:
Remote Agent Autonomous Control Experiment
Esterel and Lustre are the primary languages, and are doing very well for embedded systems programming.
Esterel language page,
This page distributes the entire Esterel system, and has papers and pointers to the other languages.
State Estimation and Mapping:
Stephen Se, David Lowe and Jim
Little, Mobile robot localization and mapping with uncertainty using
scale-invariant visual landmarks, International Journal of Robotics Research,
21, 8 (2002), pp. 735-758.
S. Thrun, D. Fox, W. Burgard,
and F. Dellaert. Robust monte carlo localization for mobile robots. Artificial
Intelligence, 128(1-2), 2001.
A hybrid approach to particle filters for localization.
Paul M. Newman and John
J. Leonard Consistent Convergent Constant Time SLAM. International Joint
Conference on Artificial Intelligence, Acapulco Mexico, August 2003.
A constant-time map-building algorithm.
S. Thrun, D. Koller,
Z. Ghahramani, H. Durrant-Whyte, and A.Y. Ng. Simultaneous mapping and
localization with sparse extended information filters:theory and initial
results. In Workshop on Algorithmic Foundations of Robotics, Nice, France,
Another constant-time map-building algorithm.
Mark A. Paskin (2003). Thin
Junction Tree Filters for Simultaneous Localization and Mapping. In G. Gottlob
and T. Walsh eds., Proceedings of the Eighteenth International Joint
Conference on Artificial Intelligence
Yet another constant map-building algorithm.
Vandi Verma, Geoff Gordon, Reid
Simmons, and Sebastian Thrun, Particle Filters for Rover Fault Diagnosis, IEEE
Robotics & Automation Magazine special issue on Human Centered Robotics and
Dependability, June 2004.
Fault State Estimation.
Hanna Pasula, Stuart Russell, Michael Ostland, and Ya'acov Ritov, ``Tracking
many objects with many sensors.'' In Proc. IJCAI-99, Stockholm, 1999
Traffic state estimation using particle filters and Bayesian estimation.
Mariott and Stuckey, The book "Programming with Constraints".
Van Hentenryck, Saraswat et al., Strategic directions in constraint programming, ACM Computing Surveys, 1996. (in directory).
Gupta et al., TCC.
There is a huge number of materials available on constraint programming.
Leslie Pack Kaelbling and Michael L. Littman and Andrew W. Moore, Reinforcement
Learning: A Survey, Journal of Artificial Intelligence Research, 1996, v. 4,
Very nice short survey of reinforcement learning.
Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction,
A very nice treatment of reinforcement learning from an introductory level: very well presented and an easy read.
P. Bertsekas and John. N. Tsitsiklis, Neuro-dynamic Programming, Athena,
Reinforcement learning in much more detail (a bit less accessible as an introduction than Sutton's book, but very comprehensive in the treatment of approximation).
Christopher J. C. H. Watkins and Peter Dayan, Q-Learning, Machine Learning, v. 8, 279-292, 1992.
Andrew W. Moore and Christopher G. Atkeson, Prioritized Sweeping---Reinforcement Learning with Less Data and Less Time, Machine Learning, v 13, 103-130, 1993.
Andrew W. Moore and Christopher G. Atkeson, The Parti-game algorithm for Variable Resolution Reinforcement Learning in Multidimensional State Spaces, Machine Learning, v 21, 199-234, 1995.
Use of function approximation for reinforcement learning:
Gerald J. Tesauro, TD-Gammo, A Self-teaching Backgammon Program, Achieves Master-Level Play, Neural Computation, v 6, 215-219, 1994.
John H. Tsitsiklis and Benjamin Van Roy, Feature-Based Methods for Large Scale DynamicProgramming, Machine Learning, v. 22, 59--94, 1996.
Decision Theoretic Planning and Markov Decision Processes:
AI Magazine 20(2).
Boutilier and Thomas Dean and Steve Hanks, Decision Theoretic Planning:
Structural Assumptions and Computational Leverage, Journal of Artificial
Intelligence Research , v 11, 1-94, 1999.
Longer survey covering AI-style representation and solution methods.
The use of search techniques to solve MDPs
A. G. Barto and S. J. Bradtke and S. P. Singh, Learning to Act using Real-Time Dynamic Programming, Artificial Intelligence, v. 72 (1-2) 81-138, 1995.
The use of AI style representations and planning-style abstraction and regression techniques
Richard Dearden and Craig Boutilier, Abstraction and Approximate Decision Theoretic Planning, artificial intelligence, v. 89, 1997, 219-283. Also see AAAI-94.
Craig Boutilier and Richard Dearden and Moises Goldszmidt, Stochastic Dynamic Programming with Factored Representations, Artificial Intelligence, to appear, 1999 (see also IJCAI-95).
The use of sampling techniques
Kearns and Yishay Mansour and Andrew Y. Ng, A Sparse Sampling Algorithm for
Near-optimal Planning in Large Markov Decision Processes, IJCAI, 1999.
Partially Observable Markov Decision Processes:
William S. Lovejoy, A Survey of Algorithmic Methods for Partially Observed Markov Decision Processes, Annals of Operations Research, vol. 28, 47-66 , 1991.
George E. Monahan, A Survey of Partially Observable Markov Decision Processes: Theory, Models and Algorithms, Journal of Management Science, vol. 28, page 1-16, 1982.
Incremental pruning for POMDPs:
R. Cassandra and Michael L. Littman and Nevin L. Zhang, Incremental Pruning: A Simple,
Fast, Exact Method for POMDPs, UAI, Providence, RI, 54-61, 1997.
Makes a big computational difference.
State of the art:
Pascal Poupart and Craig
Boutilier, Value-directed Compression of POMDPS, NIPS, Vancouver, BC, 1547-1554, 2003.
Linear compression of POMDPS.
Joelle Pineau, Geoff
Gordon and Sebastian Thrun, Point-based value iteration: An anytime algorithm
for POMDPs, IJCAI, Acapulco, Mexico 2003.
The fastest solver of large POMDPs available.
Model-based Autonomous Systems:
Diagnosis, repair and control.
Hamscher, L. Console and J. de Kleer (Ed.),
Proceedings of the International Workshop on Principles of Diagnosis.
Qualitative modeling and simulation.
Weld and J. de Kleer (Ed.),
J. de Kleer and B. Williams (Ed.), Special issue on qualitative reasoning about physical systems II, Artificial Intelligence, 51, 1991.
Proceedings of the International Workshop on Qualitative Reasoning about Physical Systems.
Planning with Discrete Events:
Daniel Weld, An introduction to least-commitment planning, AI Magazine, 27--61, Winter, 1994.
Daniel Weld, Recent advances in AI planning. AI Magazine,
summer 1999. http://www.aaai.org/Papers/Magazine/20-02/Weld.pdf
Covers satplan, graphplan, sat engines and reactive planning and execution.
Rao, recent planning tutorial at AAAI or IJCAI.
Proceedings of the International Conference on Artificial Intelligence Planning and Scheduling Systems.
Causal Link Planning
See Weld survey, 1994.
Manuela Veloso and Jim Blythe. Linkability: Examining causal link commitments in partial-order planning, Proceedings of the Second International Conference on AI Planning Systems, 170-175, June 1994.
Planning as propositional satisfiability
and Selman, on Satplan planner.
and Selman, on Black box constraint solver.
A. and Furst, M.L. (1995). Fast planning through planning graph analysis. Proc.
Hector Geffner, AIPS submission, 2000?
Weld, SGP paper, AAAI, 1998.
Has a free lisp implementation, but it's not super scalable i.e. O(number of possible worlds). Paper is pretty technical.
Model-based Reactive Planning:
B.C. and P.P. Nayak, "A Reactive Planner for a Model-based
Executive," Proceedings of the International Joint Conference on
Rune Jensen and Manuela Veloso, OBDD-based universal planning: Specifying and solving planning for synchronized agents in non-deterministic domains, Journal of Artificial Intelligence Research, 2000, to appear.
Interleaved Planning and Execution:
Ambros-Ingerson, J and Steel, S. "Integrating Planning, Execution, and Monitoring", AAAI, 1988, pages= 735--740.
Keith Golden, paper in International Conference on AI Planning and Scheduling, 1998?.
James Firby, An Investigation into Reactive Planning in Complex Domains. AAAI, 1987?, 202--206
Reid Simmons, Task Control Architecture. See Reid Simmons web page, www.cs.cmu.edu.
Georgeff and Lansky, Procedural Reasoning System. Reference TBD.
Learning in Planning and Execution:
Manuela Veloso, Jaime Carbonell, M.Alicia Perez, Daniel Borrajo, Eugene Fink, and Jim Blythe. Integrating planning and learning: The PRODIGY architecture, Journal of Experimental and Theoretical Artificial Intelligence, 7(1):81-120, 1995.
Karen Haigh and Manuela Veloso. Learning situation-dependent costs: Improving planning from probabilistic robot execution. Robotics and Autonomous Systems, 1999.
Jim Blythe and Manuela Veloso, Analogical replay for efficient conditional planning. Proceedings of AAAI-97, 668--673.
Scott Lenser and Manuela Veloso, Sensor Resetting Localization for Poorly Modelled Mobile Robots, ICRA-2000, to appear.
Planning and Execution with Resources and Time:
Smith, Frank and Jonsson, "Bridging the gap between planning and scheduling." Survey paper. See Professor Williams for a copy of the paper.
Weld and Smith , paper on temporal graphplan, IJCAI 1999.
Jonsson, Morris, Muscettola and Rajan, paper on the remote agent planner, AIPS 2000.
Penberthy & Weld, paper on Zeno, AAAI, 1994 .
Joslin & Pollack, paper on Descarte, AAAI, 1996.
Beck & Fox, AI Magazine 19(4).
Wolfman & Weld, paper on LPSAT, IJCAI, 1999.
Kautz & Walser, paper on ILP planning, AAAI, 1999
Vossen et al, IJCAI, 1999.
Penberthy & Weld, paper on Zeno, AAAI, 1994.
Executing Temporal Plans:
Muscettola and others on efficient plan running. See Professor Williams for suggested papers.
Bayesian Networks in Embedded Systems:
Daphne Koller et al.,
Object-Oriented Bayesian Networks,UAI, 1997.
A structured language for Bayes nets (best student paper award)..
Daphne Koller et al., Effective
Bayesian Inference for Stochastic Programs, AAAI 97.
A general inference procedure.
Material related to the Bayesian
network class taught by Darwiche and
Judea Pearl, new book on
causality, chapter 1.
Overview of the transition from probabilistic to causal Bayesian nets.
This is a nice introduction/overview of work in Bayesian networks, with links to some standard references and tutorials on both inference and learning.
This page includes recent and survey papers related to POMDPs and decision theoretic planning.
UAI-oriented graduate class web pages with tutorials, class notes, links to free software, etc. Common core includes basic semantics of Bayes Nets and inference. Many expand on advanced inference and learning.:
UC Irvine: http://www.ics.uci.edu/~dechter/275B.html.
Peter Stone and Manuela Veloso, Multiagent Systems: A survey from a machine learning perspective, Autonomous Robots, 2000, to appear.
Symbolic model checking:
McMillan --- Symbolic Model Checking. Kluwer Publishers.
The key book in the area --- he started it all.
Edmund Clark group at CMU.
Satisfiability and compilation in verification:
Daniel Jackson, MIT. Nitpick system.
recent work by Vardi and colleagues on model checking.
Courcoubetis, Halbwachs et al --- The algorithmic analysis of hybrid systems.
Theoretical Comp. Sci. Vol 138, 1995.
This is the basic paper which lays out the definition of hybrid automata, proves the undecidability of verification, and has some simple examples.
Kopke, Puri and Varaiya --- What is decidable about Hybrid Automata? Journal of
Computer and System Sciences, 57(1):94-124, August 1998.
Summarizes the state of the art in the area.
Ho and Wong-Toi --- HyTech. http://www-cad.eecs.berkeley.edu/~tah/HyTech/
Hytech is he best known engine for Hybrid verification --- you can easily teach the algo in 15 minutes in a lecture.
Dill -- A Theory of Timed Automata. Theoretical Comp. Sci. 1994.
The key paper on Timed automata. Beautifully written too!
Nerode and Kohn, work on topological structures for hybrid systems.
Ansaklis et al.'s work on Petri net model for hybrid systems.
timed finite state automata, optimization methods.
work (at McGill) on partition systems
(similar to the phase space partition work of Feng Zhao).
Fast Deduction and Search
Fast propositional satisfiability algorithms:
Jr., R.J. and Schrag, R.C. (1997). Using CSP look-back techniques to solve real
world SAT instances. Proc. AAAI-97,
Selman, B., Kautz, H., and Cohen, B. (1994). Noise strategies for local
search. Proc. AAAI-94,
Nayak and Williams, incremental truth maintenance, AAAI, 1998?.
Randomized systematic search (heavy tails):
(Journal of Automated Reasoning, to appear)
C.P., Selman, B., and Kautz, H. (1998). Boosting combinatorial search through
randomization. Proc. AAAI-98,
Knowledge Compilation and Theory Approximation:
Compiling propositional theories: ps file sent from Darwiche. See Professor Williams for a copy of the paper.
Selman and Kautz:
Schaerf, Cadoli, & Liberatore[ Paolo Liberatore [email@example.com] and Marco Cadoli [firstname.lastname@example.org]]
Liberatore KR-1998, On the compilability of diagnosis, planning, reasoning about actions, belief revisions, etc.
Many others by Liberatore, with similar worst-case negative results.
Cadoli,Survey on knowledge compilation, ACM.
The standard reference, although a bit has happened since then. The specific reference appears in the Darwiche paper on compiling to DNNF.
Compiling Bayesian networks