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.
-
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
-
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
- 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
-
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
-
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).
Maintained by Dinesh
Manocha
-
Efficient Collision Detection for Real-time Simulated Environments
- [Gzipped postscript]
Paul Dworkin
- "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
-
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 Constraint-based 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>