# Roadmap:Navigation

Jump to: navigation, search

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

Roger 19 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, MoveControl, Controller .

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.

• I prefer "navigagtor" to "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.
• I prefer "Probabilisic" to "Qualified" as in QualifiedCoordinates in microedition.location. It's meaning is more obvious.

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. There are three:
• 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. At present, the Pilot classes do this.
2. Update the robot pose after each elemental movement, assuming an initial pose is known. This is dead reckoning navigation and the errors of pose estimation increases with each move. The current classes do this in various ways. SimpleNavigator updates a Pose after a move but not during a move. The automatic update of pose now uses a DifferentialPilot, UpdateablePose, Movement, MovementListener interface, MovementProvider interface. I think this is more complex than it needs to be.
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 navigation tasks at each level should be built on the level below, so the architecture of the navigation classes and interfaces should do likewise. Some simplifications of the existing structure are possible. The source of the information that is needed to update a pose in response to a movement can only originate with the a Pilot object that executed the movement. And the only class to be updates in response to a movement is a pose. So the The only class that can provide a movement is the one the executes it ( a Pilot) , and the only class that can be updated by a Movement is a pose. Hence the automatic update of pose can be done without the Movement class, the MovementProvider or the MovementListener interfaces, or a DeadReckoningPoseProvider class.

In the following, I use the language of agents that have skills own, and use other agents as helpers. I hope this focuses on concepts and not on the details of the API.

### Level 1 Basic Movement Control

Motor class

• Skills:rotate to a specified angle.

Implementation detail: Methods that perform this type of task can either return after the rotation is complete, or return immediately. In either case, the motor regulator thread stops the rotation when the rotation has been completed. The immediate return option allows the calling thread to perform other tasks while the motor is rotating.

BasicPilot interface

• Skills: travel in a straight line : forward or backward) ( I don’t think this interface is necessary in a Navigation package since a if robot that cannot change direction it cannot navigate plane buy only in a line 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 ).
• Any movement can be interrupted by a client a if the immediate return option is used.
• Provide estimate, at any time, of distance traveled and heading change since start of the current movement.
• Uses:
• Motor

Pilot interface

• Skills:
• Executes all three elementary movements: straight line, rotate in place, and arc move, (forward and backward )
• Any movement can be interrupted by a client if the immediate return option is used. This permits the calling thread to execute other tasks such as reading sensors while the movement is in progress.
• Provide an estimate at any time of distance traveled and heading change since start of the current movement. The calculation of distance traveled and heading change assumes that the two motors stop within few ms of each other. This can only be assured if the Pilot is the sole client of its motors, i.e. no other object makes method calls to its motors.
• Uses: Motor
• Implementing classes:
• TachoPilot
• CompassPilot extends TachoPilot
• uses Compass sensor to control straight line movement and correct heading after turning

### Level 2 Update pose

The robot pose needs to be updated (1) upon the completion an elemental movement and (2)if another class needs a information about the pose while the robot is moving. The first update is initiated by the MoveController, and the second is initiated by the pose. Pose class (now known as UpdateablePose)

• Skills:
• update x,y, and heading using distance traveled and heading change
• provide x,y and heading at any time
• Calculate distance and heading to a point
• register as a listener to a MoveController
• request update from a MoveController
• Uses:
• lejos.geom.Point, Math, MoveController

MoveController interface extends Pilot

• Skills:
• updates a Pose at the end of every elemental movement and when requested by a Pose.
• Uses : Pose
• See Pilot
• Implementing classes:
• DifferntialMoveControl (new name for DifferentialPilot) extends TachoPilot
• Bold textCompassMoveControl extends CompassPilot

ArcMoveController interface extends ArcPilot

• Skills:
• updates a Pose at the end of every elemental movement and when requested by a Pose

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

• Skills: moves the robot to a desired Point.
• Uses: DifferentialMoveControl , Pose

This class should replace proposal.PoseController

ArcNavigator (new name for proposal.ArcPoseController

• Skills: moves the robot to a desired Point and desired heading when it arrives
• Uses: ArcPilot extended for automatic update of pose.

### Level 3 Probabilistic Navigation

This section rather tentative. I have not studied the MCL classes carefully enough verify that this is a good framework for them.

ProbabilisticMoveControl interface extends MoveController

• Skills: also provides variance of distance traveled and heading change to ProbabilisicPose
• Implementing classes;
• ProbabilisticDifferentialControl extends DifferentialMoveControl

ProbabilisticPose externds Pose

• Skills: Returns x,y and heading with mean and variance.
• Uses: a probabilistic representation of a pose belief
• Implementing classes: NormalPose, ParticleSetPose

NormalPose implements ProbabilisticPose

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

ParticleSetPose implements ProbabilisticPose extends NormalPose

• Skills: Returns x,y and heading with mean and variance.
• Uses: particle set to represent a pose.

ProbabilisticPoseProvider interface

• Skills: updates a ProbabilisticPose
• ImplementingClasses: KalmanPoseProvider, MCLPoseProvider

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

• Skills:
• Update a NormalPose using data from external sensors;
• Uses:
• NormalPose
• 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)

MCLPoseProvider implements ProbabiliseicPoseProivder (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)

ProbabilisticNavigator extends SimpleNavigator

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

### Higher levels of complexity

I have not studied this enough to make constructive suggestions. My feeling is that class to deal with things like path finding, obstacle avoidance and mapping will need to be customized for the particular environment, so generic solutions to these problems may not be useful.