1 of 49

CISC829: Advanced Topics in Algorithms and Complexity Theory

Prof. Christopher Rasmussen

2 of 49

Course Description

Introduction to research in computational complexity theory. Computational models: nondeterministic, alternating, and probabilistic machines. Boolean circuits. Complexity classes associated with these models: NP, Polynomial hierarchy, BPP, P/poly, etc. Complete problems. Interactive proof systems and probabilistically checkable proofs: IP=PSPACE and NP=PCP (log n, l). Definitions of randomness. Pseudorandomness and derandomizations. Lower bounds for concrete models such as algebraic decision trees, bounded-depth circuits, and monotone circuits.

3 of 49

CISC829:

Mobile Robot Programming

Prof. Christopher Rasmussen

4 of 49

Course Description

A hands-on approach to implementing mobile robot algorithms in simulation and on a group of small wheeled robots. Includes low- level motor control and reactive obstacle avoidance; high-level control including navigation, localization, and planning; vision-based sensing for tracking and mapping; and issues surrounding multi-robot cooperation.

5 of 49

Mobile Robot Platforms: Examples

  • Ground vehicles (UGVs)
    • Wheeled
    • Walking/running/hopping
    • Climbing
    • Snake-like/amoeboid
  • Underwater/surface vehicles (AUVs)
    • Thruster-driven
    • Fins
  • Flying vehicles (UAVs)
    • Fixed-wing airplanes
    • Helicopter variants
    • Ornithopters, blimps

​

​

  • Stanford percher (2:49)
  • ETH quadrotor (1:27)

​

6 of 49

Non-locomotion actuators

  • Sensor "aiming" with pan-tilt unit (vs. omnidirectional)
    • Camera
    • Microphone
    • Ladar
  • Manipulation
    • Arm for collecting samples
    • Gripper/digger/grinder/drill 
    • Vacuum (air/ underwater)

7 of 49

Robotic Sensors

  • Camera(s)
    • Color: Free space/ obstacle discrimination
    • Infrared
    • Stereo: Depth map recovery
  • Ladar range-finder
  • Sonar, radar, etc.
  • GPS and other differential localization techniques

Mars rover anaglyph

Velodyne 

ladar

CMU NIR + visible light vegetation inference (NDVI)

8 of 49

Structured light stereo (indoor/night only)

​

Kinect

Asus Xtion Pro Live

FOV

57° X 43°

58° X 45°

Range

1.2-3.5 m

0.8-3.5 m

Resolution

640 x 480 (0.09° / pixel)

640 x 480 (0.09° / pixel)

Update rate

30 Hz, 9.2 M points / s

30 Hz @ 640 x 480

60 Hz @ 320 x 240

Dimensions

Stripped (no case, no base)

183 mm W

32 mm H

52 mm D

180 mm W

24 mm H (no base)

36 mm D

Weight

148 g (stripped)

77 g (no case)

~140 g (with case)

Power

12 V @ 1 A

5 V USB

9 of 49

Kinect: Sample RGB and depth images

10 of 49

Stereo Vision

​

Pt. Grey Bumblebee2

FOV

43° x 32°, 65° x 49°, or 100° x 75°

Range

0.5-30 m

Resolution

640 x 480

Update rate

48 Hz @ 640 x 480 (14.7 M points / s)

20 Hz @ 1024 x 768 (15.7 M points / s)

Dimensions

157 mm W x 36 mm H x 47.4 mm D

Weight

342 g

Power

12 V, ~0.2 A

11 of 49

“TerraMax”

  • 11 cameras
    • Long-range trinocular system
    • 2 x short-range stereo system
    • 4 x monocular system (intersections, lane-changing)
  • 3 x Ibeo Alasca XT ladar
  • ~6 x Core2Duo computer (same computer switches between forward and reverse stereo)

12 of 49

VIAC, 2010 (Broggi et al.)

  • Parma to Shanghai: 8244 km in autonomous mode
  • 7 cameras
    • 3 forward panoramic
    • 2 forward stereo
    • 2 rear stereo
  • 4 ladars
    • Forward pushbroom
    • Front left, right for pedestrians
    • 4-beam parallel to ground for forward obstacles

13 of 49

Velodyne HDL-64E ladar

    • FOV: 360° H, 26.8° V
    • Range: 0.9-120 m
    • Resolution: 4167 x 64 (0.09° H, 0.33°-0.5° V) -> 267K points
    • Update rate: 5-20 Hz (always 1.33 M points / s)
    • Dimensions: 257 mm H x 224 mm W x 231 mm D
    • Weight: 13.2 Kg
    • Power: 12 V @ 4 A

​

14 of 49

Velodyne HDL-32E ladar

    • FOV: 360° H, 41.3° V
    • Range: 1-70 m
    • Resolution: 2250 x 32 (72K points)
    • Update rate: 10 Hz, 720K points / s
    • Dimensions: 150 mm H, 85 mm diameter cylinder
    • Weight: 1.3 Kg
    • Power: 12 V @ 2 A

​

15 of 49

Velodyne driving data (U. Koblenz-Landau)

16 of 49

Google Car (from IROS 2011 keynote)

(6:40-9:40)

17 of 49

