Geometric Representations and Transformations (2009)
This chapter provides important background material that will be needed for Part II. Formulating and solving motion planning problems require defining and manipulating complicated geometric models of...
Sequential Decision Theory (2009)
Chapter 9 essentially took a break from planning by indicating how to make a single decision in the presence of uncertainty. In this chapter, we return to planning by formulating a sequence of...
I-Bug: An Intensity-Based Bug Algorithm (2009)
Kamilah Taylor, Steven M. Lavalle
Abstract — This paper introduces a sensor-based planning algorithm that uses less sensing information than any others within the family of bug algorithms. The robot is unable to access precise...
Planning Under Sensing Uncertainty (2009)
The main purpose of Chapter 11 was to introduce information space (I-space) concepts and to provide illustrative examples that aid in understanding. This chapter addresses planning under sensing...
Survivability: Measuring and Ensuring Path Diversity (2009)
Lawrence H. Erickson, Steven M. Lavalle
Abstract — A novel criterion is introduced for assessing the diversity of a collection of paths or trajectories. The main idea is the notion of survivability, which measures the likelihood that...
Feedback Motion Planning (2009)
So far in Part II it has been assumed that a continuous path sufficiently solves a motion planning problem. In many applications, such as computer-generated animation and virtual prototyping, there...
Motion Planning for Highly Constrained Spaces (2009)
Anna Yershova, Steven M. Lavalle
Abstract — We introduce a sampling-based motion planning method that automatically adapts to the difficulties caused by thin regions in the free space (not necessarily narrow corridors). These...
Rendezvous without Coordinates (2009)
Jingjin Yu, Steven M. Lavalle, Daniel Liberzon
Abstract — We study minimalism in sensing and control by considering a multi-agent system in which each agent moves like a Dubins car and has a limited sensor that reports only the presence of...
Up until now it has been assumed everywhere that the current state is known. What if the state is not known? In this case, information regarding the state is obtained from sensors during the...
Generating Uniform Incremental Grids on SO(3) Using the Hopf Fibration (2009)
Anna Yershova, Steven M. Lavalle, Julie C. Mitchell
Abstract. The problem of generating uniform deterministic samples over the rotation group, SO(3), is fundamental to many fields, such as computational structural biology, robotics, computer graphics,...
Chapter 5 Motion Planning (2009)
Lydia E. Kavraki, Steven M. Lavalle
A fundamental robotics task is to plan collision-free motions for complex bodies from a start to a goal position among a collection of static obstacles. Although relative simple, this geometric path...
This chapter serves as a building block for modeling and solving planning problems that involve more than one decision maker. The focus is on making a single decision in the presence of other...
The Configuration Space (2009)
Chapter 3 only covered how to model and transform a collection of bodies; however, for the purposes of planning it is important to define the state space. The state space for motion planning is a set...
This chapter provides introductory concepts that serve as an entry point into other parts of the book. The planning problems considered here are the simplest to describe because the state space will...
Chapter 6 Combinatorial Motion Planning (2009)
Reasons to study combinatorial methods There are generally two good reasons to study combinatorial approaches to motion planning: Chapter 6 Combinatorial Motion Planning Combinatorial approaches to...
System Theory and Analytical Techniques (2009)
This chapter is complementary to Chapter 14 in that it provides tools and concepts that can be used to develop better local planning methods (LPMs). Most of the material was developed in the field of...
Part I Introductory Material (2009)
1.1 Planning to Plan Planning is a term that means different things to different groups of people. Robotics addresses the automation of mechanical systems that have sensing, actuation, and...
Part IV is a continuation of Part II. It is generally not necessary to read Part
Part II Motion Planning (2009)
Part II makes the transition from discrete to continuous state spaces. Two alternative titles are appropriate for this part: 1) motion planning, or 2) planning in continuous state spaces. Chapters...
In this section, it will be assumed that X = C, which is a C-space of one or more rigid bodies, as defined in Section 4.2. Differential models in this section are all expressed as constraints on the...
Extensions of Basic Motion Planning (2009)
This chapter presents many extensions and variations of the motion planning problem considered in Chapters 3 to 6. Each one of these can be considered as a “spin-off ” that is fairly...
Decision-Theoretic Planning Planning Under Uncertainty (2009)
called decision-theoretic planning, but it can also be considered as planning under uncertainty. All of the concepts in Parts I and II avoided models of uncertainties. Chapter 8 considered plans that...
Part II makes the transition from discrete to continuous state spaces. Two alternative titles are appropriate for this part: 1) motion planning, or 2) planning in continuous state spaces. Chapters...
Leonidas J. Guibas, Jean-claude Latombe, Steven M. Lavalle, David Lin, Rajeev Motwani
This paper addresses the problem of planning the motion of one or more pursuers in a polygonal environment to eventually \see " an evader that is unpredictable, has unknown initial position,...
Benjamín Tovar, Luigi Freda, Steven M. Lavalle
Abstract. This paper considers a robot that moves in the plane and is only able to sense the cyclic order of landmarks with respect to its current position. No metric information is available...
Extensions of Basic Motion Planning (2009)
This chapter presents many extensions and variations of the motion planning problem considered in Chapters 3 to 6. Each one of these can be considered as a “spin-off ” that is fairly...
Learning Combinatorial Information from Alignments of Landmarks (2008)
Luigi Freda, Benjamín Tovar, Steven M. Lavalle
Abstract — This paper characterizes the information space of a robot moving in the plane with limited sensing. The robot has a landmark detector, which provides the cyclic order of the landmarks...
This chapter provides a continuous-time counterpart to the state transition equation, xk+1 = f(xk,uk), which was crucial in Chapter 2. On a continuous state space, X (assumed to be a smooth...
Decision-Theoretic Planning Planning Under Uncertainty (2008)
called decision-theoretic planning, but it can also be considered as planning under uncertainty. All of the concepts in Parts I and II avoided models of uncertainties. Chapter 8 considered plans that...
1 On the Relationship Between Classical Grid Search and Probabilistic Roadmaps (2008)
Steven M. Lavalle, Michael S. Branicky
Abstract. We present, implement, and analyze a spectrum of closely-related planners, designed to gain insight into the relationship between classical grid search and probabilistic roadmaps (PRMs)....
History A Kinematics-Based Probabilistic Roadmap Method for Closed (2008)
Closed Kinematic Chains, Steven M. Lavalle, Jeffery H. Yakey, Lydia E. Kavraki, Kinematic Chains, Steven M. Lavalle, ...
This extension to the LaValle paper from Amato’s lab provided speed enhancements sufficient to make the earlier techniques practical. The Saga Continues… In Yogi’s presentation, we saw Computer...
This chapter provides introductory concepts that serve as an entry point into other parts of the book. The planning problems considered here are the simplest to describe because the state space will...
Visibility-Based Pursuit-Evasion with Bounded (2008)
Benjamín Tovar, Steven M. Lavalle
Summary. This paper presents an algorithm for a visibility-based pursuit-evasion problem in which bounds on the speeds of the pursuer and evader are given. The pursuer tries to find the evader inside...
Sensors and Information Spaces (2008)
Up until now it has been assumed everywhere that the current state is known. What if the state is not known? In this case, information regarding the state is obtained from sensors during the...
Sampling-Based Planning Under Differential Constraints (2008)
After Chapter 13, it seems that differential constraints arise nearly everywhere. For example, they may arise when wheels roll, aircraft fly, and when the dynamics of virtually any mechanical system...
On comparing the power of robots (2008)
Jason M. O’kane, Steven M. Lavalle
Robots must complete their tasks in spite of unreliable actuators and limited, noisy sensing. In this paper, we consider the information requirements of such tasks. What sensing and actuation...
Published by Cambridge University Press Chapter 5 Sampling-Based Motion Planning (2008)
There are two main philosophies for addressing the motion planning problem, in Formulation 4.1 from Section 4.3.1. This chapter presents one of the philosophies, sampling-based motion planning, which...
System Theory and Analytical Techniques (2008)
This chapter is complementary to Chapter 14 in that it provides tools and concepts that can be used to develop better local planning methods (LPMs). Most of the material was developed in the field of...
Extracting Visibility Information by Following (2008)
Anna Yershova, Benjamín Tovar, Steven M. Lavalle
Summary. This paper presents an analysis of a simple robot model, called Bitbot. The Bitbot has limited capabilities; it can reliably follow walls and sense a contact with a wall. Although the Bitbot...
Jason M. O'kane, Steven M. Lavalle, Steven M. Lavalle
Robots must complete their tasks in spite of unreliable actuators and limited, noisy sensing. In this paper, we consider the information requirements of such tasks. What sensing and actuation...
Steven M. Lavalle, Michael S. Branicky, Stephen R. Lindemann, Steven M. Lavalle, Michael S. Branicky, Stephen R. Lindemann
We present, implement, and analyze a spectrum of closely-related planners, designed to gain insight into the relationship between classical grid search and probabilistic roadmaps (PRMs). Building on...
The Configuration Space (2008)
Chapter 3 only covered how to model and transform a collection of bodies; however, for the purposes of planning it is important to define the state space. The state space for motion planning is a set...
Robert Ghrist, Jason M. O'kane, Steven M. Lavalle, Robert Ghrist, Jason M. O’kane, Steven M. Lavalle
We consider the coordination of multiple robots in a common environment, each robot having its own (distinct) roadmap. Our primary contribution is a classification of and exact algorithm for...
Steven M. Lavalle, James J. Kuffner, Steven M. Lavalle, James J. Kuffner
This paper presents the first randomized approach to kinodynamic planning (also known as trajectory planning or trajectory design). The task is to determine control inputs to drive a robot from an...
Shai Sachs, Steven M. Lavalle, Stjepan Rajko, Shai Sachs, Steven M. Lavalle, Stjepan Rajko
We address an on-line version of the visibility-based pursuit-evasion problem. We take a minimalist approach in modeling the capabilities of a pursuer robot. A point pursuer moves in an unknown,...
Steven M. Lavalle, Prashanth Konkimalla, Steven M. Lavalle, Prashanth Konkimalla
The authors address the problem of computing a navigation function that serves as a feedback motion strategy for problems that involve generic differential constraints, nonconvex collision...
Sequential Decision Theory (2008)
Chapter 9 essentially took a break from planning by indicating how to make a single decision in the presence of uncertainty. In this chapter, we return to planning by formulating a sequence of...
Visibility-Based Pursuit-Evasion with Bounded (2008)
Benjamín Tovar, Steven M. Lavalle
Summary. This paper presents an algorithm for a visibility-based pursuit-evasion problem in which bounds on the speeds of the pursuer and evader are given. The pursuer tries to find the evader inside...
Benjamín Tovar, Rafael Murrieta-cid, Steven M. Lavalle
Abstract — This paper considers what can be accomplished using a mobile robot that has limited sensing. For navigation and mapping, the robot has only one sensor, which tracks the directions of...
Benjamin Tovar, Steven M. Lavalle, Rafael Murrieta, Beckman Institue
Abstract — In this paper we present an algorithm to build a sensor-based, dynamic data structure useful for robot navigation in an unknown, multiply-connected planar environment. This data...
On comparing the power of robots (2008)
Jason M. O’kane, Steven M. Lavalle
Robots must complete their tasks in spite of unreliable actuators and limited, noisy sensing. In this paper, we consider the information requirements of such tasks. What sensing and actuation...
Abstract An Improved Random Neighborhood Graph Approach (2008)
As a general framework to determine a collision-free feedback motion strategies, the Random Neighborhood Graph (RNG) approach [19] defines a global navigation function over an approximate...
Probabilistic localization with a blind robot (2008)
Lawrence H. Erickson, Joseph Knuth, Jason M. O’kane, Steven M. Lavalle
Abstract — Researchers have addressed the localization problem for mobile robots using many different kinds of sensors, including rangefinders, cameras, and odometers. In this paper, we consider...
Abstract Efficient Nearest Neighbor Searching for Motion Planning (2008)
Anna Atramentov, Steven M. Lavalle
We present and implement an efficient algorithm for performing nearest-neighbor queries in topological spaces that usually arise in the context of motion planning. Our approach extends the Kd...
Benjamín Tovar, Luigi Freda, Steven M. Lavalle
Abstract. This paper considers a robot that moves in the plane and is only able to sense the cyclic order of landmarks with respect to its current position. No metric information is available...
Learning Combinatorial Information from Alignments of Landmarks (2008)
Luigi Freda, Benjamín Tovar, Steven M. Lavalle
Abstract — This paper characterizes the information space of a robot moving in the plane with limited sensing. The robot has a landmark detector, which provides the cyclic order of the landmarks...
1 On the Relationship Between Classical Grid Search and Probabilistic Roadmaps (2008)
Steven M. Lavalle, Michael S. Branicky
Abstract. We present, implement, and analyze a spectrum of closely-related planners, designed to gain insight into the relationship between classical grid search and probabilistic roadmaps (PRMs)....
Locally-Optimal Navigation in Multiply-Connected Environments (2008)
Without Geometric Maps, Benjamin Tovar, Steven M. Lavalle, Rafael Murrieta, Beckman Institue
In this paper we present an algorithm to build a sensor-based, dynamic data structure useful for robot navigation in an unknown, multiply-connected planar environment. This data structure offers a...
Combinatorial Motion Planning (2008)
Of Illinois Copyright, Steven M. Lavalle
this technically is not permitted, but the algorithm nevertheless correctly decides whether a solution path exists ). i i that have zero signs can be put together sequentially to produce a mapping
Representations and Transformations Steven M. (2008)
Copyright Steven Lavalle, Steven M. Lavalle
e. Both alternatives will be considered in this section. 1) a 2D world, in and 2) a 3D world, in . These 81 allow more complicated worlds, such as the surface of a sphere or even a higher dimensional...
Feedback Motion Planning (2008)
Of Illinois Copyright, Steven M. Lavalle
ion space as considered in Chapter 4. Two general ways to model uncertainty in the predictability of future states 1. Explicitly: models that explicitly account for the possible ways 369 Open Loop...
On the Relationship Between Classical (2008)
Grid Search And, Steven M. Lavalle, Michael S. Branicky
We present, implement, and analyze a spectrum of closely-related planners, designed to gain insight into the relationship between classical grid search and probabilistic roadmaps (PRMs). Building on...
Motion Planning Steven M. (2008)
Of Illinois Copyright, Steven M. Lavalle
this technicality has no practical implications; however, not very large, then it might be frustrating to obtain only probabilistic assurances, as opposed to absolute guarantees of coverage. The next...
Of Illinois Copyright, Steven M. Lavalle
ich means that a robot must use sensing information to determine its location. This is essentially a matter of maintaining derived I-states and comlocalization to problems in which the robot does not...
Of Illinois Copyright, Steven M. Lavalle
nterest. This leads which all decision makers (including the robot) can be players. 9.1 provides some basic review and perspective that will help in undersingle decision under uncertainty, which is...
Of Illinois Copyright, Steven M. Lavalle
rts are termed "problem-solving" and "planning"; however, their definitions are quite similar. The problem-solving part begins by stating, "Problem solving agents decide what...
Renato Feres, Volkan Isler, Steven M. Lavalle, Chenyang Lu, Robert Pless, Gruia-catalin Roman, ...
Autonomous robot coordination has several real-world applications where effective usage of robots can provide significant increase in efficiency, reduction in cost and higher security for people....
Sensor Beams, Obstacles, and Possible Paths (2008)
Benjamin Tovar, Fred Cohen, Steven M. Lavalle
Summary. This paper introduces a problem in which an agent (robot, human, or animal) travels among obstacles and binary detection beams. The task is to determine the possible agent path based only on...
Abstract Efficient Nearest Neighbor Searching for Motion Planning (2007)
Anna Atramentov, Steven M. Lavalle
We present and implement an efficient algorithm for performing nearest-neighbor queries in topological spaces that usually arise in the context of motion planning. Our approach extends the Kd...
Steven M. Lavalle, Paul W. Finn, Lydia E. Kavraki, Jean-claude Latombe
Computational tools have greatly expedited the pharmaceutical drug design process in recent years. One common task in this process is the search of a large library for small molecules that can...
Localization with limited sensing (2007)
Jason M. O’kane, Steven M. Lavalle
Abstract — Localization is a fundamental problem for many kinds of mobile robots. Sensor systems of varying ability have been proposed and successfully used to solve the problem. This paper probes...
On time: Clocks, chronometers, and open-loop control (2007)
Steven M. Lavalle, Magnus B. Egerstedt
Abstract — This paper addresses the peculiar treatment that time receives when studying control systems. For example, why is the ability to perfectly observe time assumed implicitly in virtually...
Localization with limited sensing (2007)
Jason M. O’kane, Steven M. Lavalle
Abstract — Localization is a fundamental problem for many kinds of mobile robots. Sensor systems of varying ability have been proposed and successfully used to solve the problem. This paper probes...
Mapping and navigation from permutations of landmarks (2007)
Benjamín Tovar, Luigi Freda, Steven M. Lavalle
This paper considers a robot that moves in the plane and is only able to sense the cyclic order of landmarks with respect to its current position. No metric information (e.g., coordinates) is...
Distance-optimal navigation in an unknown environment without sensing distances (2007)
Benjamín Tovar, Rafael Murrieta-cid, Steven M. Lavalle
Abstract — This paper considers what can be accomplished using a mobile robot that has limited sensing. For navigation and mapping, the robot has only one sensor, which tracks the directions of...
Extracting Visibility Information by Following Walls (2007)
Yershova, Anna, Tovar, Benjamin, LaValle, Steven M.
This paper presents an analysis of a simple robot model, called Bitbot. The Bitbot has limited capabilities; it can reliably follow walls and sense a contact with a wall. Although the Bitbot does not...
Real time feedback control for nonholonomic mobile robots with obstacles (2006)
Stephen R. Lindemann, Islam I. Hussein, Steven M. Lavalle
Abstract — We introduce a method for constructing smooth feedback laws for a nonholonomic robot in a 2-dimensional polygonal workspace. First, we compute a smooth feedback law in the workspace...
An explicit characterization of minimum wheel-rotation paths for differential-drives (2006)
Hamidreza Chitsaz, Steven M. Lavalle, Devin J. Balkcom, T. Mason
Summary. This paper presents characterization of shortest paths for differentialdrive mobile robots with classifying solutions in the spirit of Dubins curves and Reeds-Shepp curves for car-like...
Minimum wheel-rotation paths for differential-drive mobile robots (2006)
Hamidreza Chitsaz, Steven M. Lavalle
Abstract — Characterizing optimal paths for mobile robots is an interesting, important, and challenging endeavor. Not only they are interesting with respect to the optimized criteria, but also they...
Minimum wheel-rotation paths for differential-drive mobile robots (2006)
Hamidreza Chitsaz, Steven M. Lavalle, Devin J. Balkcom, Matthew T. Mason
The shortest paths for a mobile robot are a fundamental property of the mechanism, and may also be used as a family of primitives for motion planning in the presence of obstacles. This paper...
An explicit characterization of minimum wheel-rotation paths for differential-drives (2006)
Hamidreza Chitsaz, Steven M. Lavalle, Devin J. Balkcom, Matthew T. Mason
Abstract — This paper characterizes shortest paths for differential-drive mobile robots by classifying solutions in the spirit of Dubins curves and Reeds-Shepp curves for car-like robots. Not only...
Sampling-Based Motion Planning (2006)
There are two main philosophies for addressing the motion planning problem, in Formulation 4.1 from Section 4.3.1. This chapter presents one of the philosophies, sampling-based motion planning, which...
Sampling-Based Motion Planning with Differential Constraints (2005)
Since differential constraints which restrict admissible velocities and accelerations of robotic systems are ignored in path planning, solutions for kinodynamic and non-holonomic planning problems...
Algorithms for Planning under Uncertainty in Prediction and Sensing (2005)
Jason M. O'Kane, Jason M. O’kane, Benjamin Tovar, Peng Cheng, Steven M. Lavalle
Introduction and Preliminaries For mobile robots, uncertainty is everywhere. Wheels slip. Sensors are a#ected by noise. Obstacles move unpredictably. Truly autonomous robots (and decision-makers or...
Information spaces for mobile robots (2005)
Benjamín Tovar, Anna Yershova, Jason M. O’kane, Steven M. Lavalle
Planning with sensing uncertainty is central to robotics. Sensor limitations often prevent accurate state estimation of the robot. Two general approaches can be taken for solving robotics tasks given...
Algorithms for planning under uncertainty in prediction and sensing (2005)
Jason M. O’kane, Benjamín Tovar, Peng Cheng, Steven M. Lavalle
For mobile robots, uncertainty is everywhere. Wheels slip. Sensors are affected by noise. Obstacles move unpredictably. Truly autonomous robots (and decision-makers or agents in general) must act in...
Bitbots: Simple robots solving complex tasks (2005)
Anna Yershova, Benjamín Tovar, Robert Ghrist, Steven M. Lavalle
Sensing uncertainty is a central issue in robotics. Sensor limitations often prevent accurate state estimation, and robots find themselves confronted with a complicated information (belief) space. In...
c ○ World Scientific Publishing Company Clearing a Polygon with Two 1-searchers ∗ (2005)
Borislav H. Simov, Giora Slutzki, Steven M. Lavalle
We present an algorithm for a pair of pursuers, each with one flashlight, searching for an unpredictable, moving target in a 2D environment (simple polygon). Given a polygon with n edges and m...
Exact Pareto-optimal coordination of two translating polygonal robots on an acyclic roadmap (2004)
Hamidreza Chitsaz, Jason M. O’kane, Steven M. Lavalle
Abstract — We present an algorithm that computes the complete set of Pareto-optimal coordination strategies for two translating polygonal robots in the plane. A collision-free acyclic roadmap of...
Incremental grid sampling strategies in robotics (2004)
Stephen R. Lindemann, Anna Yershova, Steven M. Lavalle
Abstract. We present algorithms for generating deterministic sample sequences using incremental grid-based sampling. Our algorithms are designed to generate dense sample sequences over spaces common...
Peng Cheng, Emilio Frazzoli, Steven M. Lavalle
Abstract — Although sampling-based planning algorithms have been extensively used to approximately solve motion planning problems with differential constraints, gaps usually appear in their...
Visibility-based pursuit-evasion in an unknown planar environment (2004)
Shai Sachs, Stjepan Rajko, Steven M. Lavalle
We address an on-line version of the visibility-based pursuit-evasion problem. We take a minimalist approach in modeling the capabilities of a pursuer robot. A point pursuer moves in an unknown,...
On the Relationship Between Classical Grid Search and Probabilistic Roadmaps (2004)
Steven M. LaValle, Michael S. Branicky, Stephen R. Lindemann
We present, implement, and analyze a spectrum of closely-related planners, designed to gain insight into the relationship between classical grid search and probabilistic roadmaps (PRMs). Building on...
Incremental grid sampling strategies in robotics (2004)
Stephen R. Lindemann, Anna Yershova, Steven M. Lavalle
Summary. We present algorithms for generating deterministic sample sequences using incremental grid-based sampling. Our algorithms are designed to generate dense sample sequences over spaces common...
Deterministic Sampling Methods for Spheres and SO(3) (2004)
Anna Yershova, Steven M. LaValle
This paper addresses the problem of generating uniform deterministic samples over the spheres and the three-dimensional rotation group, SO(3). The target applications include motion planning,...
Incremental Grid Sampling Strategies in Robotics (2004)
Stephen R. Lindemann, Anna Yershova, Steven M. Lavalle
We present algorithms for generating deterministic sample sequences using incremental grid-based sampling. Our algorithms are designed to generate dense sample sequences over spaces common in...
Exact Pareto-Optimal Coordination of Two Translating Polygonal Robots on an Acyclic Roadmap (2004)
Hamidreza Chitsaz, Jason M. O'Kane, Jason M. O’kane, Steven M. Lavalle
We present an algorithm that computes the complete set of Pareto-optimal coordination strategies for two translating polygonal robots in the plane. A collision-free acyclic roadmap of...
Incrementally Reducing Dispersion by Increasing Voronoi Bias in RRTs (2004)
Stephen R. Lindemann, Steven M. LaValle
We discuss theoretical and practical issues related to using Rapidly-Exploring Random Trees (RRTs) to incrementally reduce dispersion in the configuration space. The original RRT planners use...
Gap navigation trees: Minimal representation for visibility-based tasks (2004)
Benjamín Tovar, Luis Guilamo, Steven M. Lavalle
Abstract. In this paper we present our advances in a data structure, the Gap Navigation Tree (GNT), useful for solving different visibility-based robotic tasks in unknown planar environments. We...
Peng Cheng, Emilio Frazzoli, Steven M. Lavalle
Abstract — Although sampling-based planning algorithms have been extensively used to approximately solve motion planning problems with differential constraints, gaps usually appear in their...
Peng Cheng, Emilio Frazzoli, Steven M. Lavalle
Abstract — Although sampling-based planning algorithms have been extensively used to approximately solve motion planning problems with differential constraints, gaps usually appear in their...
Exact Pareto-optimal coordination of two translating polygonal robots on an acyclic roadmap (2004)
Hamidreza Chitsaz, Steven M. Lavalle, Jason M. O’kane
We consider planning optimal collision-free motions of two polygonal robots under translation. Each robot has a reference point that must lie on a given graph, called a roadmap, which is embedded in...
Optimal Navigation and Object Finding (2003)
Without Geometric Maps, Benjamin Tovar, Steven M. Lavalle
In this paper we present a dynamic data structure, useful for robot navigation in an unknown, simplyconnected planar environment. The guiding philosophy in this work is to avoid traditional problems...
Optimal Navigation and Object Finding (2003)
Without Geometric Maps, Benjamin Tovar, Steven M. Lavalle
In this paper we present a dynamic data structure, useful for robot navigation in an unknown, simplyconnected planar environment. The guiding philosophy in this work is to avoid traditional problems...
Incremental Low-Discrepancy Lattice Methods for Motion Planning (2003)
Stephen R. Lindemann, Steven M. LaValle
We present deterministic sequences for use in sampling-based approaches to motion planning. They simultaneously combine the qualities found in many other sequences: i) the incremental and...
Locally-Optimal Navigation in Multiply-Connected Environments without Geometric Maps (2003)
Benjamin Tovar, Steven M. LaValle, Rafael Murrieta
In this paper we present an algorithm to build a sensor-based, dynamic data structure useful for robot navigation in an unknown, multiply-connected planar environment. This data structure offers a...
Borislav H. Simov, Steven M. Lavalle, Giora Slutzki
We present an algorithm for a pair of pursuers, each with one flashlight, searching for an unpredictable, moving target in a 2D environment (simple polygon). Given a polygon with n edges, the...
Optimal navigation and object finding without geometric maps or localization (2003)
Benjamin Tovar, Steven M. Lavalle
In this paper we present a dynamic data structure, useful for robot navigation in an unknown, simplyconnected planar environment. The guiding philosophy in this work is to avoid traditional problems...
Exploiting group symmetries to improve precision in kinodynamic and nonholonomic planning (2003)
Peng Cheng, Emilio Frazzoli, Steven M. Lavalle
We address the problem of eliminating gaps in paths that are constructed by some nonholonomic and kinodynamic motion planning algorithms. In many of these algorithms, control inputs at each planning...
From dynamic programming to RRTs: Algorithmic design of feasible trajectories (2002)
Abstract. This paper summarizes our recent development of algorithms that construct feasible trajectories for problems that involve both differential constraints (typically in the form of an...
Deterministic vs. Probabilistic Roadmaps (2002)
Michael S. Branicky, Steven M. Lavalle, Kari Olson, Libo Yang
Within the popular probabilistic roadmap (PRM) framework for motion planning, we challenge the use of randomization. By applying quasi-random sampling techniques, we illustrate both experimental and...
From Dynamic Programming to RRTs: Algorithmic Design of Feasible Trajectories (2002)
This paper summarizes our recent development of algorithms that construct feasible trajectories for problems that involve both di#erential constraints (typically in the form of an underactuated...
An Improved Random Neighborhood Graph Approach (2002)
Libo Yang Steven, Steven M. Lavalle
As a general framework to determine a collision-free feedback motion strategies, the Random Neighborhood Graph (RNG) approach [19] defines a global navigation function over an approximate...
A Complete Pursuit-Evasion Algorithm for Two Pursuers Using Beam Detection (2002)
Borislav H. Simov, Steven M. Lavalle, Giora Slutzki
We present an algorithm for a pair of pursuers, each with one rotating beam (flashlight, laser or a camera), searching for an unpredictable, moving target in a 2D environment (simple polygon). Given...
On the Relationship between Classical Grid Search and Probabilistic Roadmaps (2002)
Steven M. LaValle, Michael S. Branicky
We present, implement, and analyze a spectrum of closely-related planners, designed to gain insight into the relationship between classical grid search and probabilistic roadmaps (PRMs). Building on...
Quasi-randomized path planning (2001)
Michael S. Branicky, Steven M. Lavalle, Kari Olson, Libo Yang
We propose the use of quasi-random sampling techniques for path planning in high-dimensional conguration spaces. Following similar trends from related numerical computation elds, we show several...
1
1
A framework for planning feedback motion strategies based on a random neighborhood graph (2000)
Randomized techniques have led to the development of many successful algorithms for path planning in high-dimensional configuration spaces. This paper presents a randomized framework for computing...
RRT-Connect: An efficient approach to single-query path planning (2000)
James J. Kuffner Jr., Steven M. Lavalle
A simple and efficient randomized algorithm is presented for solving single-query path planning problems in high-dimensional configuration spaces. The method works by incrementally building two...
RRT-connect: An efficient approach to single-query path planning (2000)
James J. Kuffner Jr., Steven M. Lavalle
A simple and efficient randomized algorithm is presented for solving single-query path planning problems in high-dimensional conguration spaces. The method works by incrementally building two...
Using Randomization to Find and Optimize Feasible Trajectories for Nonlinear Systems (2000)
Peng Cheng, Zuojun Shen, Steven M. Lavalle
We present our current progress on the design and experimentation with trajectory planning and optimization algorithms for nonlinear systems that have signicant state-space constraints. An overview...
Steven M. Lavalle, Paul W. Finn, Lydia E. Kavraki, Jean-Claude Latombe
: Computational tools have greatly expedited the pharmaceutical drug design process in recent years. One common task in this process is the search of a large library for small molecules that can...
Pursuit-Evasion Using Beam Detection (2000)
Borislav H. Simov, Giora Slutzki, Steven M. Lavalle
We present an algorithm for searching a 2D environment for unpredictable moving targets using only beambased detection. One or more pursuers move along the environment boundary, and carry a rotating...
Rapidly-Exploring Random Trees: Progress and Prospects (2000)
Steven M. Lavalle, James J. Kuffner
this paper, which presents randomized, algorithmic techniques for path planning that are particular suited for problems that involve dierential constraints.
An Algorithm for Searching a Polygonal Region with a Flashlight (2000)
Steven M. Lavalle, Borislav Simov, Giora Slutzki
We present an algorithm for a single pursuer with one ashlight that searches for an unpredictable, moving target with unbounded speed in a polygonal environment. The algorithm decides whether a...
Paul W. Finn, Lydia E. Kavraki, Jean-claude Latombe, Steven M. Lavalle, Steven M. Lavalle
Computational tools have greatly expedited the pharmaceutical drug design process in recent years. One common task in this process is the search of a large library for small molecules that can...
An Algorithm for Searching a Polygonal Region with a Flashlight (2000)
Steven M. Lavalle, Borislav H. Simov, Giora Slutzki
We present an algorithm for a single pursuer with one ashlight searching for an unpredictable, moving target in a 2D environment. For a simple polygon with n edges, the algorithm uses O(n 2 ) time to...
A Framework for Planning Feedback Motion Strategies Based on a Random Neighborhood Graph (2000)
Randomized techniques have led to the development of many successful algorithms for path planning in high-dimensional conguration spaces. This paper presents a randomized framework for computing...
Pursuit-Evasion Using Beam Detection (2000)
Borislav Simov, Giora Slutzki, Steven M. Lavalle
We present an algorithm for searching a 2D environment for unpredictable moving targets using only beam-based detection. One or more pursuers move along the environment boundary, and carry a rotating...
RRT-connect: An efficient approach to single-query path planning (2000)
James J. Kuffner Jr., Steven M. Lavalle
A simple and efficient randomized algorithm is presented for solving single-query path planning problems in high-dimensional configuration spaces. The method works by incrementally building two...
An Algorithm for Searching a Polygonal Region with a Flashlight (2000)
Steven M. Lavalle, Borislav H. Simov
We present an algorithm for a single pursuer with one ashlight searching for an unpredictable, moving target in a 2D environment. The algorithm decides whether a simple polygon with n edges and m...
Using Randomization to Find and Optimize Feasible Trajectories for Nonlinear Systems (2000)
Peng Cheng, Zuojun Shen, Steven M. Lavalle
Abstract We present our current progress on the design and experimentation with trajectory planning and optimization algorithms for nonlinear systems that have significant state-space constraints. An...
A Probabilistic Roadmap Approach for Systems with Closed Kinematic Chains (1999)
Steven M. Lavalle, Jeffery H. Yakey
We present a randomized approach to path planning for articulated robots that have closed kinematic chains. The approach extends the probabilistic roadmap tech-nique which has previously been applied...
Efficient computation of optimal navigation functions for nonholonomic planning (1999)
Prashanth Konkimalla, Steven M. Lavalle
We present a fast, numerical approach to computing optimal feedback motion strategies for a nonholonomic robot in a cluttered environment. Although many techniques exist to compute navigation...
A Probabilistic Roadmap Approach for Systems with Closed Kinematic Chains (1999)
Steven M. Lavalle, Jeffery H. Yakey, Lydia E. Kavraki
We present a randomized approach to path planning for articulated robots that have closed kinematic chains. The approach extends the probabilistic roadmap technique which has previously been applied...
Steven M. Lavalle, Paul W. Finn, Lydia E. Kavraki, Jean-claude Latombe
Computational tools have greatly expedited the pharmaceutical drug design process in recent years. One common task in this process is the search of a large library for small molecules that can...
A Visibility-Based Pursuit-Evasion Problem (1999)
Leonidas J. Guibas, Jean-claude Latombe, Steven M. Lavalle, David Lin, Rajeev Motwani
This paper addresses the problem of planning the motion of one or more pursuers in a polygonal environment to eventually "see " an evader that is unpredictable, has unknown initial...
A Probabilistic Roadmap Approach for Systems with Closed Kinematic Chains (1999)
Steven M. LaValle, Jeffery H. Yakey, Lydia E. Kavraki
We present a randomized approach to path planning for articulated robots that have closed kinematic chains. The approach extends the probabilistic roadmap technique which has previously been applied...
Steven M. LaValle, Paul W. Finn, Lydia E. Kavraki, Jean-Claude Latombe
Computational tools have greatly expedited the pharmaceutical drug design process in recent years. One common task in this process is the search of a large library for small molecules that can...
Efficient Computation of Optimal Navigation Functions for Nonholonomic Planning (1999)
Prashanth Konkimalla, Steven M. Lavalle
We present a fast, numerical approach to computing optimal feedback motion strategies for a nonholonomic robot in a cluttered environment. Although many techniques exist to compute navigation...
Randomized Kinodynamic Planning (1999)
Steven M. LaValle, James J. Kuffner
This paper presents a state-space perspective on the kinodynamic planning problem, and introduces a randomized path planning technique that computes collision-free kinodynamic trajectories for high...
Visibility-Based Pursuit-Evasion: The Case of Curved Environments (1999)
Steven M. Lavalle, John E. Hinrichsen
We consider the problem of visually searching for an unpredictable target that can move arbitrarily fast in a simply-connected, curved, two-dimensional environment. A complete algorithm is presented...
Randomized Kinodynamic Planning (1999)
Steven M. LaValle, James J. Kuffner
This paper presents a state-space perspective on the kinodynamic planning problem, and introduces a randomized path planning technique that computes collision-free kinodynamic trajectories for high...
Rapidly-Exploring Random Trees: A New Tool for Path Planning (1998)
We introduce the concept of a Rapidly-exploring Random Tree (RRT) as a randomized data structure that is designed for a broad class of path planning problems. While they share many of the beneficial...
Programming is Writing: Why Student Programs Need to be Carefully Read (1998)
Steven M. LaValle, All Rights Reserved, Gary T. Leavens, Gary T. Leavens, Albert L. Baker, ...
Teaching a student to write computer programs well is much like teaching a student to write English prose well. That is, although a program must be correct in every last detail, achieving correctness...
Numerical Computation of Optimal Navigation Functions on a Simplicial Complex (1998)
This paper presents a general approach to computing optimal feedback motion strategies for a holonomic or nonholonomic robot in a static workspace. The proposed algorithm synthesizes a numerical...
On Motion Planning in Changing, Partially-Predictable Environments (1997)
Steven M. Lavalle, Rajeev Sharma
We present a framework for analyzing and computing motion plans for a robot that operates in an environment that both varies over time and is not completely predictable. We first classify sources of...
Dynamic Programming and Optimal Motion Planning (1997)
this paper can be considered as a general way to approximate solutions that might be sufficient for a particular application, or the approach might at least provide some understanding of the...
Finding an Unpredictable Target in a Workspace with Obstacles (1997)
Steven M. Lavalle, David Lin, Leonidas J. Guibas, Jean-claude Latombe, Rajeev Motwani
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...
Visibility-Based Pursuit-Evasion in a Polygonal Environment (1997)
Leonidas J. Guibas, Jean-claude Latombe, Steven M. Lavalle, David Lin, Rajeev Motwani
This paper addresses the problem of planning the motion of one or more pursuers in a polygonal environment to eventually "see" an evader that is unpredictable, has unknown initial position,...
Motion Strategies for Maintaining Visibility of a Moving Target (1997)
Steven M. Lavalle, Craig Becker, Jean-claude Latombe
We introduce the problem of computing robot motion strategies that maintain visibility of a moving target in a cluttered workspace. Both motion constraints (as considered in standard motion planning)...
Rajeev Sharma, Steven M. Lavalle, Seth Hutchinson
Abstract Gross-motion planning for assembly is commonly considered as a distinct, isolated step between task sequencing/scheduling and fine-motion planning. In this paper we formulate a problem of...
Rajeev Sharma, Steven M. Lavalle, Seth Hutchinson
Gross-motion planning for assembly is commonly considered as a distinct, isolated step between task sequencing/scheduling and fine-motion planning. In this paper we formulate a problem of delivering...
A Visibility-Based Pursuit-Evasion Problem (1996)
Leonidas J. Guibas, Jean-claude Latombe, Steven M. Lavalle, David Lin, Rajeev Motwani
This paper addresses the problem of planning the motion of one or more pursuers in a polygonal environment to eventually "see" an evader that is unpredictable, has unknown initial position,...
Robot Motion Planning: A Game-Theoretic Foundation (1996)
Analysis techniques and algorithms for basic path planning have become quite valuable in a variety of applications such as robotics, virtual prototyping, computer graphics, and computational biology....
A Visibility-Based Pursuit-Evasion Problem (1996)
Leonidas J. Guibas, Jean-claude Latombe, Steven M. Lavalle, David Lin, Rajeev Motwani
This paper presents 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...
Optimal Motion Planning for Multiple Robots Having Independent Goals (1996)
Steven M. Lavalle, Seth A. Hutchinson
This work makes two contributions to geometric motion planning for multiple robots: i) Motion plans are computed that simultaneously optimize an independent performance measure for each robot; ii) A...
In this paper we provide a method for characterizing fu-ture configurations under the implementation of a motion strategy in the presence of sensing and control uncertain-ties. We provide general...
A Framework for Constructing Probability Distributions on the Space of Image Segmentations (1995)
Steven M. Lavalle, Seth A. Hutchinson
The goal of traditional probabilistic approaches to image segmentation has been to derive a single, optimal segmentation, given statistical models for the image formation process. In this paper, we...
Steven M. Lavalle, Kenneth J. Moroney, Seth A. Hutchinson
Numerical computation with Bayesian posterior densities has recently received much attention both in the applied statistics and image processing communities. This paper surveys previous literature...
A Bayesian Segmentation Methodology for Parametric Image Models (1993)
Steven M. Lavalle, Seth A. Hutchinson
Region-based image segmentation methods require some criterion for determining when to merge regions. This paper presents a novel approach by introducing a Bayesian probability of homogeneity in a...
A pursuit-evasion BUG algorithm (1954)
Stjepan Rajko, Steven M. Lavalle
We consider the problem of searching for an unpredictable moving target, using a robot that lacks a map of the environment, lacks the ability to construct a map, and has imperfect navigation ability....
A pursuit-evasion BUG algorithm (1954)
Stjepan Rajko, Steven M. Lavalle
We consider the problem of searching for an unpredictable moving target, using a robot that lacks a map of the environment, lacks the ability to construct a map, and has imperfect navigation ability....