Department of Computer Science
College of Arts and Sciences
The University of North Carolina at Chapel Hill

COMP 790-058
Robotics

Instructor: Dinesh Manocha

Time and Place: MW 11:00am-12:15pm, SN 011

Office Hours: M 2:00-3:15pm or by appointment, FB 250

Prerequisites: Knowledge of calculus, differential equations, linear algebra, and programming is assumed and instructor's approval

Textbook: Course Notes and In-Class Handouts

Lab TA: Jamie Snape

• Course Overview
• Lectures and Approximate Schedule
• Assignments and Projects
• Student Course Projects
• Geometric Algorithms & Software Available on the Web
• Additional Reference Materials
• Conferences in Related Areas

COURSE OVERVIEW:

Robotics is the study of robot design, programming, and control. Typically a robot is refered to as an agent that can be programmed to perform a variety of tasks -- both with and without human intervention. A robot is often manifested and realized by mechanical and electrical components to carry out its actions in the physical world. Robots frequently receive input from noisy sensors, consider geometric and mechanical constraints, and operate in the physical world through imprecise actuators. The design and analysis of robot algorithms and computational elements, therefore, raises a unique combination of questions in computational and differential geometry, algorithm design, control theory, mechanics, computer science, and system engineering.

In this course, we will give an overview on fundamental components of robotic systems, including the sensing and actuation, control and modeling of motion and perception, dynamics and kinematics, motion planning and manipulation of robots. Students will learn about implementation of basic simulation programs that produce interesting results and verify its correctness. The goal of this class is to get students an appreciation of computational methods and engineering issues for modeling robots. We will discuss various considerations and tradeoffs used in designing various methodologies (e.g. time, space, robustness, and generality). This will include data structures, algorithms, computational methods, simulation techniques, runtime complexity, system implementation and integration, in the context of multi-disciplinary design. The lectures will also cover some applications of robotics to the following areas:

• Computer Animation
• Virtual Environments
• Haptic Rendering & Interfaces
• Medical Training & Robot Assisted Operations
• Design Automation and Rapid Manufacturing
• Bio-informatics and Computational Chemistry
• Sensor Networks & Distributed Robotic Systems

Furthermore, scientists have discovered that designs in the natural world can be successfully exploited to create engineered artifacts. Over the last several years, robotists have come up with several new robot designs that are based on biological entities. These new designs offer significant benefits over the traditional robot designs. Thus, a central part of the course will also cover the fundamentals and applications of biologically inspired robots. If time allows, we will also examine recent development on modular and reconfigurable robots, as well as simultaneous localization and mapping (SLAM).

In order to experiment with some of these concepts, we are going to use iRobot's Create kit (based on the Roomba). We plan to give out assignments dealing with planning the path of a single Roomba or multiple Roombas. For more information, see HERE.

LECTURES AND APPROXIMATE SCHEDULE

Here is a list of TENTATIVE lecture topics (subject to changes). Schedule and information on each topic (e.g. readings, web pointers) will be added during the semester before each class.

• Overview, iRobot Create (Wed, Aug. 20, 2008)
• Introduction to Sensing, Actuation & Kinematics (Mon, Aug. 25, 2008)
• Introduction to Roomba and Create (Jamie Snape, Wed, Aug. 27, 2008)
• Introduction to Computer Vision for Robotics (Jan-Michael Frahm, Wed, Sep. 03, 2008)
• Inverse Kinematics (Mon/Wed, Sep. 08 & 10, 2008) Background on kinematics ; Denavit-Hartenberg Convention ; Algebraic and Geometric Solutions ; Chris Hecker notes on numerical solvers for inverse kinematics;
• Rigid and Articulated Body Dynamics I, II (Tim Johnson & Yu-Hsien Su, Mon/Wed, Sep. 15 & 17, 2008)
• Single Robot Motion Planning I, II (Liangjun Zhang, Mon/Wed, Sep. 22 & 24, 2008)
• Multi-Robot Motion Planning I, II (Jur van den Berg, Mon/Wed, Sep. 29 & Oct. 06, 2008)
• Real Robots - Sensors to Simulations (Edison Hudson, iRobot Corporation, Wed, Oct. 01, 2008, 12:30pm)
• Introduction to Simultaneous Localization and Mapping (David Wilkie, Wed, Oct. 08, 2008)
• Final Project Proposal Presentations (Mon, Oct. 13, 2008)
• Motion Planning with Uncertainty (Lakulish Antani, Wed, Oct. 15, 2008)
• Probabilistic Reasoning and Bayersian Programming I, II, III (Yue-Ling Wong, Mon/Wed, Oct. 20 & 22, 2008)
• Machine Learning and Robotics (Lisa Lyons, Mon, Oct. 27, 2008)
• Collision and Proximity Computations using Hierarchies (Mon, Nov. 03, 2008)
• Crowd Simulation I, II (Glenn Elliott & Sachin Patil, Mon/Wed, Nov. 10 & 13, 2008)
• Biologically-Inspired Algorithms in Robotics (Sang Woo Lee, Mon, Nov. 17, 2008)
• Active Research Projects in the Center for Robotics and Intelligent Machines (Eddie Grant, North Carolina State University, Wed, Nov. 19, 2008)
• Medical Robotics (Susu Li, Mon, Dec. 01, 2008)
• Localization (Micah Taylor, Wed, Dec. 03, 2008)
• Assignment 3 Demos (Fri, Dec. 05, 2008, 10:30am)
• Final Project Presentations (Mon, Dec. 15, 2008, 9:00am)

