1. Summary
  2. Files
  3. Support
  4. Report Spam
  5. Create account
  6. Log in

Roadmap:Navigation

From lejos

(Difference between revisions)
Jump to: navigation, search
Line 5: Line 5:
-
===First, some thoughts about the names of classes.
+
===First, some thoughts about the names of classes.===
• Pilot was probably not the best choice.  MovmentController might be better;  shorter versions include MovementControl, MoveController, Controller .  Any of these would be better than  PoseController because  pose is the dynamic state of a navigating robot and it changes as the result of a movement.  It cannot be controlled directly.   
• Pilot was probably not the best choice.  MovmentController might be better;  shorter versions include MovementControl, MoveController, Controller .  Any of these would be better than  PoseController because  pose is the dynamic state of a navigating robot and it changes as the result of a movement.  It cannot be controlled directly.   
While  there is a couple of years of code written by many users that would be broken  if we abandon Pilot,  if we ever going to do it, release 1.0 is the time.  But I am inclined to let it stand.
While  there is a couple of years of code written by many users that would be broken  if we abandon Pilot,  if we ever going to do it, release 1.0 is the time.  But I am inclined to let it stand.
Line 30: Line 30:
-
===Level 1 Basic classes and interfaces
+
===Level 1 Basic classes and interfaces===
BasicPilot interface  
BasicPilot interface  
*Skills: travel in a straight line : forward or backward)  ( I don’t think this is necessary  in a Navigation package since a robot *that cannot change direction cannot  it cannot navigate in a plane and is hardly worth building)   
*Skills: travel in a straight line : forward or backward)  ( I don’t think this is necessary  in a Navigation package since a robot *that cannot change direction cannot  it cannot navigate in a plane and is hardly worth building)   
Line 51: Line 51:
*Uses:  two TachoMotors  for differential steering;
*Uses:  two TachoMotors  for differential steering;
-
===Level 2A
+
===Level 2A update of pose ===
    
    
Pose
Pose
Line 61: Line 61:
*Note: To update this simple pose requires a navigator class  that uses a gets the distance and heading change from a Pilot and calls the update method on the Pose
*Note: To update this simple pose requires a navigator class  that uses a gets the distance and heading change from a Pilot and calls the update method on the Pose
   
   
-
+++Level 2automatic update of pose at the end of each elemental movement.
+
===Level 2B automatic update of pose at the end of each elemental movement.===
Movement  class
Movement  class
-
Skills:  
+
*Skills:  
-
none –a passive data carrier of distance traveled, heading change and movement type as supplied by MovementProvider , used by  a MoveListener
+
**none –a passive data carrier of distance traveled, heading change and movement type as supplied by MovementProvider , used by  a  
 +
MovementListener
MovementProvider  interface  
MovementProvider  interface  
-
Skills:   
+
*Skills:   
-
updates MovementListeners  at the end of every elemental movement and when requested by a MovementListener
+
**updates MovementListeners  at the end of every elemental movement and when requested by a MovementListener
-
Uses:  
+
*Uses:  
-
Movement , MovementListener
+
**Movement , MovementListener
-
Interface: MovementListener
+
MovementListener interface
-
Skills: updates itself from data contained in a  Movement which is supplied by a MovementProvider
+
*Skills:  
-
Uses: Movement , MovementProvider to supply a current Movement
+
**updates itself from data contained in a  Movement which is supplied by a MovementProvider
 +
*Uses:  
 +
