Navigational overview
 Recent changes
 Navigation  Robotics
 Navigation  Games
 Heuristic Search
 RealTime Search
 Collision Detection
 Publication lists
 Books
 Other links
Many of the articles below are postscript files (.ps).
If you need a postscript viewer try
Ghostview. Files packed with compress (.Z)
and with gzip (.gz) can be unpacked with gzip
which is available at the official
GNU ftp site. For DVI (DeVice Independent) files use dvips or
similar to convert into postscript.

Using genetic algorithms for robot motion planning
 [Gzipped postscript]
Abstract: [...] we show that the path planning problem
can be expressed as an optimization problem and thus solved with a
genetic algorithm. We illustrate this approach by building a path
planner for a planar arm with two degree of freedom, then we
demonstrate the validity of the method by planning paths for a holonomic
mobile robot [...]
Juan Manuel Ahuactzin,
ElGhazali Talbi,
Pierre Bessiere, and
Emmanuel Mazer

Towards the Unification of Navigational Planning and Reactive
Control
 [Compressed postscript]
Abstract: The illusion that reactive and hierarchical planning
methods are at odds with each other needs to be dropped. By exploiting
each methods's strengths, a synthesis of hierarchical and reactive
paradigms can yield robust, flexible, and generalizable
navigation. Psychological and neuroscientific studies support this claim.
Ronald C. Arkin

Spatial Learning and Localization in Animals: A Computational Model
and its Implications for Mobile Robots
 [Postscript]
Abstract: The ability to acquire a representation of the
spatial environment and the ability to localize within it are essential
for successful navigation in apriori unknown environments [...] This
paper briefly reviews the relevant neurobiological and cognitive data
and their relation to computational models of spatial learning and
localization used in mobile robots [...] The resulting model allows
a robot to learn a placebased, metric representation of space in
apriori unknown environments and to localize itself in a
stochastically optimal manner [...]
Karthik Balakrishnan,
Olivier Bousquet, and
Vasant Honovar

Gridbased Navigation for Mobile Robots
 [Compressed postscript]
Introductory article to navigation using a rectangular uniform grid
and static wavefront expansion.
Tucker Balch

Dynamic trajectory planning for crosscountry navigator
 Abstract:Autonomous CrossCountry Navigation requires
planning algorithms which supports rapid traversal of challenging
terrain while maintaining vehicle safety [...] The planning system
uses a recursive trajectory generation algorithm, which generates
spatial trajectories and then heuristically modifies them to achieve
safe paths around obstacles. Velocities along the spatial trajectory
are then set to ensure a dynamically stable traversal [...]
Barry L. Brumitt,
R. Craig Coulter,
Anthony Stentz

An Opportunistic Global Path Planner
 [Postscript]
Abstract: In this paper we describe a robot path planning algorithm
that constructs a global skeleton of freespace by incremental local
methods. The curves of the skeleton are the loci of maxima of an
artificial potential field that is directly proportional to [the]
distance of the robot from the obstacles. Our method has the
advantage of fast convergence of local methods in uncluttered
environments, but it also has a deterministic and efficient method
of escaping local extremal points of the potential function [...]
John F. Canny and
Ming Chieh Lin

On AllTerrain Vehicle Motion Planning
 [Gzipped postscript]
Introduction: In this paper, we address the problem of
motion planning for a mobile robot moving on a hilly three dimensional
terrain, and subject to dynamic and physical interaction constraints. [...]
a mixed planning method [...] based upon a twolevel approach combining
a discrete search strategy operating on a subset of the configuration
space of the robot, and a continuous motion generation technique
considering the kinematic and dynamic constraints of the task [...]
Moez Cherif

Harmonic Functions and Collision Probabilities
 Abstract: There is a close relationship between harmonic
functions  which have recently been proposed for path planning 
and hitting probabilities for random processes. The hitting probabilities
for random walks can be cast as a Dirichlet problem for harmonic functions,
in much the same way as in path planning. This equivalence has
implications both for uncertainty in motion planing and in the
application of machine learning techniques to som robot problems [...]
Christopher I. Connolly

