Motion Planning HW6

Ross Hatton

``Inside" and ``Outside" vectors

Each line segment in my functions is inherently oriented, in that it is defined by an ordered pair of points. I consider the line segment as a vector departing from the first point and arriving at the second.

The boundaries on all my objects (robot and obstacles) are positively oriented (when moving around the object in the direction of its component line segments, the interior of the object is always on the left). I use this property extensively to determine whether a given line segment is inside or outside of any given object.

At the intersection of two line segments, one line segment will have come from ``inside" the other if its vector has a positive dot product with the outward pointing normal vector of the other segment. This rule can be expanded to handle special cases, such as segments which meet at endpoints, though the rules are more complex.

Implementation

Each obstacle in the world has a number. Each edge is identified by the numbers of the obstacles it separates, and each node by the numbers of the three obstacles it is closest to.

The robot gets onto the graph by running the corr_loop function with a coarse step size, then a finer one. Having reached the graph, it detects the edge it is on and follows it to a node with follow_edge_to_node. Having reached the node, it uses the identify_node function to find the edges which connect to the node. The robot then follows each edge to its terminal node, and adds that node to the graph. The algorithm terminates when all nodes in the graph have no unexplored edges.

The distances and directions to the obstacles are found by first finding the nearest vertex to the robot, then projecting the robot's position onto the obstacle edges connecting to that vertex. The closet point on the obstacle is the nearest projection which is on the edge of the obstacle, or the vertex if neither projection is on the obstacle.

Movie 1 Movie 2 Matlab code

corr_loop.m

Take correcting steps until robot is on the GVD.

correction_step.m

Step towards the GVD.

cyclic.m

1-based mod function.

detect_collisions.m

Detect any boundary collisions between two world-objects.

distance_to_obstacle.m

Find the distance from the robot to an obstacle.

distance.m

Get the Euclidean distance between a point and a set of points.

draw_object.m

Draw a world-object.

draw_set.m

Draw an array of world-objects.

follow_edge_to_node.m

Follow an edge of the GVD to the next node.

identify_node.m

Determine whether the node the robot is at has been reached before.

meetpoint.m

Find collisions between two sets of line segments.

nearest_obstacles.m

Find the three nearest obstacles to the robot.

node_check.m

Test whether the robot is at a node.

outboard_test.m

Test whether a vector is inside or outside of a pair of vectors.

set_explored.m

Set the ``explored" flags for a node.

trace_voronoi.m

Main function for generating the GVD.

update_vertices.m

Generate the world-vertices for an object from its local geometry.

voronoi_step.m

Step along the GVD.

About this document ...

Motion Planning HW6

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 writeup.tex

The translation was initiated by Ross Hatton on 2007-11-05