We present a motion planner for autonomous highway driving that adapts the state lattice framework pioneered for planetary rover navigation to the structured environment of public roadways. The main contribution of this paper is a search space representation that allows the search algorithm to systematically and efficiently explore both spatial and temporal dimensions in real time. This allows the low-level trajectory planner to assume greater responsibility in planning to follow a leading vehicle, perform lane changes, and merge between other vehicles. We show that our algorithm can readily be accelerated on a GPU, and demonstrate it on an autonomous passenger vehicle.

In this paper we introduce focused A* heuristic recomputation (FAHR), an enhancement to A* search that can detect and correct large discrepancies between the heuristic cost-to-go estimate and the true cost function. In situations where these large discrepancies exist, the search may expend significant effort escaping from the ¿bowl¿ of a local minimum. A* typically computes supporting data structures for the heuristic once, prior to initiating the search. FAHR directs the search out of the bowl by recomputing parts of the heuristic function opportunistically as the search space is explored. FAHR may be used when the heuristic function is in the form of a pattern database. We demonstrate the effectiveness of the algorithm through experiments on a ground vehicle path planning simulation.

In this paper we present CASTRO, a new approach for achieving robust planned trajectories for nonlinear systems in the presence of modelling uncertainty. With CASTRO, we simultaneously optimize trajectories for multiple copies of the same system model, each using different estimates for the system parameters. The systems are constrained to use the same policy. With an appropriate sampling of system parameters in the optimization problem, the trajectory will be robust when run on the real system, compared to a trajectory optimized with just one model. We present results on a simulated double-link pendulum swing-up problem.

Patterns and pattern catalogs (pattern languages) have been proposed as a mechanism for re-use. Traditionally, patterns have been used to foster design re-use, and generative design patterns have been used to achieve both design and code re-use. In theory, a pattern catalog could be created and used to provide re-usable patterns within a project and across a group of related projects. This idea raises a natural question. How can we measure the effectiveness of a pattern catalog or compare the effectiveness of different pattern catalogs? In this paper, we define four metrics that can be used to measure the effectiveness of pattern catalogs. We illustrate these metrics by applying them to a case study that uses a pattern catalog of generative design patterns to generate scripting code for computer games. The metrics are general enough to assess any pattern catalog, independent of application domain or whether the patterns are generative or descriptive.

We describe in this paper a novel implementation of the interprocess communication (IPC) technology, called Broker, in support of the development and the operation of a complex robot system. We view each robot system as a collection of processes that need to exchange information, e.g. motion commands and sensory data, in a flexible and convenient fashion, without affecting each other's operations in case of a process's scheduled termination or unexpected failure. We argue that the IPC technology provides an ideal framework for this purpose, and we carefully make our design decisions about its implementation based on the needs of robotics applications. Broker is programming language, operating system, and hardware platform independent and has served us well in a RoboCup project and collective robotics experiments, in both simulation and real-world environments.