Robust Path Planning in the Plane
 [Gzipped postscript]
Abstract: This work presents an approach to plan motion
strategies for robotics tasks constrainted by uncertainty in position,
orientation and control. Our approach operates in a (x, y, theta)
configuration space and it combines two local functions: a contactbased
attraction function and an exploration function. Compliant motions are
used to reduce the position/orientation uncertainty. An explicit geometric
model for the uncertainty is defined to evaluate the reachability of the
obstacle surfaces when the robot translates in free space.
Fernando De la Rosa,
Christian Laugier, and
Jose Najera

The Geometrical Representation of Path Planning Problems
 Abstract: The path planning problem for arbitrary devices
is first and foremost a geometrical problem. For the field of control
theory, advanced mathematical techniques have been developed to
describe and use geometry. In this paper, we use the notations of
the flow of vector fields and geodesics in metric spaces to formalize
and unify path planning problems. A path planning algorithm based on
flow propagation is briefly discussed. Applications to the theory
to motion planning for a robot arm, a maneuvering car, and Rubik's
Cube are given. These very different problems (holonomic, nonholonomic
and discrete, respectively) are solved by the same unified procedure.
Leo Dorst,
Indur Mandhyan, and
Karen Trovato

Maze Navigation Using Optical Flow
 [Compressed postscript]  File appears to be corrupted.
Abstract: Some recent work with autonomous robots has
focused on using optical flow for "direct" control of speed and
rotation in obstacle avoidance and other simple behaviors. This work
has been inspired by work with insects showing similar mechanisms.
To extend these behaviors, three methods of maze navigation are
investigated in a simulated robot modeled after a real one [...]
Andrew Duchon

Ecological Robotics
 [Compressed postscript]
Abstract: There are striking parallels between ecological
psychology and the new trends in robotics and computer vision, particularly
regarding how agents interact with the environment. We present some ideas
from ecological psychology, including control laws using optic flow,
affordances and action modes, and describe our implementation of these
concepts in a small mobile robot which can avoid obstacles and chase or
flee moving targets solely using optic flow [...]
Andrew Duchon,
William Warren and
Leslie Pack Kaelbling

CollisionFree Object Movement Using Vector Fields
 Abstract:We present a technique for automatically providing
animation and collision avoidance in a generalpurpose computer
graphics system. The technique, which relies on an expanded notion
of vector fields, allows users to easily set up and animate objects,
then prevents objects from colliding as the animation proceeds [...]
Parris K. Egbert and
Scott H. Winkler

Force Strategies for Cooperative Tasks in Multiple Mobile Manipulation Systems
 [Postscript]
Abstract: Mobile manipulation capabilities are key to many
new applications of robotics in space, underwater, construction, and
service environments [...] This work builds on four methodologies we
have previously developed for fixedbase manipulation: the Operational
Space Formulation for taskoriented robot motion and force control; the
Dextrous Dynamic Coordination of Macro/Mini structures for increased
mechanical bandwidth of robot systems; the Augmented Object Model for
the manipulation of objects in a robot system with multiple arms; and
the Virtual Linkage Model for the characterization and control of internal
forces in a multiarm system. We present the extension of these
methodologies to mobile manipulation systems and propose a new decentralized
control structure for cooperative tasks [...]
Oussama Khatib,
K. Yokoi,
K. Chang,
Diego Ruspini,
Bob Holmberg,
Arancha Casal, and
Andreas Baader

Combining PhysicallyBased Simulation of Colliding Objects with
Trajectory Control
 Abstract: This paper describes a method that facilitates
the use of physically based models by animators. The main point is
to give the animator a familiar interface, while providing a
simulation module which detects collisions thus enhancing
realism. [...]
Alexis Lamouret,
MariePaule Gascuel,
JeanDominique Gascuel

Robot Motion Planning: A GameTheoretic Foundation
 [Gzipped postscript]
A method based on Game Theory to deal with uncertainty in robot
motion planning.
Steven M. LaValle