CMU “Boss” (1st place in Urban Challenge)

  • Applanix POS-LV 220 IMU
  • Ladars (11)
    • Velodyne HDL-64
    • 6 x SICK LMS 291
      • Reflectivity used to distinguish lane markings
    • 2 x Continental ISF 172
    • 2 x Ibeo Alasca XT
  • 5 x Continental ARS radar
  • 2 x Pt. Grey Firefly camera
  • 10 x 2.16-GHz Core2Duo processors

18 of 49

Stanford “Junior” (2nd place)

  • Applanix POS-LV 420 INS
  • Ladars (8)
    • Velodyne, Riegl
    • 4 x SICK
    • 2 x IBEO
  • 5 x Bosch long-range radar
  • Two quad-core servers
    1. Perception
    2. Motion planning
  • Power from vehicle engine via battery-backed “high- current prototype alternator”

​

19 of 49

MIT “Talos” (4th place)

  • Applanix POS-LV 220 GPS/INS
  • Velodyne
  • 12 x SICK LMS 291
    • 5 pushbroom from roof
    • 7 low, parallel to ground
  • 15 x Delphi radar = 240° FOV
  • 5 x Pt. Grey Firefly cameras = 360° FOV
  • 10-blade server
  • External 6,000 W generator needed to power all this

20 of 49

Hokuyo UTM-30LX ladar

  • FOV: 270° H
  • Range: 0.1-30 m
  • Resolution: 0.25° / point (1080 points / scan)
  • Update rate: 40 Hz, 43K points / s
  • Dimensions: 87 mm H, 60 mm W x 60 mm D
  • Weight: ~210 g (370 g with cable)
  • Power: 12 V @ 1 A

21 of 49

3-D Point Clouds via Nodding/Spinning

  • Tilt servo for household object manipulation (Jain & Kemp, ICRA 2010), uneven floor navigation for humanoid (Chestnutt et al., IROS 2009)

​

22 of 49

Chestnutt et al., IROS 2009

23 of 49

3-D Point Clouds via Nodding/Spinning

  • Zebedee (Bosse et al., TRO 2012) Spring- mounted Hokuyo + IMU (e.g. Microstrain 3DM-GX3-25 OEM weighing 11.5 g)

24 of 49

Zebedee demo

25 of 49

3-D Point Clouds via Nodding/Spinning

  • Off-axis spinning with slip ring (Singh et al., IROS 2011)

26 of 49

UD Warthog

  • Robot platform
    • Segway RMP 400
  • Primary sensors
    • Stereo omnidirectional color cameras
    • Tiltable SICK LMS ladar
    • Bumpers linked to e-stop
    • GPS
    • Kinects
  • Computing
    • Two laptops running multiple processes communicating via IPC

27 of 49

Warthog Sensing: Omni Camera, Tilt Ladar

28 of 49

Warthog in action

29 of 49

Warthog timelapse

30 of 49

UD Create Robot

  • iRobot Create base
  • Hokuyo URG-04LX ladar for obstacle avoidance, mapping
  • ASUS Xtion Live Pro on tilt servo for
    • Place recognition
    • Object detection/ classification
    • Visual odometry

31 of 49

MIT Urban Challenge modules

32 of 49

Key Algorithmic Issues

  • Control
    • How do we command the robot to move the way we want subject to gravity, inertia, friction, wind, etc.?
  • Motion planning
    • What trajectory should the robot follow to reach a goal given kinematic, dynamic, and environmental constraints?
  • Estimation and tracking
    • Where is X (where X could be the robot itself or an external object, either rigid or articulated)? What is its orientation/velocity/etc.?

​

33 of 49

Control: Balancing (Tokyo Gakuin U.)

34 of 49

Control: U. Pennsylania quadrotor

35 of 49

Motion Planning: V-REP Simulator

36 of 49

Motion Planning: Little Dog at USC

37 of 49

Tracking: Willow Garage project

38 of 49

Key Algorithmic Issues

  • Perception
    • How do we detect obstacles/objects of interest in cluttered scenes, recognize places, and so on?
  • Localization
    • Where is the robot in a pre-existing map?
  • Mapping
    • How do we build a model of the area the robot is moving through?

​

39 of 49

MIT quadrotor doing obstacle avoidance

with onboard ladar sensing (3:00)

40 of 49

Object detection (Burrus' RGBDemo)

41 of 49

Feature-based Place Recognition (Oxford)

42 of 49

KinectFusion (SIGGRAPH 2011)

43 of 49

Intel/UW SLAM from stereo (1:33)

44 of 49

Key Algorithmic Issues

  • Manipulation
    • How can the robot affect the environment through pushing, digging, grasping, etc.?
  • Multi-robot coordination and cooperation
    • How can we have robots avoid each other, get into formations, and share information?

45 of 49

Grasping: PR2 at TU Munich

46 of 49

Multi-robot collision avoidance: Willow Garage

47 of 49

Coordination: U. Pennsylvania nano-quadrotors

48 of 49

Cooperative Pushing: U. Pennsylvania

49 of 49

Administrative Details

  • Course page:
    • http://nameless.cis.udel.edu/class_wiki/index.php/CISC829_F2012
    • Or: http://goo.gl/F0K83
  • Grading
    • 3 programming assignments: 16% each
    • Presentation: 20%
    • Project: 32%
  • We will be using Piazza for discussion, questions, and help

​