Activity:Dead Reckoning Navigation

From Bespoke Robot Society
Jump to navigation Jump to search
Dead Reckoning Navigation
Type Activity
Difficulty Beginner
Real-World Uses GPS-denied indoor navigation, precision positioning in manufacturing, submarine navigation, spacecraft navigation
Required Capabilities Capability:Optical Odometry or Capability:IMU Sensing, Capability:Differential Drive
Possible Behaviors Behavior:Dead Reckoning
Robots SimpleBot
Status Fully Documented


Dead reckoning navigation is a fundamental technique for determining a robot's current position by continuously tracking its motion from a known starting point. The term "dead reckoning" comes from nautical navigation, where it originally meant "deduced reckoning" - calculating your position based on your previous position, speed, and direction traveled.

Overview

Dead reckoning works by:

  1. Starting from a known position (often set as the origin: x=0, y=0, heading=0°)
  2. Measuring incremental movements (distance traveled, turns made)
  3. Computing the new position by adding those movements to the previous position
  4. Repeating this process continuously as the robot moves

This creates a running estimate of where the robot is relative to its starting point, without needing external references like GPS, cameras looking at the environment, or beacon systems.

Real-World Applications

Dead reckoning is essential in environments where external positioning systems are unavailable or unreliable:

  • Indoor Navigation: GPS signals don't penetrate buildings, so robots use dead reckoning combined with other sensors
  • Submarine Navigation: Underwater vessels cannot receive GPS signals and rely heavily on inertial navigation
  • Spacecraft Navigation: Between ground station updates, spacecraft use dead reckoning to maintain position estimates
  • Manufacturing: Automated guided vehicles (AGVs) use dead reckoning for precise positioning on factory floors
  • Mining Operations: Underground vehicles navigate without GPS using odometry and inertial sensors

Required Capabilities

Dead reckoning requires two fundamental capabilities:

Motion Measurement

The robot must measure how it moves. This can be achieved through:

Controlled Movement

The robot must execute controlled movements to follow planned paths:

How Dead Reckoning Works

The core concept is integration - continuously adding small changes to build up a complete picture of motion:

  1. Measure the change since the last update (e.g., "moved 5cm forward, turned 2° right")
  2. Calculate how this affects your position in global coordinates
  3. Update your position estimate: new_position = old_position + change
  4. Repeat at a high frequency (typically 10-100 times per second)

For example, if a robot:

  • Starts at position (0, 0) facing north (0°)
  • Drives forward 1 meter
  • Its new position is (0, 1) still facing north (0°)

If it then:

  • Turns 90° right (now facing east at 90°)
  • Drives forward 1 meter
  • Its new position is (1, 1) facing east (90°)

The robot continuously performs these calculations to maintain its position estimate.

Types of Dead Reckoning

Odometry-Based Dead Reckoning

Uses wheel encoder measurements to estimate position:

Advantages:

  • Simple and intuitive
  • Works well for short distances on smooth surfaces
  • Relatively inexpensive hardware

Disadvantages:

  • Sensitive to wheel slippage
  • Affected by uneven floors or carpets
  • Wheel diameter variations cause systematic errors

IMU-Based Dead Reckoning

Uses inertial measurement units (accelerometers and gyroscopes):

Advantages:

  • Not affected by wheel slip
  • Works on any terrain
  • Can detect external forces (being pushed)

Disadvantages:

  • Must integrate acceleration twice (position error grows very quickly)
  • Requires careful calibration
  • Sensitive to sensor bias and drift

Hybrid Approaches

Most practical systems combine both:

  • Use odometry for position tracking
  • Use gyroscope for accurate heading measurement
  • Compensate odometry with IMU data when slip is detected

Error Accumulation

The fundamental limitation of dead reckoning is drift - errors accumulate over time:

Sources of Error

  • Measurement errors: Sensors aren't perfectly accurate
  • Integration errors: Small measurement errors compound with each update
  • Systematic errors: Wheel diameter mismatch, sensor bias
  • Environmental factors: Floor friction, carpet texture, debris on wheels

Error Growth

  • Errors are cumulative - each error adds to all previous errors
  • Position error typically grows proportionally with distance traveled
  • Heading errors are particularly problematic because they cause position errors that grow with time
  • After driving in a square and returning to start, the robot will likely be offset from its true starting position

Practical Implications

  • Dead reckoning is excellent for short-term navigation (seconds to minutes)
  • Useful for relative positioning ("move 1 meter forward from here")
  • Must be corrected periodically using external reference points for long-term accuracy

SimpleBot Challenges

SimpleBot provides an excellent platform for learning dead reckoning concepts through hands-on challenges.

Challenge A: Out and Back

Objective: Navigate a configured path forward, then return to the starting point by executing the path in exact reverse.

Setup:

  1. Configure a multi-segment path (e.g., forward 1m, turn 45° left, forward 0.5m, turn 90° right, forward 0.75m)
  2. Robot executes the path while tracking each movement
  3. Robot must return home by reversing each step in the opposite order

Learning Goals:

  • Understanding position tracking
  • Implementing movement reversal logic
  • Observing error accumulation even on a carefully reversed path

Expected Outcome: Students will notice that even with careful reversal, the robot doesn't return exactly to the starting position. This demonstrates cumulative errors in dead reckoning.

Challenge B: Hypotenuse Return

Objective: Drive an L-shaped path (forward then turn and forward), then return to start via the straight-line hypotenuse.

Setup:

  1. Drive forward X meters (e.g., 1 meter)
  2. Turn 90° (e.g., right)
  3. Drive forward Y meters (e.g., 1 meter)
  4. Calculate the required heading to return to start
  5. Calculate the straight-line distance (hypotenuse)
  6. Execute the direct return path

Learning Goals:

  • Using position estimates for path planning
  • Calculating angles and distances from position data
  • Comparing actual vs. expected final position

Expected Outcome: This challenge requires students to:

  • Maintain a position estimate throughout the L-shaped path
  • Calculate return_distance = sqrt(X² + Y²)
  • Calculate return_angle = atan2(Y, X) + 180° (relative to current heading)
  • Execute the calculated return maneuver
  • Measure how far off they are from the true starting position

Bonus Challenge: Quantifying Error

After completing either challenge:

  • Place a marker at the robot's actual starting position
  • Measure the error between where the robot thinks it ended and where it actually ended
  • Repeat the challenge multiple times and plot error vs. distance traveled
  • Investigate which factors contribute most to error (turning vs. straight-line motion)

Limitations and When to Use Sensor Fusion

Dead reckoning alone has significant limitations:

When Dead Reckoning Is Sufficient

  • Short-duration tasks (under 1 minute)
  • Short-distance navigation (under 5 meters)
  • Relative positioning tasks ("move 30cm forward")
  • Smooth, predictable surfaces
  • When approximate positioning is acceptable

When Additional Sensors Are Needed

  • Long-duration autonomous operation
  • Precise positioning requirements
  • Environments with wheel slip (carpet, loose surfaces)
  • Tasks requiring return to exact locations
  • Mission-critical navigation

Sensor Fusion Approaches

To overcome dead reckoning limitations, combine it with:

  • Visual landmarks: Periodically detect known features to correct position
  • Capability:LIDAR Sensing: Match scans to known maps
  • Beacon systems: Triangulate position from known transmitters
  • GPS: When available outdoors
  • Motion capture systems: For laboratory environments

The combination is often called sensor fusion or probabilistic localization, where dead reckoning provides continuous estimates that are periodically corrected by absolute position measurements.

See Also

Retrieved from "https://wiki.bespokerobotsociety.org/index.php?title=Activity:Dead_Reckoning_Navigation&oldid=10"