Motion Strategies for Maintaining Visibility of a Moving Target
 ...
Steven M. LaValle,
Héctor H. GonzálezBañoz,
Craig Becker and
JeanClaude Latombe

Finding an Unpredictable Target in a Workspace with Obstacles
 [Gzipped postscript]
Abstract: This paper introduces a visibilitybased motion
planning problem in which the task is to coordinate the motions of one
or more robots that have omnidirectional vision sensors, to eventually
"see" a target that is unpredictable, has unknown initial position, and
is capable of moving arbitrarily fast. A visibility region is associated
with each robot, and the goal is to guarantee that the target will
ultimately lie in at least one visibility region [...] A complete
algorithm for computing the motion strategy of the robots is also
presented [...]
Steven LaValle,
David Lin,
Leonidas Guibas,
JeanClaude Latombe, and
Rajeev Motwani

BehaviorBased Control: Examples from Navigation, Learning, and Group Behavior
 [Gzipped postscript]
Abstract:This paper describes the main properties of
behaviorbased approaches to control. Different approaches to designing
and using behaviors as basic units for control, representation, and
learning are illustrated on three empirical examples of robots performing
navigation and pathfinding, group behaviors, and learning behavior
selection.
Maja Mataric

Elastic bands: Connecting Path Planning and Control
 [Postscript]
Abstract: Elastic bands are proposed as the basis for a new
framework to close the gap between global path planning and
realtime sensorbased robot control. An elastic band is a
deformable collisionfree path. The initial shape of the elastic is
the free path generated by a planer. Subjected to artificial forces,
the elastic band deforms in real time to a short and smooth path
that maintains clearance from the obstacles [...] This paper
outlines the framework and discusses an efficient implementation
based on bubbles.
Sean Quinlan and
Oussama Khatib
 MITSIM
 Abstract:A MIcroscopic Traffic SIMulator (MITSIM) has been
developed for modeling traffic networks with advanced traffic
control, route guidance and surveillance systems. MITSIM represents
networks in detail and simulates individual vehicle movements using
car following, lane changing, and traffic signal responding logic. A
probabilistic route choice model is used to capture drivers' route
choice decisions in the presence of real time traffic information
provided by route guidance systems [...]
Qi Yang and
Haris N. Koutsopoulos

Continuous Motion Plans for Robotic Systems with Changing Dynamics Behavior
 [Postscript]
Abstract: The main objective of this paper is to address
motion planning for systems in which the dynamic equations describing
the evolution of the system change in different regions of the state
space. We adopt the control theory point of view and focus on the
planning of open loop trajectories that can be used as nominal inputs
for control [...] We present a formal framework for describing systems
with changing dynamic behavior borrowing from the litterature on hybrid
systems. We formulate the optimal control problem for such systems,
develop a novel technique for simplifying the problem when the sequence
of discrete states is known, and suggest a numerical method for dealing
with inequality constraints [...]
Milos Zefran,
Jaydev Desai, and
Vijay Kumar

Dynamtic path planning
 [Gzipped postscript]
Abstract: Path planning is dynamic when the path is
continually recomputed as more information becomes available. A
computational framework for dynamic path planning is proposed which
has the ability to provide navigational directions during the
computation of the plan. Path planning is performed using a
potential field approach. We use a specific type of potential
function  a harmonic function  which has no local minima [...]
John S. Zelek

A Mobile Robot Navigation Exploration Algorithm
 [Postscript]
Abstract: This paper will present an algorithm for path
planning to a goal with a mobile robot in an unknown
environment. The robot maps the environment only to the extent that
is necessary to achieve the goal [...] Paths are generated by
treating unknown regions in the environment as free space. As
obstacles are encountered en route to a goal, the model of the
environment is updated and a new path to the goal is planned and
executed [...] The algorithm presented in this paper makes use of
the quadtree data structure to model the environment and uses the
distance transform methodology to generate paths for the robot to
execute.
Alexander Zelinsky

Mission Planning and Control Path Planning
 Includes VectorError Path Planner, DistanceTransform Path Planner,
