GVG Algorithm Outline





Initialization:
The program connects to the robot and initialize the encoders and sensors. The datastructures for mapping and exploration are also initialized at this time.


Access GVG:
In order to access the nearest GVG edge in the environment, the sonar sensors are polled to determine local minima. The robot then turns away from the nearest object and moves forward, checking local minima. When equidistance is reached the robot stops and turns onto the calculated GVG edge. Now the main loop of the algorithm may begin.


Edge Trace:
This is a velocity based control loop. The sonar sensor data is processed using the arc transversal method(ATM) to refine the coordinates of local minima. The local minima coordinates are used to calculate the GVG edge, which is a line that can be followed by adjusting the robot velocities appropriately. Most of the time spent in this stage of the algorithm, the robot follows the GVG edge defined by the closest pair of local minima. When the local minima indicate that the robot is approaching a meetpoint, control is passed to the Meetpoint Homing control law. When the local minima indicate that the robot is approaching a boundary node, control is passed to the Boundary Registration procedure.


Meetpoint Homing:
This is a short control loop that calculates a desired coordinate position for the robot based on three or more local minima. This coordinate is the equidistant point of all local minima and is referred to as a meetpoint. This control law is very important because the meetpoint is a stable feature of the environment, and the robot is able to consistently move to the coordinates with great accuracy. Once the robot halts at the coordinates of the meetpoint, control passes to Meetpoint Registration.


Meetpoint Registration:
The sensor data at a meetpoint defines a signature for that meetpoint. Using the signature with GVG connectivity information, the meetpoint can be classified as a new point in the environment or a previously explored coordinate. In both cases this information is stored and control is then passed to the Determine Direction function.


Boundary Registration:
When a boundary node is detected the robot halts and registers the node information. This function is similar to Meetpoint Registration and differs in that no homing takes place. Control is passed to the Determine Direction function.


Determine Direction:
This function analyzes the stored data and determines which edge of the robot's current node should be explored. When all of the current node edges are explored, a search by Djykstra's algorithm (breadth-first-search) on the GVG determines the closest node with unexpolored edges and which edge the robot should follow to reach that node. If a departing edge is calculated, then the robot is rotated onto that edge and control is passed to Edge Trace. If the search determines that the GVG has been completely explored, then the algorithm is Finished.