CMPT894 Directed Study: Autonomous Robots
Richard Vaughan [vaughan@sfu.ca]
Revisions
- 2013.01.06 rtv - initial version
Program
The class consists of a 90-minute weekly reading group based on the reading list
below, and a practical robotics research project. In each session the student will:
- summarize the papers you read
- discuss the ideas of the week in context
- discuss progress of the project
Reading
Each week, read the first two (sometimes three) papers listed. Then read and
watch the extra material if you wish. Naturally, the books contain
much more depth than the papers, but may take more time to read than
you have available.
The more you read and think about this topic, the more successful
the class will be. Further reading, thinking, movie watching and
debate is recommended. Evidence of wider reading and tbought will be
rewarded in the final grade.
Links are given to local copies where
available. The raw directory of
papers is here.
Project
Design and implement an autonomous mobile robot system in a Stage
simulation but suitable for porting to a real robot. The robot must perform the task
described below indefinitely, recharging itself as necessary.
Task
- Place a charging station in the centre of a large world
- Make a metric occupancy grid map of the environment - assume perfect localization and sensing. Make as complete a map of the area around the charging station as possible.
- Do not get stuck
- Return to recharge, then continue mapping.
You should aim to make the map as quickly as possible.
Complete a final demonstration and 3-page report explaining the goals, key design decisions and technology you used, and an evaluation of your system.
Getting started
- Install Stage and familiarize
yourself with the example controllers in (stage source
dir)/examples/ctrl. The fasr example includes basic navigation and recharging.
- Write a new world file and a robot controller
that explores the environment, recharging as necessary.
Grading
Final grade is based on a project including coding
and an extended-abstract style project report.
Reading list
Week 1: Introduction
- Alan M. Turing (1950). Computing machinery and
intelligence. Mind, 59, 433-460. HTML
version
- Isaac Asimov, "I, Robot", Doubleday, 1950. Chapters 1-3 (at
least). [PDF] Wikipedia
entry eBook ISBN 1401400396
- Richard T.Vaughan. Massively multi-robot simulations in
stage. Swarm Intelligence, 2(2-4):189-208, 2008. [PDF]
Extras
- R. Scott (1982) Blade Runner (movie), Warner Bros.
- R. Vaughan, B. Gerkey & A. Howard (2003) On device abstractions
for portable, resuable robot code. Proceedings of the 2003 IEEE/RSJ
International Conference on Intelligent Robots and Systems. pp2121-2427. [PDF]
Week 2: AI, Robots and the Frame Problem
- N. Nilsson (1984) Shakey the Robot, Technical Note 325, SRI
International, Menlo Park, CA, 1984. [PDF]. (You don't need to read this long paper thoroughly, but scan it to get an idea of the major contribution it was).
- D.C. Dennett (1987) Cognitive Wheels: The Frame Problem of AI, in Z.W. Pylyshyn (ed.) (1987), The Robot's Dilemma: The Frame Problem in Artificial Intelligence, Norwood, NJ: Ablex. HTML
- Stanford Encyclopedia of Philosophy entry on the Frame Problem.
Extras
- A. Newell & H.A. Simon (1975) Computer Science as Empirical Inquiry:
Symbols and Search. 1975 ACM Turing Award Lecture. HTML
- S. Kubrick (1968) 2001 (movie), MGM.
Week 3: Autonomy and Energy
- R. Pfeifer (1996) Building "Fungus Eaters": Design principles of autonomous agents. Proc. Int. Conf. on Simulation and Adaptive Behavior, 1996
[PDF]
- J. Wawerla and R. T. Vaughan. (2008) Optimal robot recharging for time discounted labour. In Proceedings of the Eleventh International Conference on Artificial Life (ALife XI), August 2008. [PDF]
Extras
- D. McFarland & T. Bosser (1993) Intelligent Behavior in Animals and Robots. MIT Press
- M. Toda (1962). Design of a Fungus-Eater. Behavioral Science, 7, 164-183. (Reprinted in M. Toda (1982) Man, robot and society. The Hague: Martinus Nijhoff Publishing, pp100-129. (no digital copy available)
- A. Stanton (2008) Wall-E, Pixar Animation Studios (movie)
Week 4: Behavior-based robots
- P. Agre and D. Chapman (1990) What are plans for?, Robotics and Autonomous Systems, pp17--34, MIT Press. Also MIT AI Memo 1050A.
[PDF]
- R.A. Brooks (1985) A Robust Layered Control System for a Mobile Robot, IEEE Journal of Robotics and Automation, Vol. 2, No. 1, March 1986, pp. 14-23; also MIT AI Memo 864, September 1985. [PDF]
- R.A. Brooks (1990) Elephants Don't Play Chess, Robotics and Autonomous Systems (6), 1990, pp. 3-15. [PDF]
Extras
- H.A. Simon (1996) The Sciences of the Artificial (third edition), MIT Press.
- R.A. Arkin (1998) Behavior-Based Robotics. MIT Press.
- E. Morris (1997) Fast, Cheap and Out of Control (movie), Sony Pictures Classics.
Week 5: Navigation
- J. Minguez and L. Montano, "Nearness Diagram Navigation (ND):
Collision Avoidance in Troublesome Scenarios", IEEE Transactions on
Robotics and Automation 20(1), February, 2004.
[PDF]
- A. Stentz, "Optimal and Efficient Path Planning for Partially-Known Environments", Proceedings of the IEEE International Conference on Robotics and Automation, May, 1994
[PDF]
Extras
- J. Borenstein and Y. Koren (1991) "The Vector Field Histogram -- Fast Obstacle-Avoidance for Mobile Robots." IEEE Journal of Robotics and Automation, Vol. 7, No. 3., June 1991, pp. 278-288
[PDF]
- Y. Koren, and J. Borenstein (1991) Potential Field Methods and Their Inherent Limitations
for Mobile Robot Navigation
, Proceedings of the IEEE Conference on Robotics and Automation, Sacramento, California, April 7-12, 1991, pp. 1398-1404
[PDF]
Week 6: Localization and Mapping
- S. Thrun, D. Fox, W. Burgard, and F. Dellaert. Robust monte carlo
localization for mobile robots. Articial Intelligence, 2001.
[PDF]
- Andrew Howard. "Multi-robot Simultaneous Localization and Mapping using Particle Filters". In International Journal of Robotics Research, 25(12):1243-1256, 2006
[PDF]
Extras
- J. J. Leonard and H. F. Durrant-Whyte. Mobile robot localization by tracking geometric beacons. IEEE Trans. Robotics and Automation, 7(3):376-382, June 1991.
- J. J. Leonard, I. J. Cox, and H. F. Durrant-Whyte. Dynamic map building for an autonomous mobile robot. Int. J. Robotics Research, 11(4):286--298, August 1992.
Week 7: Multiple Robot Systems
B. Gerkey and M. Mataric´.(2004) A formal analysis and taxonomy of task allocation in multi-robot systems.
Intl. Journal of Robotics Research, 23(9):939-954, September 2004.
[PDF]
- R. Vaughan, K. Stoy, G. Sukhatme & M. Mataric (2000) Go ahead,
make my day: robot conflict resolution by aggressive
competition. Proc. Int. Conf. Simulation of Adaptive Behaviour, Paris,France. [PDF]
- David Payton, Mike Daily, Regina Estowski, Mike Howard, Craig Lee (2001) Pheromone Robotics.
Autonomous Robots 11(3):319-324, November 2001. PDF
Extras
- Y.U. Cao, A.S. Fukunaga, A.B. Kahng (1997) Cooperative Mobile Robots: Antecedents and
Directions. Autonomous Robots (4) pp1-27. [Long, useful review paper] [PDF]
- M. Batalin and G. Sukhatme (2007) "The Design and Analysis of an
Efficient Local Algorithm for Coverage and Exploration Based on Sensor
Network Deployment", IEEE Transactions on Robotics, 23:4, pp.661-675, August 2007. [PDF]
- M. Fontan & M. Mataric (1998) Territorial multi-robot task
division. IEEE Transactions on Robotics and Automation, 15(5). PS.GZ
- David Payton, Regina Estowski, Mike Howard (2001) Compound Behaviors in Pheromone Robotics,
Robotics and Autonomous Systems, 44 (3-4): 229-240, Sept. 2003 PDF
Week 8: Minimalist and Nano-Robots
- O.E. Holland, C. Melhuish (1999) Stigmergy, self-organisation, and sorting in collective robotics. Artificial Life, 5:2, 173-202 1999
[PDF]
- R. Feynman (1959) There's Plenty of Room at the Bottom. Talk to the American Physical Society at CalTech, published (1960) Engineering and Science. [HTML]
Extras
- R. Vaughan, N. Sumpter, J. Henderson, A. Frost & S. Cameron. Experiments in Automatic Flock Control (2000) Robotics and Autonomous Systems 31 pp.109-117 [PDF]
- N. Stephenson (1995) The Diamond Age. Bantam Spectra
Week 9: Internal Dynamics, Emotion & Consciousness
- C. Breazeal & B. Scassellati (1999) How to build robots that make friends and influence people, Proceedings of the 1999 International Conference on Intelligent Robot Systems. [PDF]
- C. Breazeal (2003) Emotion and sociable humanoid robots. Int. Jnl. Human-Computer Interaction, 59. pp199-155. [PDF]
Extras
- D. McFarland (1995) Opportunity versus Goals in Robots, Animals and People.In Roitblat & Meyer (Eds.) Comparative Approaches to Cognitive Science. 415--433. MIT Press. (Available as an eBook in the SFU library)
- A. Clark (1997) Being There: Putting Brain, Body, and World Together Again. MIT Press.
- D. Dennett (1992) Consciousness Explained. Back Bay Books.
Week 10: Biomimetics
- B. Webb. (1995) Using robots to model animals: a cricket test . Robotics and Autonomous Systems, 16, 117-134.
- B. Webb (2000) What does robotics offer animal behaviour? Animal Behavior 60 pp545-558. [PDF]
Extras
-
J.Y. Lettvin, H.R. Maturana, W.S. McCulloch, and W.H. Pitts, (1959) What the Frog's Eye Tells the Frog's Brain. Proceedings of the IRE (Institute of Radio Engineers, now the IEEE), 47 : pp1940-1959
- Webb, B. (2002) Robots in invertebrate neuroscience Nature 417:359-363 [PDF]
Week 11: Evolutionary Robotics
- S. Wilson (1985) Knowledge Growth in an Artificial Animal. Proceedings of the First International Conference on Genetic Algorithms and their Applications, Carnegie Melon University, Pittsburgh, 1985, pp.1-8. [PDF]
- P. Husbands, I. Harvey, D. Cliff and G. Miller (1997) Artificial Evolution: A New Path for Artificial Intelligence? Brain and Cognition, 34:130-159. [PDF]
Extras
- N. Jakobi (1997) Evolutionary Robotics and the Radical Envelope
of Noise Hypothesis. Adaptive Behavior, 6(2):325-368. [PDF]
- R. Dawkins (1989) The Selfish Gene. Oxford Paperbacks.
- J. Maynard-Smith (1982) Evolution and the Theory of Games. Cambridge University Press.