Potential Path Following Method, and (Forward and Back propagation)
A* Algorithm
Mission Planning and Control

An optimal pathfinder for vehicles in realworld digital terrain maps
 Abstract: This paper describes an algorithm for
approximately finding the fastest route for a vehicle to travel
between two points in a digital terrain map, avoiding obstacles
along the way [...] The enemies are avoided by staying out of their
line of sight. However, the general results of this paper should be
feasable for a much wider range of applications ranging from
complex GIS [Geographic Information Systems] systems to home
computer games. The approach taken in this work is to translate the
problem into a least cost path graph problem with an associated cost
function on the graph edges [...]
Frank Markus Jönsson

Smart Unit Navigation
 Introduction: Navigating a unit from A to B with some
intelligence has always been an interesting problem frequently asked by
game programmers. There are different ways of implementing this and I
will try to show some algorithms and examples.
John Christian Lønningdal

MuttonRobot
 A* again
Cyril Mathey and Sebastien
Marchant

Various Game Programming stuff
 Source code, descriptions, and links for navigation and AI in games.
Amit
Patel

Steering Behaviors For Autonomous Characters
 [Java enabled browser required]
Abstract: This paper presents solutions for one
requirement of autonomous characters in animation and games:
the ability to navigate around their world in a lifelike and
improvisational manner. These "steering behaviors" are largely
independent of the particulars of the character's means of
locomotion. Combinations of steering behaviors can be used to
achieve higher level goals (For example: get from here to there
while avoiding obstacles, go down this corridor, join that group
of characters...) This paper divides motion behavior into three
levels. It will focus on the middle level of steering behaviors,
briefly describe the lower level of locomotion, and touch lightly
on the higher level of goal setting and strategy.
Craig W. Reynolds

Smart Moves: Intelligent Pathfinding
 Introduction: Of all the decisions involved in computergame
AI, the most common is probably pathfinding  looking for a good route
for moving an entity from here to there. The entity can be a single person,
a vehicle, or a combat unit; the genre can be an action game, a simulator,
a roleplaying game, or a strategy game. But any game in which the computer
is responsible for moving things around has to solve the pathfinding problem.
And this is not a trivial problem. Questions about pathfinding are regularly
seen in online game programming forums, and the entities in several games
move in less than intelligent paths. However, although pathfinding is not
trivial, there are some wellestablished, solid algorithms that deserve to
be known better in the game community.
Bryan Stout

Bolo Robot
 Not exactly navigation... but close.
Andrew
Wilson and
Stephen Intille

How to do: Artificial Intelligence
 From the Game Programming Galaxy. A brief mentioning of Pursuit and
Evade, and of obstacle avoidance

Heuristic search
 Hill climing, bestfirst, A*, AND/OR trees. Part of a course.
Steve Belleguelle

Shortest Paths Algorithms: Theory and Experimental Evaluation
 [Gzipped postscript]
Abstract: We conduct an extensive computational study of
shortest paths algorithms, including some very recent algorithms. We also
suggest new algorithms motivated by the experimental results and prove
interesting theoretical results suggested by the experimental data. Our
computational study is based on several natural problem classes which
identify strengths and weaknesses of various algorithms. These problem
classes and algorithm implementations form an environment for testing
the performance of shortest paths algorithms. The interaction between
the experimental evaluation of algorithm behavior and the theoretical
analysis of algorithm performance plays an important role in our research.
Boris Cherkassky,
Andrew Goldberg, and
Tomasz Radzik

Online and Dynamic Algorithms for Shortest Path Problems
 [Compressed DVI]
Abstract: We describe algorithms for finding shortest paths
and distances in a planar digraph which exploit the particular topology
of the input graph. An important feature of our algorithms is that they
can work in a dynamic environment, where the cost of any edge can be
changed or the edge can be deleted. For outerplanar digraphs, for instance,
the data structures can be updated after any such change in only O(log n)
time, where n is the number of vertices of the digraph [...]
Hristo Djidjev,
Grammati Pantziou, and
Christos Zarliagis

