Path PlanningPath planning is the quintessential problem in algorithmic robotics. In its most basic form, the problem is to find a collisionfree path for a freeflying rigid object moving in an environment populated with stationary obstacles. By increasing the number of degrees of freedom of the robotic system (e.g., by considering articulated kinematic chains or multirobot systems), or by relaxing constraints on the environment (e.g., allowing obstacles to move), one can construct a broad range of problems that qualify as path planning problems. Our research has considered several variations of the path planning problem, and our contributions include both planning algorithms as well as graph algorithms that support the path planning process. An overview of the main projects is given below.
 
 
Path Planning for HumanoidsSalvatore Candido, YongTae Kim and Seth Hutchinson  
Path planning for walking robots is both a computationally expensive and
theoretically challenging problem. A typical bipedal robot has a high degree of
actuation, which gives the robot a wide range of motion. Although this is advantageous
for many tasks, because of the complexity of the robot's configuration space
and its stability requirements, it becomes difficult to find a trajectory to
navigate the robot between arbitrary locations. A common strategy to deal with
this complexity is to use a set of motion primitives for a given robot.
Unfortunately, reducing the robot's controls to a discrete set of motion
primitives creates a search problem that is also intractable. We have developed
two main algorithms that deliver heuristics and approximations that allow paths
to be planned quickly while not greatly sacrificing the quality of the
sequences of motion primitives chosen.
This collaboration with Professor YongTae Kim took place during his visit to my lab in the Beckman Institute.  
This work is described in the following papers.
 
 
Path Planning for PermutationInvariant FormationsStephen Kloder and Seth Hutchinson  
In many multirobot applications, the specific assignment of goal configurations
to robots is less important than the overall behavior of the robot formation.
In such cases, it is convenient to define a permutationinvariant multirobot
formation as a set of robot configurations, without assigning specific
configurations to specific robots. For the case of robots that translate in the
plane, we can represent such a formation by the coefficients of a complex
polynomial whose roots represent the robot configurations. Since these
coefficients are invariant with respect to permutation of the roots of the
polynomial, they provide an effective representation for permutationinvariant
formations. In this work, we extend this idea to build a full representation
of a permutationinvariant formation space. We have
described the properties of the
representation, and shown how it can be used to construct collisionfree paths
for permutationinvariant formations
The figure to the left shows two examples of collisionfree paths for permutationinvariant formations.  
This work is described in our TRO paper: Back to top  
 
Optimal Paths for LandmarkBased NavigationSourabh Bhattacharya and Seth Hutchinson  
In this work, we considered the problem of planning optimal paths for a
differentialdrive robot with limited sensing, that must maintain visibility of
a fixed landmark as it navigates in its environment.
We assume that the robot's vision sensor has a limited field of view (FOV),
and that the
fixed landmark must remain within the FOV throughout the robot's motion.
We first investigated the nature of extremal paths that satisfy the FOV constraint.
These extremal paths saturate the camera pan angle. We then showed that optimal
paths are composed of straightline segments and sections of these these
extremal paths. We provided a characterization of the shortest paths
for the system by partitioning the plane into a set of disjoint regions, such
that the structure of the optimal path is invariant over the individual regions
The figure to the left illustrates the partition of the plane that defines regions in which the various types of trajectory are optimal.  
This work is described in Sourabh's TRO paper: Back to top  
 
