CS287 Advanced Robotics

Course Outline

Some background in computational geometry and control theory is essential and rather than assume this, the first few weeks will cover the material we need. Topics include data structures, sweepline algorithms, voronoi diagrams, convex hulls and linear programming, duality, epsilon-nets, dynamics and model-based control. The core topics that follow are (i) telerobotics and telesurgery, (ii) agents and model-based vs. behavior-based architectures (iii) RISC and minimalist designs for sensors and manipulators (iv) micro-robotics, silicon motors, grippers, motion arrays and sensors (v) nano-technology, SPMs, molecular pistons, Fullerenes, "lego" proteins.


Computational Geometry

  • Review of Data structures. Balanced trees and persistent BBTs. Algebraic representation of polygons.

  • An O((n+k)log n) line-sweep algorithm for intersection/union and for generating a data structure for point-in-polygon queries.

  • Convex Hulls and an O(n log n) algorithm in the plane. Relationship with linear programming. An O(n)-time randomized algorithm for linear programming in fixed dimension. Collision-testing using linear programming.

  • Duality definitions and examples. Voronoi diagrams and Delaunay triangulations and their relationship to convex hull. Motion planning using Voronoi diagrams. Delaunay triangulations for surface and volume representation.

  • A constant-time (typically) algorithm for incremental collision detection and distance measuring. Measuring penetration using duality.

  • Random sampling and epsilon-nets. Applications to grasping and curve approximation. Clarkson's evolutionary algorithm.

  • Control and Dynamics

  • PD and PID controllers. Poles and stability.

  • Rigid body dynamics. Newton-Euler equations of motion.

  • Efficient O(n) dynamics for tree and almost-tree topology robots.

  • Model-based control. Computed-torque controllers. Force controllers.

  • Reinforcement-learning algorithms. Beam balancing example.

  • Resources on the Web

  • Computational Geometry
  • CG201 an introductory course from Curtin University.
  • Resource List from UCB.
  • General Robotics Links

  • Telerobotics
  • JPL/NASA Telerobotics Projects
  • Back to the CS287 home page.