New Results About SubAdmissibility for General Families of Heuristic
Search Algorithms
 [Gzipped postscript]
Abstract: We propose a formal generalization for various
works dealing with Heuristic Search in state graphs. This generalization
focuses on the properties of the evaluation functions, on the characteristics
of the state graph, on the notion of path length, on the procedures that
control the choices of the node expansion, on the rules that govern the
updating operations. Consequently, we present new theorems about the
subadmissibility [...]
Henri Farreny

Search in Temporal Domains
 [Gzipped postscript]
Abstract: Bestfirst search algorithms have been widely
used to find a minimum cost path in graph search. To formulate certain
problems involving temporal events, it is at times instrumental to use
graphs whose edge costs are timedependent. In such a graph, shortest
paths are dependent on time at which traversal in the graph begins [...]
In this paper, a bestfirst algorithm is generalized to handle
timedependent graphs to find shortest paths together with their start
time characteristics and some properties of the algorithm are investigated.
Kikuo Fujimura

Implementations of Dijkstra's Algorithm Based on MultiLevel
Buckets
 [Gzipped postscript]
Abstract: A 2level bucket data structure has been shown
to perform well in a Dijkstra's algorithm implementation. In this
paper we study how the implementation performance depends on the
number of bucket levels used. In particular we are interested in
the best number of levels to use in pratice.
Andrew Goldberg and
Craig Silverstein

Expected Performance of Dijkstra's Shortest Path Algorithm
 [Gzipped postscript]
Abstract: We show that the expected number of
decreasekey operations in Dijkstra's shortest path
algorithm is O(n log(1 + m/n)) for an nvertex, marc graph.
The bounds holds for any graph structure [...] This result
explains the small number of decreasekey operations
observed in practice and helps to explain why Dijkstra codes
based on binary heaps perform better than ones based on
Fibonacci heaps.
Andrew Goldberg and
Robert Tarjan

Hierarchical A*: Searching Abstraction Hierarchies Efficiently
 [Postscript]
Abstract: Abstraction, in search, problem solving, and planning,
works by replacing one state space by another (the "abstract space") that is
easier to search. The results of the search in the abstract space are used
to guide search in the original space. A natural application of this
technique is to use the length of the abstract solution as a heuristic
for A* in searching in the original space. However, there are two obstacles
to making this work efficiently. The first is a theorem stating that for
a large class of abstractions, "embedded abstractions", every state expanded
by blind search must also be expanded by A* when its heuristic is computed
in this way. The second obstacle arises because in solving a problem A*
needs repeatedly to do a search of the abstract space while computing its
heuristic. This paper introduces a new abstractioninduced search technique,
"Hierarchical A*," that gets around both of these difficulties: first, by
drawing from a different class of abstractions, "homomorphism abstractions,"
and, secondly, by using novel caching technique to avoid repeatedly expanding
the same states in successive searches in the abstraction space. Hierarchical
A* outperforms blind search on all the search spaces studied.
Robert Holte,
M.B. Perez,
Robert Zimmer, and
Alan MacDonald

The Tradeoff Between Speed and Optimality in Hierarchical Search
 [Postscript]
Abstract: Abstraction works by replacing a state space, SS,
by another, "abstract" space that is easier to search, SS'. There are two
wellknown strategies for employing the "abstract" solutions found in SS'
to guide the search in the original space. The first uses the lengths of
the abstract solutions as a heuristic for an A* search of SS. This always
produces optimal solutions. The second strategy does not guarantee
optimality, but it does tend to find a solution quickly. In this paper,
we study the tradeoffs between the loss of optimality and the gain of
speed in moving from the one strategy to the other [...]
Robert Holte,
M.B. Perez,
Robert Zimmer, and
Alan MacDonald

Bidirectional Heuristic Search Reconsidered
 [Postscript]
