Additional Topics and General Readings
The following are papers in intelligent embedded systems recommended by many of the key researchers in the field. You may want to draw from this reading list during the development of your course project. Suggestions are provided thanks to:
Craig Boutilier, Adnan Darwiche, Vineet Gupta, Leslie Kaebling, Henry Kautz, Judea Pearl, Bart Selman, Dave Smith,Manuela Veloso, Dan Weld and Feng Zhao.
See the page
final project page for details on the project and relevant deadlines. Note that many of these references are only partial, but they should offer some clues as to where to look. Also take ample advantage of the LCS reading room on the first floor of NE43, and take ample advantage of the web's search capabilities. Most authors these days post their papers.
Intelligent Embedded Systems:
Robotic Soccer
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.
at Cornell. http://www.mae.cornell.edu/robocup/Introduction.html
Autonomous Space Probes:
Remote Agent Autonomous Control Experiment
http://rax.arc.nasa.gov
Reactive Programming:
Esterel and Lustre are the primary languages, and are doing very well for embedded systems programming.
Esterel language page, http://www-sop.inria.fr/meije/esterel/esterel-eng.html.
This page distributes the entire Esterel system, and has papers and pointers to the other languages.
Constraint Programming:
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.
Reinforcement Learning:
Surveys:
Leslie Pack Kaelbling and Michael L. Littman and Andrew W. Moore, Reinforcement Learning: A Survey, Journal of Artificial Intelligence Research, 1996, v. 4, 237-285.
Very nice short survey of reinforcement learning.
Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, MIT Press, Cambridge, MA, 1998.
A very nice treatment of reinforcement learning from an introductory level: very well presented and an easy read.
Dimitri P. Bertsekas and John. N. Tsitsiklis, Neuro-dynamic Programming, Athena, Belmont, MA, 1996.
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).
Some classics:
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:
Surveys:
Blythe, AI Magazine 20(2).
Short survey
Craig 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
Michael Kearns and Yishay Mansour and Andrew Y. Ng, A Sparse Sampling Algorithm for Near-optimal Planning in Large Markov Decision Processes, IJCAI, 1999. Stockholm, 1324--1331.
Partially Observable Markov Decision Processes:
Surveys:
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:
Anthony 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.
Model-based Autonomous Systems:
Diagnosis, repair and control.
W. Hamscher, L. Console and J. de Kleer (Ed.), Readings in Model-based Diagnosis, Morgan Kaufman, San Mateo, CA, 1992.
Proceedings of the International Workshop on Principles of Diagnosis.
Qualitative modeling and simulation.
D. Weld and J. de Kleer (Ed.), Readings in Qualitative Physics, Morgan Kaufman, San Mateo, CA, 1990.
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:
Surveys
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
Kautz and Selman, on Satplan planner.
http://www.research.att.com/~kautz/papers-ftp/plan.ps
Kautz and Selman, on Black box constraint solver.
http://www.research.att.com/~kautz/papers-ftp/ijcai99blackbox.ps
Graphplan
Blum, A. and Furst, M.L. (1995). Fast planning through planning graph analysis. Proc. IJCAI-95, Montreal, Canada.
Conditional planning
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: Williams, B.C. and P.P. Nayak, "A Reactive Planner for a Model-based Executive," Proceedings of the International Joint Conference on Artificial Intelligence, Nagoya, Japan, 1997
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:
Survey:
Smith, Frank and Jonsson, "Bridging the gap between planning and scheduling." Survey paper. See Professor Williams for a copy of the paper.
Temporal Planning:
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.
Scheduling:
Beck & Fox, AI Magazine 19(4).
Metric Quantities:
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 Pearl can be found at UCLA: http://www.cs.ucla.edu/~darwiche/cs262a/
Judea Pearl, new book on causality, chapter 1.
http://bayes.cs.ucla.edu/jp_home.html
Overview of the transition from probabilistic to causal Bayesian nets.
http://www.cs.berkeley.edu/~murphyk/Bayes/bayes.html
This is a nice introduction/overview of work in Bayesian networks, with links to some standard references and tutorials on both inference and learning.
http://www.cs.berkeley.edu/~murphyk/pomdp.html
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.:
Stanford: http://www.stanford.edu/class/cs228/
Harvard: http://deas.harvard.edu/courses/cs281r/
Duke: http://www.stat.duke.edu/courses/Spring99/sta294/
UC Irvine: http://www.ics.uci.edu/~dechter/275B.html.
Multi-agent Systems:
Surveys:
Peter Stone and Manuela Veloso, Multiagent Systems: A survey from a machine learning perspective, Autonomous Robots, 2000, to appear.
Automated Verification:
Symbolic model checking:
Ken 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.
Hybrid Systems:
Alur, 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.
Henzinger, 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.
Henzinger, 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.
Alur and 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.
Berkeley's work (Shankar Sastry, Claire Tomlin et al.):
timed finite state automata, optimization methods.
Caine's work (at McGill) on partition systems
(similar to the phase space partition work of Feng Zhao).
Fast Deduction and Search
Fast propositional satisfiability algorithms:
Bayardo Jr., R.J. and Schrag, R.C. (1997). Using CSP look-back techniques to solve real world SAT instances. Proc. AAAI-97, Portland, OR.
Li, Chu Min and Anbulagan (1997). Heuristics based on unit propagation for satisfiability problems. Proc. IJCAI-97, Nagoya, Japan.
Selman, B., Kautz, H., and Cohen, B. (1994). Noise strategies for local search. Proc. AAAI-94, Seattle, WA.
Nayak and Williams, incremental truth maintenance, AAAI, 1998?.
Randomized systematic search (heavy tails):
http://www.research.att.com/~kautz/papers-ftp/heavytails.ps
(Journal of Automated Reasoning, to appear)
Gomes, C.P., Selman, B., and Kautz, H. (1998). Boosting combinatorial search through randomization. Proc. AAAI-98, Madison, WI.
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:
http://www.acm.org/pubs/articles/journals/jacm/1996-43-2/p193-selman/p193-selman.pdf
Schaerf, Cadoli, & Liberatore[ Paolo Liberatore [liberatore@dis.uniroma1.it] and Marco Cadoli [cadoli@dis.uniroma1.it]]
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
Home | Announcements | Readings | Final Project