ASSIGNMENTS AND PROJECTS

The class grade of each student is determined by

• Assignments: Problems and programming assignments (35%)
• Class presentation (15%)
• Final project (50%)

Problems:

• Assignment 2 (Wed, Oct. 22, 2008)

Programming assignments:

• Assignment 1 (Wed, Sep. 10, 2008)
• Assignment 3 (Fri, Dec. 05, 2008)

For useful documentation, code examples, software tools, and web links, see here.

STUDENT COURSE PROJECTS

• Visibility-based pursuit evasion (Lakulish Antani)
• Space syntax (Glenn Elliott)
• Bio-inspired crowd evasion behavior (Sang Woo Lee)
• Realistic traffic reconstruction with stoplights (Susu Li and Lisa Lyons)
• Fast proximity queries with swept sphere volumes on GPUs (Qi Mo)
• Directable multi-agent navigation and simulation (Sachin Patil)
• Determining location with diffraction propagation (Micah Taylor)
• SimTraffic (David Wilkie, Tim Johnson, and Yu-Hsien Su)
• Modeling sheep dog herding on a robot (Yue-Ling Wong)

GEOMETRIC ALGORITHMS AND SOFTWARES AVAILABLE ON THE WEB:

• Internet Finite Element Resources
• A comprehensive collection of geometric software
• CGAL: Computational Geometry Algorithms Library (in C++)
• LEDA: Library of Efficient Datatypes and Algorithms (in C++)
• The Stony Brook Algorithm Repository: Implementation in C, C++, Pascal and Fortran
• CMU's Computer Vision Homepage
• Finite element mesh generation and More
• Machine learning resources

ADDITIONAL REFERENCE MATERIALS

Here is a list of suggested reading materials.

Some Reference Books in Robotics:

• Planning Algorithms, by Steven LaValle. Cambridge University Press, 2006.
• Probablistic Robotics, by S. Thrun, W. Burgard, and D. Fox. MIT Press, 2005.
• Principles of Robot Motion: Theory, Algorithms, and Implementation, by H. Choset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki, and S. Thrun. MIT Press, 2005.
• Introduction to Robotics: Mechanics and Control, by J.J. Craig. Prentice Hall, 3rd edition, 2003,
• Robot Motion Planning, by Jean-Claude Latombe. Kluwer Academic Publishers, 1991.
• Robot Manipulators: Mathematics, Programming, and Control, by Richard Paul. MIT Press, 1981.
• Amphibionics: Build Your Own Biologically Inspired Reptilian Robot, by Karl Williams. McGraw-Hill/TAB Electronics, 2003.
• Robot Building for Beginners, by David Cook. APress, 2002.
• Biomimetic Sensor Technology, by Kiyoshi Toko. Cambridge University Press, 2000.

Other Reference Books in Mechanics:

• Concepts and Applications of Finite Element Analysis, by R. D. Cook, D. S. Malkus and M. E. Plesha, John Wiley & Sons, 1989.
• Finite Element Procedures, by K.-J. Bathe, Prentice Hall, 1996.
• First Course in Continuum Mechanics, by Y.C. Fung, Prentice Hall, 1993.

Other Reference Books in Numerical Methods:

• Numerical Recipes, by Press, Flanner, Teukolsky and Vetterling, Cambridge University Press.
• Handbook of Numerical Analysis, edited by Ciarlet and Lions, Vol. I - VI, North-Holland, 1994.

Other Reference Books in Geometry:

• Computational Geometry (Algorithms and Applications), by de Berg, van Kreveld, Overmars and Schwarzkofp, Springer-Verlag, 1997.
• Computational Geometry In C (Second Edition), by O'Rourke, Cambridge University Press, 1998.
• Handbook on Discrete and Computational Geometry, by Goodman and O'Rourke (eds), CRC Press LLC, 1997.
• Applied Computational Geometry: Toward Geometric Engineering, by Lin and Manocha (eds), Springer-Verlag, 1996.
• Algorithms in Combinatorial Geometry, by Edelsbrunner, Springer-Verlag, 1987.
• Computational Geometry (An Introduction), by Preparata and Shamos, Springer-Verlag, 1985.

Other Related Reference Books in Computer Animation:

• Making Them Move: Mechanics, Control and Animation of Articulated Figures, by Badler, Barsky and Zelter, Morgan Kaufmann Publishers, 1991.

Copyright 2006, 2008. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the author.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.