Abstract: The assessment of bidirectional heuristic
search has been incorrect since it was first published more than a
quarter of a century ago. [...] we present both a new generic approach
to bidirectional heuristic search and a new approach to dynamically
improving heuristic values that is feasible in bidirectional search
only. These approaches are put into perspective with both the traditional
and more recently proposed approaches in order to facilitate a better
overall understanding. [...] Empirical results of experiments with our
new approaches show that bidirectional heuristic search can be performed
very efficiently and also with limited memory. These results suggest
that bidirectional heuristic search appears to be better for solving
certain difficult problems than corresponding unidirectional search [...]
Hermann Kaindl and
Gerhard Kainz

Parallel BestFirst of StateSpace Graphs: A Summary of Results
 [Postscript]
Abstract: This paper presents many different parallel
formulations of the A*/BranchandBound search algorithm. The
parallel formulations primarily differ in the data structure
used [...] Concurrent and distributed priority queues used in
these parallel formulations can be used in many parallel
algorithms other than parallel A*/branchandbound.
Vipin Kumar,
K. Ramesh, and
Vempaty Nageshwara Rao

Efficient Parallel Algorithms on Reconfigurable Mesh Architectures
 Abstract: This dissertation describes a number of novel
parallel algorithms for solving mazerouting problems and string
matching problems on a proposed reconfigurable mesh architecture [...]
Section II presents a number of timeefficient algorithms to solve
the mazerouting problem. Mazerouting algorithms are used in VLSI
routing and robot path planning. In that section, definitions for
absolute shortest path (ASP), shortest duplexpath (SDP), shortest
triplexpath (STP), and single shortest path (SSP) are given. Then,
O(1) algorithms are presented for: (i) testing the existence of
specific types of paths, (ii) finding an ASP and a SDP. In addition,
fast algorithms are presented for finding the STP and the SSP. The
simulation results indicate that a large percentage of the shortest
paths that exist between two randomly selected terminals fall into
one of the categories studied in this section [...]
HsiChieh Lee

TimeVarying K Shortest Paths Algorithm
 [Gzipped postscript]
Abstract: We examine a particular algorithm that finds the
k shortest paths between a given source node and destination node of a
directed graph with nonnegative edge weights [...] It is a generalization
of Dijkstra's algorithm, so coding is relatively straightforward [...]
Furthermore it is easy to extend the algorithm to handle a distance
function that varies with time [...]
John Leo

A Hybrid Technique for Deterministic Algorithms with a Shortest Path Example
 [Compressed postscript]
Abstract: A general hybridization technique, potentially
effective in improving algorithmic efficiency, is presented for deterministic
algorithms. Extensions of existing hybrid techniques for nondeterministic
algorithms to deterministic ones are also described. The new technique
uses one or more input parameters to predict the behavior of a group of
algorithms and then takes advantage of the fastest method for that instance.
We have applied this technique to Dijkstra's and Floyd's algorithms for
the shortest path problem to create a hybrid dependent on the size and
density of the input graph [...] The hybrid algorithm was able to provide
16% and 26% improvement over each parent algorithm respectively, for large
graphs and a uniform distribution of density.
Miroslaw Malek and
Ahmed Azfar Moin

Dual algorithms for the Shortest Path Tree problem
 [Gzipped postscript]
Abstract: We consider dual approaches for the Shortest Path Tree
problem. After a brief introduction to the problem, we review the most
important dual algorithms which have been described in the literature for
its solution, and propose a new family of dual ascent algorithms. In these
algorithms, "local" and "global" dual updating operations are performed at
the nodes in order to enlarge a partial shortest path tree, which at the
beginning contains only the root node, until a shortest path tree is found.
Several kinds of dual updating operations are proposed, which allow one to
derive different dual algorithms from a general shcema. One of them, in
particular, which is based only on global operations, can be viewed as a
dual interpretation of Dijkstra's classical algorithm [...]
Stefano Pallottino and
Maria Grazia Scutella

Shortest Path Algorithms in Transportation Models: Classical and Innovative
Aspects
 [Gzipped postscript]
Abstract: Shortest Path Problems are among the most studied
network flow optimization problems, with interesting applications in
various fields. One such field is transportation, where various kinds of
shortest path problems need to be solved [...] The aim of this work is to
present in a unifying framework both the main algorithmic approaches for
solving the shortest path problems that arise most frequently in the
transportation field, and some important implementation techniques which
allow effient procedures [...]
Stefano Pallottino and
Maria Grazia Scutella