**Movement , MovementProvider to supply a current Movement
UpdatingPilot  interface  extends Pilot  implements MovementProvider     
UpdatingPilot  interface  extends Pilot  implements MovementProvider     
-
Skills:   
+
*Skills:   
-
See MovementProvider and Pilot
+
**See MovementProvider and Pilot
-
Uses  
+
*Uses  
-
Movement, Motor
+
**Movement, Motor
UpdatingDifferntialPilot  class  implements Updataing Pilot extends DifferentialPilot
UpdatingDifferntialPilot  class  implements Updataing Pilot extends DifferentialPilot
-
Skills: see UpdataingPilot and DifferentialPilot
+
*Skills: see UpdatingPilot and DifferentialPilot
UpdateablePose  extends Pose implements MoveListener  
UpdateablePose  extends Pose implements MoveListener  
-
Skills:  
+
* Skills: See Pose and MoveListener
-
See Pose and MoveListener
+
*Uses: Movement
-
Uses:
+
-
Movement
+
SimpleNavigator  (stripped down version of current class  only has goTo(x,y)  
SimpleNavigator  (stripped down version of current class  only has goTo(x,y)  
-
Skills:  moves the robot to a desired Point.
+
*Skills:  moves the robot to a desired Point.
-
Uses:  UpdatingPilot, UpdateablePose  
+
*Uses:  UpdatingPilot, UpdateablePose  
RCNavigator extends SimpleNavigator
RCNavigator extends SimpleNavigator
-
Uses; communicator to get commands from a remote controller.
+
*Uses: communicator to get commands from a remote controller.
 +
===Probabilistic Navigation===
-
--------------- Probabilistic Navigation------------------
+
ProbabisticMovement class extends Movement  *( could be called QualifiedMovement if you really want to)
 +
*Skills: carries three variable Normal distribution representation of a movement;
-
ProbabisticMovement extends Movement  ***( could be called QualifiedMovement if you really want to)
+
ProbabilisticMovementProvider interface extends MovementProvider
-
Skills: carries three variable Normal distribution representation of a movement;
+
*Skills: updates  ProbabilisticMoveListeners
 +
*Uses: ProbabilisticMovement
-
Interface:  ProbabilisticMovementProvider extends MovementProvider
 
-
Skills: updates  ProbabilisticMoveListeners
 
-
Uses: ProbabilisticMovement
 
-
 
+
ProbabilisticPilot interface extends UpdatingPilot implements ProbabilisticMovementProvider   
-
ProbabilisticPilot extends UpdatingPilot implements ProbabilisticMovementProvider   
+
*Skills:   ProbabilisticMovementProvider, UpdatingPilot
-
Skills:
+
Uses: ProbabilisticMovement
-
see ProbabilisticMovementProvider
+
-
see UpdatingPilot
+
-
 
+
-
Uses:  
+
-
ProbabilisticMovement
+
ProbabilisticDifferentialPilot extends UpdatingDifferentialPilot implements ProbabilisticMovementProvider   
ProbabilisticDifferentialPilot extends UpdatingDifferentialPilot implements ProbabilisticMovementProvider   
-
Skills:   
+
Skills:  see ProbabilisticMovementProvider ,UpdatingDifferentialPilot
-
see ProbabilisticMovementProvider
+
Uses: ProbabilisticMovement
-
see UpdatingDifferentialPilot
+
-
 
+
-
Uses:  
+
-
ProbabilisticMovement
+
NormalPose extends UpdateablePose
NormalPose extends UpdateablePose
-
Skills:  uses a three variable normal distribution to represent  pose. Returns x,y and heading  with  mean and variance.  
+
*Skills:   
 +
**uses a three variable normal distribution to represent  pose.  
 +
** Returns x,y and heading  with  mean and variance.  
ParticleSetPose extends UpdateablePose
ParticleSetPose extends UpdateablePose
-
Skills:  uses a particle set to represent a pose.  Can return mean and variance of x,y and heading.
+
*Skills:  uses a particle set to represent a pose.  Can return mean and variance of x,y and heading.
KalmanPoseProvider (probably an abstract class  with sub classes for different sensor models)
KalmanPoseProvider (probably an abstract class  with sub classes for different sensor models)
Line 139: Line 133:
**Navigator (to aim the robot if sensors are fixed)
**Navigator (to aim the robot if sensors are fixed)
**Updating algorithm using Kalman filter  
**Updating algorithm using Kalman filter  
-
Map (to determine where to point sensors)
+
**Map (to determine where to point sensors)
 +
 
MonteCarloPoseProvider  (probably an abstract class  with sub classes for different sensor models)
MonteCarloPoseProvider  (probably an abstract class  with sub classes for different sensor models)
-
Skills: updates a ParticleSetPose  
+
*Skills: updates a ParticleSetPose  
-
Uses:   
+
*Uses:   
-
ParticleSetPose
+
**ParticleSetPose
-
various sensors and motors to direct the sensors;  
+
**various sensors and motors to direct the sensors;  
-
Navigator (to aim the robot if sensors are fixed)
+
**Navigator (to aim the robot if sensors are fixed)
-
Uses Monte Carlo update.  
+
*Uses Monte Carlo update.  
-
Map (to determine where to point sensors)
+
**Map (to determine where to point sensors)
KalmanNavigator extends SimpleNavigator
KalmanNavigator extends SimpleNavigator
-
Skills: moves the robot to a desired destination Point as accurately as possible
+
*Skills: moves the robot to a desired destination Point as accurately as possible
-
Uses: ProbabilisticPilot, NormalPose, KalmanPoseProvider
+
*Uses: ProbabilisticPilot, NormalPose, KalmanPoseProvider
MonteCarloNavigator
MonteCarloNavigator
-
Skills: moves the robot to a desired destination Point as accurately as possible
+
*Skills: moves the robot to a desired destination Point as accurately as possible
-
Uses: ProbabilisticPilot, ParticleSetPose, MonteCarloPoseProvider
+
*Uses: ProbabilisticPilot, ParticleSetPose, MonteCarloPoseProvider
-
-------Higher levels of complexity  - ideas gleaned form other posts as I understand them.
+
===Higher levels of complexity  - ideas gleaned form other posts as I understand them.===
GlobalLocalizer
GlobalLocalizer
-
Skills: uses a Map to determine the robot position with minimum initial information
+
*Skills: uses a Map to determine the robot position with minimum initial information
-
Uses: Navigator, ProbabilisticPilot, ParticleSetPose, MonteCarlotPoseProvider
+
*Uses: Navigator, ProbabilisticPilot, ParticleSetPose, MonteCarlotPoseProvider
`
`
PathPlanner (tentative not sure of a good collaboration with Obstacle avoider)
PathPlanner (tentative not sure of a good collaboration with Obstacle avoider)
-
Skills:  determine  and follow the best route (a series of waypoints ) to get to a specified destination.
+
*Skills:  determine  and follow the best route (a series of waypoints ) to get to a specified destination.
-
Uses:  
+
*Uses: Map
-
Map
+
**Navigator ( goTo( next waypoint)
-
Navigator ( goTo( next waypoint)
+
Pose.  getX(), getY()
Pose.  getX(), getY()
 +
Obstacle avoider (tentative – not sure of a good relationship with Path Planner)
Obstacle avoider (tentative – not sure of a good relationship with Path Planner)
-
Skills:   
+
*Skills:   
-
go to specified destination despite obstacles
+
**go to specified destination despite obstacles
-
detect and avoid obstacles.
+
**detect and avoid obstacles.
-
Uses:  
+
*Uses:  
-
Navigator (for maneuvering around obstacle)  
+
**Navigator (for maneuvering around obstacle)  
-
PathPlanner (for next waypoint to avoid the obstacle ?)
+
**PathPlanner (for next waypoint to avoid the obstacle ?)
-
Map (update with representation of obstacle?)
+
**Map (update with representation of obstacle?)
-
          Pose .  getX(), getY()
+
 
Map
Map
-
Represents things in a plane, such as walls and landmarks
+
*Represents things in a plane, such as walls and landmarks
-
Skills ?
+
*Skills  
-
Distance to nearest  thing (in a specified direction) from (x,y)
+
**Distance to nearest  thing (in a specified direction) from (x,y)
-
Direction to the closest point in a wall from (x,y)
+
**Direction to the closest point in a wall from (x,y)
-
Others??
+
**Others??

Revision as of 06:58, 18 November 2009

Contents

Navigation proposal

Navigation names, definitions, and classes as agents, their skills and dependencies

Roger 17 November


First, some thoughts about the names of classes.

• Pilot was probably not the best choice. MovmentController might be better; shorter versions include MovementControl, MoveController, Controller . Any of these would be better than PoseController because pose is the dynamic state of a navigating robot and it changes as the result of a movement. It cannot be controlled directly. While there is a couple of years of code written by many users that would be broken if we abandon Pilot, if we ever going to do it, release 1.0 is the time. But I am inclined to let it stand. • I don’t care for Qualified as the QualifiedCoordinates in microedition.location, but prefer Probabilistic

Definitions of terms • Navigation: control of movement in the plane. • Directions in a the plane are relative to the direction of the X axis ; the direction of the Y axis is 90 degrees. • Heading: the direction the robot travels while moving forward. (if it moves backwards, the direction of motion is the heading + 180 degrees) • Pose: the current coordinates of the robot and its heading In probabilistic robotics, the pose is a random variable, the value of which is never known exactly. But decisions are based on a belief about the pose. This belief is represented as a probability distribution, the two most popular representations being the multi-variate normal and particle set. In this context, I use the term pose to mean “belief about the pose” • Elemental movements are : • travel in a straight line – change coordinates but not heading • rotate in place – change heading but not coordinates • trace a circular arc While it is true that a straight line is an arc with infinite radius, and rotation in place is an arc with zero radius, these special cases are the most commonly used and each deserves its own method. This allows the amount of movement to be specified by a single parameter.

The various tasks involved in navigation can usefully be classified by their complexity. 1. Execute elemental movements 2. Update the robot pose after each elemental movement, assuming an initial pose is known. In the absence of sensor data from external sources, this dead reckoning navigation and the errors of pose estimation increases with each move. 3. Improve the accuracy of the estimated pose by using sensor data and external landmarks, using algorithms such Kalman filter and extensions, and Monte Carlo Localization based on particle sets. 4. More complex tasks such as global localization, path planning, obstacle avoidance and combinations of these. I have not thought much about these, so will not discuss them. My view is that the classes and interfaces that implement navigation tasks at each level should be built on the level below. In the following, I use the language of agents that have skills of their own, and use other agents as helpers. I hope this focuses on concepts and not on the details of the API.


Level 1 Basic classes and interfaces

BasicPilot interface

  • Skills: travel in a straight line : forward or backward) ( I don’t think this is necessary in a Navigation package since a robot *that cannot change direction cannot it cannot navigate in a plane and is hardly worth building)
Arc Pilot  interface
  • Skills:
    • Executes two of the elementary movements in a plane: straight line and arc move, forward and backward . Movement can be interrupted by a client.

Provide estimate, at any time, of distance traveled and heading change since start of the current movement.

  • Uses:
    • Motor

Pilot interface

  • Skills:
    • Executes two of the elementary movements in a plane: straight line and arc move, forward and backward . Movement can be **interrupted by a client.
    • Provide estimate, at any time, of distance traveled and heading change since start of the current movement
  • Uses: Motor

DifferentialPilot class (renamed from TachoPilot ) implements Pilot

  • Skills: See Pilot
  • Uses: two TachoMotors for differential steering;

Level 2A update of pose

Pose

  • Skills:
    • update x,y, and heading using distance traveled and heading change
    • Calculate distance and heading to a point
  • Uses:
    • lejos.geom.Point, Math
  • Note: To update this simple pose requires a navigator class that uses a gets the distance and heading change from a Pilot and calls the update method on the Pose

Level 2B automatic update of pose at the end of each elemental movement.

Movement class

  • Skills:
    • none –a passive data carrier of distance traveled, heading change and movement type as supplied by MovementProvider , used by a

MovementListener

MovementProvider interface

  • Skills:
    • updates MovementListeners at the end of every elemental movement and when requested by a MovementListener
  • Uses:
    • Movement , MovementListener

MovementListener interface

  • Skills:
    • updates itself from data contained in a Movement which is supplied by a MovementProvider
  • Uses:
    • Movement , MovementProvider to supply a current Movement

UpdatingPilot interface extends Pilot implements MovementProvider

  • Skills:
    • See MovementProvider and Pilot
  • Uses
    • Movement, Motor

UpdatingDifferntialPilot class implements Updataing Pilot extends DifferentialPilot

  • Skills: see UpdatingPilot and DifferentialPilot

UpdateablePose extends Pose implements MoveListener

  • Skills: See Pose and MoveListener
  • Uses: Movement

SimpleNavigator (stripped down version of current class only has goTo(x,y)

  • Skills: moves the robot to a desired Point.
  • Uses: UpdatingPilot, UpdateablePose

RCNavigator extends SimpleNavigator

  • Uses: communicator to get commands from a remote controller.
===Probabilistic Navigation===

ProbabisticMovement class extends Movement *( could be called QualifiedMovement if you really want to)

  • Skills: carries three variable Normal distribution representation of a movement;

ProbabilisticMovementProvider interface extends MovementProvider

  • Skills: updates ProbabilisticMoveListeners
  • Uses: ProbabilisticMovement


ProbabilisticPilot interface extends UpdatingPilot implements ProbabilisticMovementProvider

  • Skills: ProbabilisticMovementProvider, UpdatingPilot

Uses: ProbabilisticMovement

ProbabilisticDifferentialPilot extends UpdatingDifferentialPilot implements ProbabilisticMovementProvider Skills: see ProbabilisticMovementProvider ,UpdatingDifferentialPilot Uses: ProbabilisticMovement

NormalPose extends UpdateablePose

  • Skills:
    • uses a three variable normal distribution to represent pose.
    • Returns x,y and heading with mean and variance.

ParticleSetPose extends UpdateablePose

  • Skills: uses a particle set to represent a pose. Can return mean and variance of x,y and heading.

KalmanPoseProvider (probably an abstract class with sub classes for different sensor models)

  • Skills:
    • Update a NormalPose using data from external sensors;
  • Uses:
    • Pose
    • various sensors and motors to direct the sensors;
    • Navigator (to aim the robot if sensors are fixed)
    • Updating algorithm using Kalman filter
    • Map (to determine where to point sensors)

MonteCarloPoseProvider (probably an abstract class with sub classes for different sensor models)

  • Skills: updates a ParticleSetPose
  • Uses:
    • ParticleSetPose
    • various sensors and motors to direct the sensors;
    • Navigator (to aim the robot if sensors are fixed)
  • Uses Monte Carlo update.
    • Map (to determine where to point sensors)

KalmanNavigator extends SimpleNavigator

  • Skills: moves the robot to a desired destination Point as accurately as possible
  • Uses: ProbabilisticPilot, NormalPose, KalmanPoseProvider

MonteCarloNavigator

  • Skills: moves the robot to a desired destination Point as accurately as possible
  • Uses: ProbabilisticPilot, ParticleSetPose, MonteCarloPoseProvider


Higher levels of complexity - ideas gleaned form other posts as I understand them.

GlobalLocalizer

  • Skills: uses a Map to determine the robot position with minimum initial information
  • Uses: Navigator, ProbabilisticPilot, ParticleSetPose, MonteCarlotPoseProvider

`

PathPlanner (tentative not sure of a good collaboration with Obstacle avoider)

  • Skills: determine and follow the best route (a series of waypoints ) to get to a specified destination.
  • Uses: Map
    • Navigator ( goTo( next waypoint)

Pose. getX(), getY()

Obstacle avoider (tentative – not sure of a good relationship with Path Planner)

  • Skills:
    • go to specified destination despite obstacles
    • detect and avoid obstacles.
  • Uses:
    • Navigator (for maneuvering around obstacle)
    • PathPlanner (for next waypoint to avoid the obstacle ?)
    • Map (update with representation of obstacle?)

Map

  • Represents things in a plane, such as walls and landmarks
  • Skills
    • Distance to nearest thing (in a specified direction) from (x,y)
    • Direction to the closest point in a wall from (x,y)
    • Others??
Personal tools