Path Planning and Computational Geometry
Outdoor robots must also be able to cope with various types of terrain (e.g., asphalt, grass, dirt, sand, snow).   The terrain surface will affect the required time and energy for a robot to travel from one point to another.   We have been investigating algorithms to compute efficient shortest paths between two points on various polyhedral surfaces.  



Mobile robots must also take into account the slope of the terrain as it navigates along a path.   Slopes too steep are either impossible or dangerous for most robots to climb.   Therefore, in addition to computing paths that take into account the terrain type, we also developed algorithms that take into account the slope of the path solutions.   Such paths are called shortest anisotropic paths.   The solutions are quite different and allow the robot safer travel.



Finally, since terrain data is often quite large (e.g., potentially terabytes of data), it is extremely time-consuming to process the information with a single computer/processor.   We therefore developed distributed computing algorithms for computing these terrain paths by allowing multiple computers/processors to share the workload in computing the solutions.  



Mobile robots have a limited amount of energy (i.e., battery, gasoline, propane, etc...).   Therefore, they are limited in the distance that they are able to travel before their energy runs out.   Various factors such as terrain steepness and terrain type weigh heavily on energy usage.   Consider a team of robots dropped into a terrain via parachute at various locations.   Assume that these robots need to meet together in order to accomplish their task at hand.   We have been developing algorithms to take into account the various terrain factors in order to compute an efficient meeting location for these robots that will minimize the total energy usage of the team, thereby maximizing the amount of remaining energy (e.g., battery power) at the meeting location.


In robotics one common/complex navigation problem is to determine a safe and efficient path for a robot to travel along between two locations.   2D Roadmap-based path planning algorithms are a group of algorithms that are utilized when we have full knowledge of the robots environment. This project involved the creation of an interactive application for the purpose of demonstrating how various 2D roadmap-based path planning algorithms work.   Various decomposition methods algorithms were tested based on triangulations, Voronoi diagram decomposition, grid sampling and probabilistic algorithms using rapidly exploring random trees.


This project investigated algorithms for determining efficient paths from one location to another on a terrain surface based on limited knowledge of the terrain.   That is, assume that a robot is standing at one location on a terrain and it has a kind of laser range finder that lets it map a small portion of the terrain nearby in all directions.   The problem is to try and head efficiently towards a goal location by computing a "best guess" partial path based on the current limited terrain knowledge.   As the robot moves towards the goal, it obtains new terrain readings and formulates additional "best-guess" paths.


Assuming a fixed-width circular robot, we implemented an algorithm that will allow the robot to cover the interior of a polygon by making a lap around the polygon and then working itself inwards by computing recursively a smaller polygon(s) representing the uncovered areas.   In the image below, the purple line indicates the path that the robot travelled, while the green lines represent the smaller recursive polygons that are covered in turn.   The blue portions are unreachable areas of the environment, which is defined by the robot's thickness.


This project investigated various strategies for determining efficient decomposition of a polygonal environment in order to evenly distribute the amount of environment that each robot is responsible for.   In the image below, the environment (e.g., building schematic) is decomposed into 4 colored areas which would be assigned to individual robots for task purposes.   Various techniques for decomposing the environment were investigated based on attempts to equalize the area, perimeter, maximum distance across or number of triangular regions that each robot would need to cover.  


This project incorporated two previous projects by first determining an efficient decomposition of a polygonal environment and then assigning portions of the environment to individual robots for them to cover their portion for security or cleaning tasks.   In the image below, the environment (e.g., building schematic) is decomposed into 10 colored areas which would be assigned to individual robots.  


In this project, we developed algorithms to allow groups of robots to travel on a 3D surface while maintaining line formation.   While travelling, each robot needed to remain within "line-of-sight" with their neighbours on the line.    This allows the team to ensure that any defective or malfunctioning robots are detected along the way so that no robot gets lost.


Consider an unbounded (i.e., open) environment with some obstacles.   Imagine a "treasure" that must be guarded from anyone approaching.   In this project, we developped an algorithm to compute efficient locations for guards to stand at in order to protect the treasure from any incoming robbers.   The algorithm attempts to find a minimum amount of "imaginary fencing" lines that will enclose the treasure and then places a sufficient number of guards along the fence pieces at "arms-length" distance from one another so that they are able to prevent any access through the imaginary fence line.


This project dealt with trying to find the geodesic center of a group of robots (points) placed inside a simple polygon.  The geodesic center is the point within the polygon where all the robots should move such that the maximum distance travelled (completely within the polygon) by each of the robots is minimized.   This will be an optimal meeting point for a group or robots if the goal is to ensure that each robot arrives at the meeting location with the maximum amount of power still remaining in its battery or gas tank.


This project involved implementing an algorithm for placing guards in a simple rectilinear polygon.  I implemented this in the Computational Geometry Workbench which was organized by Prof. J-R. Sack. The algorithm involved performing a plane sweep to create a quadrileteralization of the polygon and then coloring the graph representing the dual tree of this newly created subdivision.  The image above is a scan of a printout of a snapshot from the workbench showing a quadrilateralization of a rectilinear polygon.