PathFinding and the A* Algorithm
 An excellent description of A*.
Amit Patel

A general framework for shortest path algorithms
 [Compressed postscript]
Abstract: In this paper we present a general framework for
shortest path algorihtms, including amongst others Dijkstra's algorithm
and the A* algorithm. By showing that all algorithms are special cases
of one algorithm in which some of the nondeterministic choices are made
deterministic, termination and correctness can be proved by proving
termination and correctness of the root algorithm. Furthermore, several
invariants of the algorithms are derived which improve the insight with
respect to the operations of the algorithms.
Wim Pijls and
Antoon Kolen

An Incremental Algorithm for a Generalization of the ShortestPath Problem
 [Compressed postscript]
Abstract: The grammar problem, a generalization of the
singlesource shortestpath problem introduced by Knuth, is to compute
the minimumcost derivation of a terminal string from one or more nonterminals
of a given contextfree grammer, with the cost of a derivation being
suitably defined. In this paper we present an incremental algorithm for a
version of the grammar problem. As a special case of this algorithm we
obtain an efficient incremental algorithm for the singlesource shortestpath
problem with positive edge lengths. The aspect of our incremental
algorithms that distinguishes it from all other work on the dynamic
shortestpath problem is its ability to handle "multiple heterogeneous
modufications": between updates, the input graph is allowed to be
restructured by an arbitrary mixture of edge insertions, edge deletions,
and edge=length changes.
G. Ramalingam and
Thomas Reps

Optimal and Efficient Path Planning for PartiallyKnown
Environments
 [Postscript]
Abstract: [...] This paper introduces a new algorithm, D*,
capable of planning paths in unknown, partially known, and changing
environments in an efficient, optimal, and complete manner.
Anthony Stentz

The Focussed D* Algorithm for RealTime Replanning
 [Postscript]
Abstract: [...] The D* algorithm (Dynamic A*) plans optimal
traverses in realtime by incrementally repairing paths to the
robot's state as new information is discovered. This paper describes
an extension to D* that focusses the repairs to significantly reduce
the total time required for the initial path calculation and
subsequent replanning operations. This extension completes the
development of the D* algorithm as a full generalization of A* for
dynamic environments, where arc costs can change during the traverse
of the solution path
An online description
Anthony Stentz

Updating Shortest Paths
 [Gzipped postscript]
Abstract: Moving target search is a state space approach for
finding nonstationary goals. The plot is given by a realtime situation
in which the target has to be captured by a socalled problem solver [...]
The trailblazer search does not use information about former maps. Thus,
the main problem tackled in this paper is the incremental calculation of
the shortest path tree [...]
Stefan Edelkamp

New Strategies in RealTime Heuristic Search
 [Gzipped postscript]
Abstract: In contrast to offline search algorithms such as
A* and IDA*, in realtime heuristic search we have to commit a move
within a limited search horizon or time. [...] An algorithm is said
to learn if it improves its performance over successive problem trials.
[...] The aim of the strategies proposed in this paper is to improve
the estimations found in LRTA* [Learning RealTime A* by Richard Korf]
Experimentally we show that CRTA* [RTA* with cleaning up strategy]
expands significantly less modes than LRTA* and thus converges faster
to the optimal values.
Stefan Edelkamp
and
Jürgen Eckerle

Two is not always better than one: Experiences in RealTime Bidirectional
Search
 [Postscript]
Abstract: This paper investigates realtime bidirectional
search algorithms, where two problem solving agents, starting from
the initial and goal states, physically move towards each other [...]
Toru Ishida

RealTime Search in NonDeterministic Domains
 [Gzipped postscript]
Abstract: Many search domains are nondeterministic. Although
realtime search methods have traditionally been studied in deterministic
domains, they are wll suited for searching nondeterministic domains
since they do not have to plan for every contingency  they can react
to the actual outcomes of actions. In this paper, we introduce the
minmax LRTA* algorithm, a simple extension of Korf's Learning
RealTime A* algorithm [...]
Sven Koenig and
Reid Simmons