RealTime Path Planning in Changing EnvironmentsPeter Leven and Seth Hutchinson  
In this work,
we
presented a method for generating collisionfree paths for robots
operating in changing environments.
Our approach is closely related to probabilistic roadmap approaches.
These planners use preprocessing and query
stages, and are aimed at planning many times in the same environment.
In contrast, our preprocessing stage creates a representation of the configuration
space that can be easily modified in real time to account for changes in the
environment, thus facilitating realtime planning.
As with previous approaches,
we begin by constructing a graph that represents a roadmap in the configuration
space, but we do not construct this graph for a specific workspace.
Instead, we construct the graph for an obstaclefree workspace,
and encode the mapping from
workspace cells to nodes and arcs in the graph.
When the environment changes,
this mapping is used to make the appropriate modifications to the graph, and
plans can be generated by searching the modified graph.
The figure above shows a simple example. On the left, a twolink planar arm is located in a workspace that contains a single obstacle (the small black square). The middle figure illustrates the mapping of the obstacle from the workspace to the configuration space, superimposed on an existing configurationspace roadmap. The figure on the right shows the roadmap after enhancement.  
This work is described in Peter's IJRR paper: Back to top  
 
ManipulabilityBased Sampling for Probabilistic RoadmapsPeter Leven and Seth Hutchinson  
Probabilistic roadmaps (PRMs) are a popular representation used by many current path planners. Construction of a PRM requires the ability to generate a set of random samples from the robot's configuration space, and much recent research has concentrated on new methods to do this. In this work, we developed a sampling scheme that is based on the manipulability measure associated with a robot arm. Intuitively, manipulability characterizes the arm's freedom of motion for a given configuration. Thus, our approach is to densely sample those regions of the configuration space in which manipulability is low (and therefore, the robot has less dexterity), while sampling more sparsely those regions in which the manipulability is high. The figure above shows a few typical sample configurations.  
This work is described in Peter's TRO paper: Back to top  
 
Coordination on RoadmapsSteve LaValle and Seth Hutchinson  
This work made two contributions to geometric motion planning for multiple robots: 1) motion plans are computed that simultaneously optimize an independent performance measure for each robot; 2) a general spectrum is defined between decoupled and centralized planning, in which we introduce coordination along independent roadmaps. By considering independent performance measures, we introduced a form of optimality that is consistent with concepts from multiobjective optimization and game theory literature. We implemented multiplerobot motion planning algorithms that are derived from the principle of optimality, for three problem classes along the spectrum between centralized and decoupled planning: coordination along fixed, independent paths; coordination along independent roadmaps; and general, unconstrained motion planning.  
This work is described in Steve's TRA paper: Back to top  
 
Efficient Search and Hierarchical Motion Planning By Dynamically Maintaining SingleSource Shortest Paths TreesMichael Barbehenn and Seth Hutchinson  
Hierarchical approximate cell decomposition is a an approach to the geometric robot motion planning problem. In many cases, the search effort expended at a particular iteration can be greatly reduced by exploiting the work done during previous iterations. In this work, we described how this exploitation of past computation can be effected by the use of a dynamically maintained singlesource shortest paths tree. Our approach was to embed a singlesource shortest paths tree in the connectivity graph of the approximate representation of the robot configuration space. This shortest paths tree records the most promising path to each vertex in the connectivity graph from the vertex corresponding to the robot's initial configuration. At each iteration, some vertex in the connectivity graph is replaced with a new set of vertices, corresponding to a more detailed representation of the configuration space. Our dynamic algorithm is then used to update the singlesource shortest paths tree to reflect these changes to the underlying connectivity graph.  
This work is described in the following TRO paper: Back to top  
 
An Integrated Architecture for Robot Motion Planning and Control in the Presence of Obstacles with Unknown TrajectoriesRobert Spence and Seth Hutchinson  
In this work, we presented an integrated architecture for realtime planning and control of robot motions, for a robot operating in the presence of moving obstacles whose trajectories are not known a priori. The architecture comprises three control loops: an inner loop to linearize the robot dynamics, and two outer loops to implement the attractive and repulsive forces used by an artificial potential field motion planning algorithm. From a control theory perspective, our approach is unique in that the outer control loops are used to effect both desirable transient response and collision avoidance. From a motion planning perspective, our approach is unique in that the dynamic characteristics of both the robot and the moving obstacles are considered.  
This work is described in Rob's IEEE SMC paper: Back to top  
