Navigational overview

Recent changes
Navigation - Robotics
Navigation - Games
Heuristic Search
Real-Time 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.

Navigation - Robotics

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, El-Ghazali 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 a-priori 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 place-based, metric representation of space in a-priori unknown environments and to localize itself in a stochastically optimal manner [...]
Karthik Balakrishnan, Olivier Bousquet, and Vasant Honovar
Grid-based 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 cross-country navigator: Abstract:Autonomous Cross-Country 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 free-space 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 All-Terrain 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 two-level 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 contact-based 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, non-holonomic 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
Collision-Free Object Movement Using Vector Fields: Abstract:We present a technique for automatically providing animation and collision avoidance in a general-purpose 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 fixed-base manipulation: the Operational Space Formulation for task-oriented 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 multi-arm 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 Physically-Based 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, Marie-Paule Gascuel, Jean-Dominique Gascuel
Robot Motion Planning: A Game-Theoretic 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ález-Bañoz, Craig Becker and Jean-Claude Latombe
Finding an Unpredictable Target in a Workspace with Obstacles: [Gzipped postscript]
Abstract: This paper introduces a visibility-based 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, Jean-Claude Latombe, and Rajeev Motwani
Behavior-Based Control: Examples from Navigation, Learning, and Group Behavior: [Gzipped postscript]
Abstract:This paper describes the main properties of behavior-based 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 path-finding, 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 real-time sensor-based robot control. An elastic band is a deformable collision-free 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 Vector-Error Path Planner, Distance-Transform Path Planner, Potential Path Following Method, and (Forward and Back propagation) A* Algorithm
Mission Planning and Control

Navigation - Games

An optimal pathfinder for vehicles in real-world 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
Mutton-Robot: 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 life-like 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 computer-game 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 role-playing 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 well-established, 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

Heuristic search: Hill climing, best-first, 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
On-line 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 Sub-Admissibility 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 sub-admissibility [...]
Henri Farreny
Search in Temporal Domains: [Gzipped postscript]
Abstract: Best-first 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 time-dependent. In such a graph, shortest paths are dependent on time at which traversal in the graph begins [...] In this paper, a best-first algorithm is generalized to handle time-dependent 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 Multi-Level Buckets: [Gzipped postscript]
Abstract: A 2-level 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 decrease-key operations in Dijkstra's shortest path algorithm is O(n log(1 + m/n)) for an n-vertex, m-arc graph. The bounds holds for any graph structure [...] This result explains the small number of decrease-key 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 abstraction-induced 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 well-known 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 Best-First of State-Space Graphs: A Summary of Results: [Postscript]
Abstract: This paper presents many different parallel formulations of the A*/Branch-and-Bound 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*/branch-and-bound.
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 maze-routing problems and string matching problems on a proposed reconfigurable mesh architecture [...] Section II presents a number of time-efficient algorithms to solve the maze-routing problem. Maze-routing algorithms are used in VLSI routing and robot path planning. In that section, definitions for absolute shortest path (ASP), shortest duplex-path (SDP), shortest triplex-path (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 [...]
Hsi-Chieh Lee
Time-Varying 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 non-negative 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
Path-Finding 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 Shortest-Path Problem: [Compressed postscript]
Abstract: The grammar problem, a generalization of the single-source shortest-path problem introduced by Knuth, is to compute the minimum-cost derivation of a terminal string from one or more non-terminals of a given context-free 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 single-source shortest-path problem with positive edge lengths. The aspect of our incremental algorithms that distinguishes it from all other work on the dynamic shortest-path 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 Partially-Known 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 Real-Time Replanning: [Postscript]
Abstract: [...] The D* algorithm (Dynamic A*) plans optimal traverses in real-time 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 on-line description
Anthony Stentz

Real-Time Search

Updating Shortest Paths: [Gzipped postscript]
Abstract: Moving target search is a state space approach for finding non-stationary goals. The plot is given by a real-time situation in which the target has to be captured by a so-called 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 Real-Time Heuristic Search: [Gzipped postscript]
Abstract: In contrast to off-line search algorithms such as A* and IDA*, in real-time 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 Real-Time 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 Real-Time Bidirectional Search: [Postscript]
Abstract: This paper investigates real-time bidirectional search algorithms, where two problem solving agents, starting from the initial and goal states, physically move towards each other [...]
Toru Ishida
Real-Time Search in Non-Deterministic Domains: [Gzipped postscript]
Abstract: Many search domains are non-deterministic. Although real-time search methods have traditionally been studied in deterministic domains, they are wll suited for searching non-deterministic 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 min-max LRTA* algorithm, a simple extension of Korf's Learning Real-Time A* algorithm [...]
Sven Koenig and Reid Simmons
Easy and Hard Testbeds for Real-Time 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 real-time 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 real-time search algorithms to solve [...] Because traditional real-time search testbeds (such as the eight puzzle and gridworlds) are Eulerian, they cannot be used to distinguish between efficient and inefficient real-time search algorithms. It follows that one has to use non-Eulerian domains to demonstrate the general superiority of a given algorithm. To this end, we present two classes of hard-to-search state spaces and demonstrate the performance of various real-time 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 depth-first search, attempts to adampt the well-known depth-first 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 depth-first 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

Collision Detection

Kinetic collision detection for two simple polygons

...
Jeff Ericson, Julien Basch, Leonidas Guibas, John Hershberger, and Li Zhang

Lin-Canny Closest Features Algorithm

The original algorithm for I-Collide (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).

I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scaled Environments
[Compressed postscript]
Efficient Collision Detection for Animation and Robotics
[Compressed postscript]

Maintained by Dinesh Manocha

Efficient Collision Detection for Real-time Simulated Environments

[Gzipped postscript]
Paul Dworkin

Publication lists

On-line Computer Science Techreports

Robotics papers and preprints at California Institute of Technology (Caltech)
Barry Brumitt's reseach publications on navigation at Carnegie Mellon University
Dana Nau's Publications on AI Planning at University of Maryland at College Park
Special Issue on Learning Autonomous Robots in IEEE Transactions on Systems, Man, and Cybernetics-Part B, Vol.26, No.3, June 1996.
Publications at Cognitive Robotics at GMD (German National Research Center for Information Technology)
Publications at Robotics and Computer Vision Laboratory, Beckman Institute, University of Illinois
Robot Navigation at the Department of Computer Science, Manchester University
On-line publications at Mobile Robot Laboratory, Georgia Institute of Technology
R.James Firby's publication list at University of Chicago
Publications of Neil Rowe at the Naval Postgraduate School

Books

"Robot Motion Planning": by Jean-Claude Latombe
Kluwer Academic Publishers, 1991
ISBN 0-7923-9129-2 (alk. paper)
"Computational Geometry in C": by Joseph O'Rourke
Cambridge University Press, 1993
ISBN 0-521-44034-3 hardback
ISBN 0-521-44592-2 paperback
"Heuristics : intelligent search strategies for computer problem solving": by Judea Pearl
Addison-Wesley, 1984
ISBN 0-201-05594-5