Easy and Hard Testbeds for RealTime Search Algorithms
 [Gzipped postscript]
Abstract: Although researchers have studied which factors
influence the behavior of traditional search algorithms, currently
not much is known about how domain properties influence the performance
of realtime search algorithms. In this paper we demonstrate, both
theoretically and experimentally, that Eulerian state spaces (a
superset of undirected state spaces) are very easy for some existing
realtime search algorithms to solve [...] Because traditional
realtime search testbeds (such as the eight puzzle and gridworlds)
are Eulerian, they cannot be used to distinguish between efficient
and inefficient realtime search algorithms. It follows that one
has to use nonEulerian domains to demonstrate the general superiority
of a given algorithm. To this end, we present two classes of
hardtosearch state spaces and demonstrate the performance of
various realtime search algorithms on them.
Sven Koenig and
Reid Simmons

New Approaches to Moving Target Search
 [Gzipped postscript]
Abstract: New methods for doing moving target search
are presented. One algorithm, forgetful depthfirst search,
attempts to adampt the wellknown depthfirst algorithm to this
problem domain. Also, a search technique called marking quickly
acquires general knowledge about the search space. These methods
are discussed and compared with other known methods. Experimental
results show that forgetful depthfirst search and marking give
good performance.
Stan Melax

The Trailblazer Search with a Hierarchical Abstract Map
 [Compressed postscript]
Abstract: We deal with the moving target search problem
where the location of the goal may change during the search process.
The Trailblazer Search achieves a systematic and effective search by
maintaining a map. The map stores path information about the region
where the algorithm has already searched through. However, because
of the growth of the map, there is a problem that the time to make
decisions of search steps increases rapidly. We propose an algorithm,
the Trailblazer Search with Abstract Map, that reduces the cost of
map maintenance of the local maps [...]
Takahiro Sasaki,
Fumihiko Chimura, and
Mario Tokoro

Kinetic collision detection for two simple polygons
 ...
Jeff Ericson,
Julien Basch,
Leonidas Guibas,
John Hershberger, and
Li Zhang

LinCanny Closest Features Algorithm
 The original algorithm for ICollide (see below.)
Ming Chieh Lin and
John F. Canny

Interactive and Exact Collision Detection for Virtual and Simulated
Environments

Collision Detection and Contact Determination
Several good articles on collision detection. They obtain execution
times close to O(n), rather than the usual O(n^2).
Maintained by Dinesh
Manocha

Efficient Collision Detection for Realtime Simulated Environments
 [Gzipped postscript]
Paul Dworkin
 "Robot Motion Planning"
 by
JeanClaude Latombe
Kluwer Academic Publishers, 1991
ISBN 0792391292 (alk. paper)
 "Computational Geometry in C"
 by
Joseph O'Rourke
Cambridge University Press, 1993
ISBN 0521440343 hardback
ISBN 0521445922 paperback
 "Heuristics : intelligent search strategies for computer problem
solving"
 by
Judea Pearl
AddisonWesley, 1984
ISBN 0201055945

Robotics Internet Resources Page
 Huge collection of links to other robotics pages
 Geometry

Directory of Computational Geometry Software

Geometry Formulas and Facts

Geometry in Action  Robot Motion Planning

The Game Programming Page

Artificial Intelligence in Games
 Steven Woodcock's excellent collection about AI in games

Machine Learning in Games

The Artificial Life Games Homepage

Characters, improvisations, and...
 A large number of links to autonomous characters maintained by Craig
Reynolds

Excalibur  Home Page
 Adaptive Constraintbased Agents in Artificial Environments

Priority Queues
 An impressive collection of papers on priority queues
Last modified: Tue Nov 17 11:47:07 MET 1998
Bjørn Reese
<breese@imada.ou.dk>
Archivist (since Feb 18, 1999): Craig Reynolds
<cwr@red.com>