Lydia E. Kavraki

ICRA Conference 2025 Conference Paper

CaStL: Constraints as Specifications Through Llm Translation for Long-Horizon Task and Motion Planning

• Weihang Guo
• Zachary Kingston
• Lydia E. Kavraki

Large Language Models (LLMs) have demonstrated remarkable ability in long-horizon Task and Motion Planning (TAMP) by translating clear and straightforward natural language problems into formal specifications such as the Planning Domain Definition Language (PDDL). However, real-world problems are often ambiguous and involve many complex constraints. In this paper, we introduce Constraints as Specifications through LLMs (CaStL), a framework that identifies constraints such as goal conditions, action ordering, and action blocking from natural language in multiple stages. CaStL translates these constraints into PDDL and Python scripts, which are then solved using an custom PDDL solver. Tested across three PDDL domains, CaStL significantly improves constraint handling and planning success rates from natural language specification in complex scenarios.

ICRA Conference 2025 Conference Paper

Nearest-Neighbourless Asymptotically Optimal Motion Planning with Fully Connected Informed Trees (FCIT*)

• Tyler S. Wilson
• Wil Thomason
• Zachary Kingston
• Lydia E. Kavraki
• Jonathan D. Gammell

Improving the performance of motion planning algorithms for high-degree-of-freedom robots usually requires reducing the cost or frequency of computationally expensive operations. Traditionally, and especially for asymptotically optimal sampling-based motion planners, the most expensive operations are local motion validation and querying the nearest neighbours of a configuration. Recent advances have significantly reduced the cost of motion validation by using single instruction/multiple data (SIMD) parallelism to improve solution times for satisficing motion planning problems. These advances have not yet been applied to asymptotically optimal motion planning. This paper presents Fully Connected Informed Trees (FCIT*), the first fully connected, informed, anytime almost-surely asymptotically optimal (ASAO) algorithm. FCIT* exploits the radically reduced cost of edge evaluation via SIMD parallelism to build and search fully connected graphs. This removes the need for nearest-neighbours structures, which are a dominant cost for many sampling-based motion planners, and allows it to find initial solutions faster than state-of-the-art ASAO (VAMP, OMPL) and satisficing (OMPL) algorithms on the MotionBenchMaker dataset while converging towards optimal plans in an anytime manner.

ICRA Conference 2024 Conference Paper

Accelerating Long-Horizon Planning with Affordance-Directed Dynamic Grounding of Abstract Strategies

• Khen Elimelech
• Zachary Kingston
• Wil Thomason
• Moshe Y. Vardi
• Lydia E. Kavraki

Long-horizon task planning is important for robot autonomy, especially as a subroutine for frameworks such as Integrated Task and Motion Planning. However, task planning is computationally challenging and struggles to scale to realistic problem settings. We propose to accelerate task planning over an agent’s lifetime by integrating abstract strategies: a generalizable planning experience encoding introduced in earlier work. In this work, we contribute a practical approach to planning with strategies by introducing a novel formalism of planning in a strategy-augmented domain. We also introduce and formulate the notion of a strategy’s affordance, which indicates its predicted benefit to the solution, and use it to guide the planning and strategy grounding processes. Together, our observations yield an affordance-directed, lazy-search planning algorithm, which can seamlessly compose strategies and actions to solve long-horizon planning problems. We evaluate our planner in an object rearrangement domain, where we demonstrate performance benefits relative to a state-of-the-art task planner.

ICRA Conference 2024 Conference Paper

Motions in Microseconds via Vectorized Sampling-Based Planning

• Wil Thomason
• Zachary Kingston
• Lydia E. Kavraki

Modern sampling-based motion planning algorithms typically take between hundreds of milliseconds to dozens of seconds to find collision-free motions for high degree-of-freedom problems. This paper presents performance improvements of more than 500x over the state-of-the-art, bringing planning times into the range of microseconds and solution rates into the range of kilohertz, without specialized hardware. Our key insight is how to exploit fine-grained parallelism within planning, providing generality-preserving algorithmic improvements to any such planner and significantly accelerating critical subroutines, such as forward kinematics and collision checking. We demonstrate our approach over a diverse set of challenging, realistic problems for complex robots ranging from 7 to 14 degrees-of-freedom. Moreover, we show our approach does not require high-power hardware by evaluating on a low-power single-board computer. The planning speeds demonstrated are fast enough to reside in the range of control frequencies and open up new avenues of motion planning research.

IROS Conference 2024 Conference Paper

Robust and Safe Task-Driven Planning and Navigation for Heterogeneous Multi-Robot Teams with Uncertain Dynamics

• Tianyang Pan
• Christos K. Verginis
• Lydia E. Kavraki

Task and motion planning (TAMP) can enhance intelligent multi-robot coordination. TAMP becomes signifi-cantly more complicated in obstacle-cluttered environments and in the presence of robot dynamic uncertainties. We propose a control framework that solves the motion-planning problem for multi-robot teams with uncertain dynamics, addressing a key component of the TAMP pipeline. The principal part of the proposed algorithm constitutes a decentralized feedback control policy for tracking of reference paths taken by the robots while avoiding collision and adapting in real time to the underlying dynamic uncertainties. The proposed framework further leverages sampling-based motion planners to free the robots from local-minimum configurations. Extensive experimental results in complex, realistic environments illustrate the superior efficiency of the proposed approach, in terms of planning time and number of encountered local minima, with respect to state-of-the-art baseline methods.

ICRA Conference 2024 Conference Paper

Stochastic Games for Interactive Manipulation Domains

• Karan Muvvala
• Andrew M. Wells
• Morteza Lahijanian
• Lydia E. Kavraki
• Moshe Y. Vardi

As robots become more prevalent, the complexity of robot-robot, robot-human, and robot-environment interactions increases. In these interactions, a robot needs to consider not only the effects of its own actions, but also the effects of other agents’ actions and the possible interactions between agents. Previous works have considered reactive synthesis, where the human/environment is modeled as a deterministic, adversarial agent; as well as probabilistic synthesis, where the human/environment is modeled via a Markov chain. While they provide strong theoretical frameworks, there are still many aspects of human-robot interaction that cannot be fully expressed and many assumptions that must be made in each model. In this work, we propose stochastic games as a general model for human-robot interaction, which subsumes the expressivity of all previous representations. In addition, it allows us to make fewer modeling assumptions and leads to more natural and powerful models of interaction. We introduce the semantics of this abstraction and show how existing tools can be utilized to synthesize strategies to achieve complex tasks with guarantees. Further, we discuss the current computational limitations and improve the scalability by two orders of magnitude by a new way of constructing models for PRISM-games.

ICRA Conference 2024 Conference Paper

Stochastic Implicit Neural Signed Distance Functions for Safe Motion Planning under Sensing Uncertainty

• Carlos Quintero-Peña
• Wil Thomason
• Zachary Kingston
• Anastasios Kyrillidis
• Lydia E. Kavraki

Motion planning under sensing uncertainty is critical for robots in unstructured environments, to guarantee safety for both the robot and any nearby humans. Most work on planning under uncertainty does not scale to high-dimensional robots such as manipulators, assumes simplified geometry of the robot or environment, or requires per-object knowledge of noise. Instead, we propose a method that directly models sensor-specific aleatoric uncertainty to find safe motions for high-dimensional systems in complex environments, without exact knowledge of environment geometry. We combine a novel implicit neural model of stochastic signed distance functions with a hierarchical optimization-based motion planner to plan low- risk motions without sacrificing path quality. Our method also explicitly bounds the risk of the path, offering trustworthiness. We empirically validate that our method produces safe motions and accurate risk bounds and is safer than baseline approaches.

ICRA Conference 2023 Conference Paper

Efficient Inference of Temporal Task Specifications from Human Demonstrations using Experiment Design

• Shlok Sobti
• Rahul Shome
• Lydia E. Kavraki

Robotic deployments in human environments have motivated the need for autonomous systems to be able to interact with humans and solve tasks effectively. Human demonstrations of tasks can be used to infer underlying task specifications, commonly modeled with temporal logic. State-of-the-art methods have developed Bayesian inference tools to estimate a temporal logic formula from a sequence of demon-strations. The current work proposes the use of experiment design to choose environments for humans to perform these demonstrations. This reduces the number of demonstrations needed to estimate the unknown ground truth formula with low error. A novel computationally efficient strategy is proposed to generate informative environments by using an optimal planner as the model for the demonstrator. Instead of evaluating all possible environments, the search space reduces to the placement of informative orderings of likely eventual goals along an optimal planner's solution. A human study with 600 demonstrations from 20 participants for 4 tasks on a 2D interface validates the proposed hypothesis and empirical performance benefit in terms of convergence and error over baselines. The human study dataset is also publicly shared.

ICRA Conference 2023 Conference Paper

Extracting generalizable skills from a single plan execution using abstraction-critical state detection

• Khen Elimelech
• Lydia E. Kavraki
• Moshe Y. Vardi

Robotic task planning is computationally challenging. To reduce planning cost and support life-long operation, we must leverage prior planning experience. To this end, we address the problem of extracting reusable and generalizable abstract skills from successful plan executions. In previous work, we introduced a supporting framework, allowing us, theoretically, to extract an abstract skill from a single execution and later automatically adapt it and reuse it in new domains. We also proved that, given a library of such skills, we can significantly reduce the planning effort for new problems. Nevertheless, until now, abstract-skill extraction could only be performed manually. In this paper, we finally close the automation loop and explain how abstract skills can be practically and automatically extracted. We start by analyzing the desired qualities of an abstract skill and formulate skill extraction as an optimization problem. We then develop two extraction algorithms, based on the novel concept of abstraction-critical state detection. As we show experimentally, the approach is independent of any planning domain.

ICRA Conference 2023 Conference Paper

Kinodynamic Rapidly-exploring Random Forest for Rearrangement-Based Nonprehensile Manipulation

• Kejia Ren
• Podshara Chanrungmaneekul
• Lydia E. Kavraki
• Kaiyu Hang

Rearrangement-based nonprehensile manipulation still remains as a challenging problem due to the high-dimensional problem space and the complex physical uncertainties it entails. We formulate this class of problems as a coupled problem of local rearrangement and global action optimization by incorporating free-space transit motions between constrained rearranging actions. We propose a forest-based kinodynamic planning framework to concurrently search in multiple problem regions, so as to enable global exploration of the most task-relevant subspaces, while facilitating effective switches between local rearranging actions. By interleaving dynamic horizon planning and action execution, our framework can adaptively handle real-world uncertainties. With extensive experiments, we show that our framework significantly improves the planning efficiency and manipulation effectiveness while being robust against various uncertainties.

ICRA Conference 2023 Conference Paper

Object Reconfiguration with Simulation-Derived Feasible Actions

• Yiyuan Lee
• Wil Thomason
• Zachary Kingston
• Lydia E. Kavraki

3D object reconfiguration encompasses common robot manipulation tasks in which a set of objects must be moved through a series of physically feasible state changes into a desired final configuration. Object reconfiguration is challenging to solve in general, as it requires efficient reasoning about environment physics that determine action validity. This information is typically manually encoded in an explicit transition system. Constructing these explicit encodings is tedious and error-prone, and is often a bottleneck for planner use. In this work, we explore embedding a physics simulator within a motion planner to implicitly discover and specify the valid actions from any state, removing the need for manual specification of action semantics. Our experiments demonstrate that the resulting simulation-based planner can effectively produce physically valid rearrangement trajectories for a range of 3D object reconfiguration problems without requiring more than an environment description and start and goal arrangements.

ICRA Conference 2023 Conference Paper

Optimal Grasps and Placements for Task and Motion Planning in Clutter

• Carlos Quintero-Peña
• Zachary Kingston
• Tianyang Pan
• Rahul Shome
• Anastasios Kyrillidis
• Lydia E. Kavraki

Many methods that solve robot planning problems, such as task and motion planners, employ discrete symbolic search to find sequences of valid symbolic actions that are grounded with motion planning. Much of the efficacy of these planners lies in this grounding-bad placement and grasp choices can lead to inefficient planning when a problem has many geometric constraints. Moreover, grounding methods such as naïve sampling often fail to find appropriate values for these choices in the presence of clutter. Towards efficient task and motion planning, we present a novel optimization-based approach for grounding to solve cluttered problems that have many constraints that arise from geometry. Our approach finds an optimal grounding and can provide feedback to discrete search for more effective planning. We demonstrate our method against baseline methods in complex simulated environments.

IROS Conference 2023 Conference Paper

Robots as AI Double Agents: Privacy in Motion Planning

• Rahul Shome
• Zachary Kingston
• Lydia E. Kavraki

Robotics and automation are poised to change the landscape of home and work in the near future. Robots are adept at deliberately moving, sensing, and interacting with their environments. The pervasive use of robotics promises societal and economic payoffs due to its capabilities—conversely, the capabilities of robots to move within and sense the world around them is susceptible to abuse. Robots, unlike typical sensors, are inherently autonomous, active, and deliberate. Such automated agents can become AI double agents liable to violate the privacy of coworkers, privileged spaces, and other stakeholders. In this work we highlight the understudied and inevitable threats to privacy that can be posed by the autonomous, deliberate motions and sensing of robots. We frame the problem within broader sociotechnological questions alongside a comprehensive review. The privacy-aware motion planning problem is formulated in terms of cost functions that can be modified to induce privacy-aware behavior: preserving, agnostic, or violating. Simulated case studies in manipulation and navigation, with altered cost functions, are used to demonstrate how privacy-violating threats can be easily injected, sometimes with only small changes in performance (solution path lengths). Such functionality is already widely available. This preliminary work is meant to lay the foundations for near-future, holistic, interdisciplinary investigations that can address questions surrounding privacy in intelligent robotic behaviors determined by planning algorithms.

IROS Conference 2022 Conference Paper

Comparing Reconstruction- and Contrastive-based Models for Visual Task Planning

• Constantinos Chamzas
• Martina Lippi
• Michael C. Welle
• Anastasia Varava
• Lydia E. Kavraki
• Danica Kragic

Learning state representations enables robotic planning directly from raw observations such as images. Several methods learn state representations by utilizing losses based on the reconstruction of the raw observations from a lower-dimensional latent space. The similarity between observations in the space of images is often assumed and used as a proxy for estimating similarity between the underlying states of the system. However, observations commonly contain task-irrelevant factors of variation which are nonetheless important for reconstruction, such as varying lighting and different camera viewpoints. In this work, we define relevant evaluation metrics and perform a thorough study of different loss functions for state representation learning. We show that models exploiting task priors, such as Siamese networks with a simple contrastive loss, outperform reconstruction-based representations in visual task planning in case of task-irrelevant factors of variations.

ICRA Conference 2022 Conference Paper

Failure is an option: Task and Motion Planning with Failing Executions

• Tianyang Pan
• Andrew M. Wells
• Rahul Shome
• Lydia E. Kavraki

Future robotic deployments will require robots to be able to repeatedly solve a variety of tasks in application domains. Task and motion planning addresses complex robotic problems that combine discrete reasoning over states and actions and geometric interactions during action executions. Moving beyond deterministic settings, stochastic actions can be handled by modeling the problem as a Markov Decision Process. The underlying probabilities however are typically hard to model since failures might be caused by hardware imperfections, sensing noise, or physical interactions. We pro-pose a framework to address a task and motion planning setting where actions can fail during execution. To achieve a task goal actions need to be computed and executed despite failures. The robot has to infer which actions are robust and for each new problem effectively choose a solution that reduces expected execution failures. The key idea is to continually recover and refine the underlying beliefs associated with actions across multiple different problems in the domain. Our proposed method can find solutions that reduce the expected number of discrete, executed actions. Results in physics-based simulation indicate that our method outperforms baseline replanning strategies to deal with failing executions.

ICRA Conference 2022 Conference Paper

Human-Guided Motion Planning in Partially Observable Environments

• Carlos Quintero-Peña
• Constantinos Chamzas
• Zhanyi Sun
• Vaibhav V. Unhelkar
• Lydia E. Kavraki

Motion planning is a core problem in robotics, with a range of existing methods aimed to address its diverse set of challenges. However, most existing methods rely on complete knowledge of the robot environment; an assumption that seldom holds true due to inherent limitations of robot perception. To enable tractable motion planning for high-DOF robots under partial observability, we introduce BLIND, an algorithm that leverages human guidance. BLIND utilizes inverse reinforcement learning to derive motion-level guidance from human critiques. The algorithm overcomes the computational challenge of reward learning for high-DOF robots by projecting the robot's continuous configuration space to a motion-planner-guided discrete task model. The learned reward is in turn used as guidance to generate robot motion using a novel motion planner. We demonstrate BLIND using the Fetch robot and perform two simulation experiments with partial observability. Our experiments demonstrate that, despite the challenge of partial observability and high dimensionality, BLIND is capable of generating safe robot motion and outperforms baselines on metrics of teaching efficiency, success rate, and path quality.

ICRA Conference 2022 Conference Paper

Learning to Retrieve Relevant Experiences for Motion Planning

• Constantinos Chamzas
• Aedan Cullen
• Anshumali Shrivastava
• Lydia E. Kavraki

Recent work has demonstrated that motion planners' performance can be significantly improved by retrieving past experiences from a database. Typically, the experience database is queried for past similar problems using a similarity function defined over the motion planning problems. However, to date, most works rely on simple hand-crafted similarity functions and fail to generalize outside their corresponding training dataset. To address this limitation, we propose (FIRE), a framework that extracts local representations of planning problems and learns a similarity function over them. To generate the training data we introduce a novel self-supervised method that identifies similar and dissimilar pairs of local primitives from past solution paths. With these pairs, a Siamese network is trained with the contrastive loss and the similarity function is realized in the network's latent space. We evaluate FIRE on an 8-DOF manipulator in five categories of motion planning problems with sensed environments. Our experiments show that FIRE retrieves relevant experiences which can informatively guide sampling-based planners even in problems outside its training distribution, outperforming other baselines.

IROS Conference 2022 Conference Paper

Rearrangement-Based Manipulation via Kinodynamic Planning and Dynamic Planning Horizons

• Kejia Ren
• Lydia E. Kavraki
• Kaiyu Hang

Robot manipulation in cluttered environments of-ten requires complex and sequential rearrangement of multiple objects in order to achieve the desired reconfiguration of the target objects. Due to the sophisticated physical interactions involved in such scenarios, rearrangement-based manipulation is still limited to a small range of tasks and is especially vulnerable to physical uncertainties and perception noise. This paper presents a planning framework that leverages the efficiency of sampling-based planning approaches, and closes the manipulation loop by dynamically controlling the planning horizon. Our approach interleaves planning and execution to progressively approach the manipulation goal while correcting any errors or path deviations along the process. Meanwhile, our framework allows the definition of manipulation goals without requiring explicit goal configurations, enabling the robot to flexibly interact with all objects to facilitate the manipulation of the target ones. With extensive experiments both in simulation and on a real robot, we evaluate our framework on three manipulation tasks in cluttered environments: grasping, relocating, and sorting. In comparison with two baseline approaches, we show that our framework can significantly improve planning efficiency, robustness against physical uncertainties, and task success rate under limited time budgets.

IROS Conference 2022 Conference Paper

Robowflex: Robot Motion Planning with MoveIt Made Easy

• Zachary Kingston
• Lydia E. Kavraki

Robowflex is a software library for robot motion planning in industrial and research applications, leveraging the popular Moveit library and Robot Operating System (ROS) middleware. Robowflex provides an augmented API for crafting and manipulating motion planning queries within a single program, making motion planning with Moveit easy. Robowflex's high-level API simplifies many common use-cases while still providing low-level access to the Moveit library when needed. Robowflex is particularly useful for 1) developing new motion planners, 2) evaluating motion planners, and 3) complex problems that use motion planning as a subroutine (e. g. , task and motion planning). Robowflex also provides visualization capabilities, integrations to other robotics libraries (e. g. , DART and Tesseract), and is complementary to other robotics packages. With our library, the user does not need to be an expert at ROS or Moveit to set up motion planning queries, extract information from results, and directly interface with a variety of software components. We demonstrate its efficacy through several example use-cases.

IROS Conference 2021 Conference Paper

A General Task and Motion Planning Framework For Multiple Manipulators

• Tianyang Pan
• Andrew M. Wells
• Rahul Shome
• Lydia E. Kavraki

Many manipulation tasks combine high-level discrete planning over actions with low-level motion planning over continuous robot motions. Task and motion planning (TMP) provides a powerful general framework to combine discrete and geometric reasoning, and solvers have been previously proposed for single-robot problems. Multi-robot TMP expands the range of TMP problems that can be solved but poses significant challenges when considering scalability and solution quality. We present a general TMP framework designed for multiple robotic manipulators. This is based on two contributions. First, we propose an optimal task planner designed to support simultaneous discrete actions. Second, we introduce an intermediate scheduler layer between task planner and motion planner to evaluate alternate robot assignments to these actions. This aggressively explores the search space and typically reduces the number of expensive task planning calls. Several benchmarks with a rich set of actions for two manipulators are evaluated. We show promising results in scalability and solution quality of our TMP framework with the scheduler for up to six objects. A demonstration indicates scalability to up to five robots.

IROS Conference 2021 Conference Paper

A Sampling-based Motion Planning Framework for Complex Motor Actions

• Shlok Sobti
• Rahul Shome
• Swarat Chaudhuri
• Lydia E. Kavraki

We present a framework for planning complex motor actions such as pouring or scooping from arbitrary start states in cluttered real-world scenes. Traditional approaches to such tasks use dynamic motion primitives (DMPs) learned from human demonstrations. We enhance a recently proposed state-of-the-art DMP technique capable of obstacle avoidance by including them within a novel hybrid framework. This complements DMPs with sampling-based motion planning algorithms, using the latter to explore the scene and reach promising regions from which a DMP can successfully complete the task. Experiments indicate that even obstacle-aware DMPs suffer in task success when used in scenarios which largely differ from the trained demonstration in terms of the start, goal, and obstacles. Our hybrid approach significantly outperforms obstacle-aware DMPs by successfully completing tasks in cluttered scenes for a pouring task in simulation. We further demonstrate our method on a real robot for pouring and scooping tasks.

ICRA Conference 2021 Conference Paper

Asymptotically Optimal Kinodynamic Planning Using Bundles of Edges

• Rahul Shome
• Lydia E. Kavraki

Using sampling to estimate the connectivity of high-dimensional configuration spaces has been the theoretical underpinning for effective sampling-based motion planners. Typical strategies either build a roadmap, or a tree as the underlying search structure that connects sampled configurations, with a focus on guaranteeing completeness and optimality as the number of samples tends to infinity. Roadmap-based planners allow preprocessing the space, and can solve multiple kinematic motion planning problems, but need a steering function to connect pairwise-states. Such steering functions are difficult to define for kinodynamic systems, and limit the applicability of roadmaps to motion planning problems with dynamical systems. Recent advances in the analysis of single-query tree-based planners has shown that forward search trees based on random propagations are asymptotically optimal. The current work leverages these recent results and proposes a multi-query framework for kinodynamic planning. Bundles of kinodynamic edges can be sampled to cover the state space before the query arrives. Then, given a motion planning query, the connectivity of the state space reachable from the start can be recovered from a forward search tree reasoning about a local neighborhood of the edge bundle from each tree node. The work demonstrates theoretically that considering any constant radial neighborhood during this process is sufficient to guarantee asymptotic optimality. Experimental validation in five and twelve dimensional simulated systems also highlights the ability of the proposed edge bundles to express high-quality kinodynamic solutions. Our approach consistently finds higher quality solutions compared to SST, and RRT, often with faster initial solution times. The strategy of sampling kinodynamic edges is demonstrated to be a promising new paradigm.

ICRA Conference 2021 Conference Paper

Finite-Horizon Synthesis for Probabilistic Manipulation Domains

• Andrew M. Wells
• Zachary Kingston
• Morteza Lahijanian
• Lydia E. Kavraki
• Moshe Y. Vardi

Robots have begun operating and collaborating with humans in industrial and social settings. This collaboration introduces challenges: the robot must plan while taking the human’s actions into account. In prior work, the problem was posed as a 2-player deterministic game, with a limited number of human moves. The limit on human moves is unintuitive, and in many settings determinism is undesirable. In this paper, we present a novel planning method for collaborative human-robot manipulation tasks via probabilistic synthesis. We introduce a probabilistic manipulation domain that captures the interaction by allowing for both robot and human actions with states that represent the configurations of the objects in the workspace. The task is specified using Linear Temporal Logic over finite traces (LTL f ). We then transform our manipulation domain into a Markov Decision Process (MDP) and synthesize an optimal policy to satisfy the specification on this MDP. We present two novel contributions: a formalization of probabilistic manipulation domains allowing us to apply existing techniques and a comparison of different encodings of these domains. Our framework is validated on a physical UR5 robot.

IROS Conference 2021 Conference Paper

HyperPlan: A Framework for Motion Planning Algorithm Selection and Parameter Optimization

• Mark Moll
• Constantinos Chamzas
• Zachary Kingston
• Lydia E. Kavraki

Over the years, many motion planning algorithms have been proposed. It is often unclear which algorithm might be best suited for a particular class of problems. The problem is compounded by the fact that algorithm performance can be highly dependent on parameter settings. This paper shows that hyperparameter optimization is an effective tool in both algorithm selection and parameter tuning over a given set of motion planning problems. We present different loss functions for optimization that capture different notions of optimality. The approach is evaluated on a broad range of scenes using two different manipulators, a Fetch and a Baxter. We show that optimized planning algorithm performance significantly improves upon baseline performance and generalizes broadly in the sense that performance improvements carry over to problems that are very different from the ones considered during optimization.

ICRA Conference 2021 Conference Paper

Learning Sampling Distributions Using Local 3D Workspace Decompositions for Motion Planning in High Dimensions

• Constantinos Chamzas
• Zachary Kingston
• Carlos Quintero-Peña
• Anshumali Shrivastava
• Lydia E. Kavraki

Earlier work has shown that reusing experience from prior motion planning problems can improve the efficiency of similar, future motion planning queries. However, for robots with many degrees-of-freedom, these methods exhibit poor generalization across different environments and often require large datasets that are impractical to gather. We present SPARK and FLAME, two experience-based frameworks for sampling-based planning applicable to complex manipulators in 3D environments. Both combine samplers associated with features from a workspace decomposition into a global biased sampling distribution. SPARK decomposes the environment based on exact geometry while FLAME is more general, and uses an octree-based decomposition obtained from sensor data. We demonstrate the effectiveness of SPARK and FLAME on a real and simulated Fetch robot tasked with challenging pick-and-place manipulation problems. Our approaches can be trained incrementally and significantly improve performance with only a handful of examples, generalizing better over diverse tasks and environments as compared to prior approaches.

ICRA Conference 2021 Conference Paper

Robust Optimization-based Motion Planning for high-DOF Robots under Sensing Uncertainty

• Carlos Quintero-Peña
• Anastasios Kyrillidis
• Lydia E. Kavraki

Motion planning for high degree-of-freedom (DOF) robots is challenging, especially when acting in complex environments under sensing uncertainty. While there is significant work on how to plan under state uncertainty for low-DOF robots, existing methods cannot be easily translated into the high-DOF case, due to the complex geometry of the robot’s body and its environment. In this paper, we present a method that enhances optimization-based motion planners to produce robust trajectories for high-DOF robots for convex obstacles. Our approach introduces robustness into planners that are based on sequential convex programming: We reformulate each convex subproblem as a robust optimization problem that "protects" the solution against deviations due to sensing uncertainty. The parameters of the robust problem are estimated by sampling from the distribution of noisy obstacles, and performing a first-order approximation of the signed distance function. The original merit function is updated to account for the new costs of the robust formulation at every step. The effectiveness of our approach is demonstrated on two simulated experiments that involve a full body square robot, that moves in randomly generated scenes, and a 7-DOF Fetch robot, performing tabletop operations. The results show nearly zero probability of collision for a reasonable range of the noise parameters for Gaussian and Uniform uncertainty.

IROS Conference 2021 Conference Paper

Using Experience to Improve Constrained Planning on Foliations for Multi-Modal Problems

• Zachary Kingston
• Constantinos Chamzas
• Lydia E. Kavraki

Many robotic manipulation problems are multi-modal—they consist of a discrete set of mode families (e. g. , whether an object is grasped or placed) each with a continuum of parameters (e. g. , where exactly an object is grasped). Core to these problems is solving single-mode motion plans, i. e. , given a mode from a mode family (e. g. , a specific grasp), find a feasible motion to transition to the next desired mode. Many planners for such problems have been proposed, but complex manipulation plans may require prohibitively long computation times due to the difficulty of solving these underlying single-mode problems. It has been shown that using experience from similar planning queries can significantly improve the efficiency of motion planning. However, even though modes from the same family are similar, they impose different constraints on the planning problem, and thus experience gained in one mode cannot be directly applied to another. We present a new experience-based framework, ALEF, for such multi-modal planning problems. ALEF learns using paths from single-mode problems from a mode family, and applies this experience to novel modes from the same family. We evaluate ALEF on a variety of challenging problems and show a significant improvement in the efficiency of sampling-based planners both in isolation and within a multi-modal manipulation planner.

IROS Conference 2020 Conference Paper

Augmenting Control Policies with Motion Planning for Robust and Safe Multi-robot Navigation

• Tianyang Pan
• Christos K. Verginis
• Andrew M. Wells
• Lydia E. Kavraki
• Dimos V. Dimarogonas

This work proposes a novel method of incorporating calls to a motion planner inside a potential field control policy for safe multi-robot navigation with uncertain dynamics. The proposed framework can handle more general scenes than the control policy and has low computational costs. Our work is robust to uncertain dynamics and quickly finds high-quality paths in scenarios generated from real-world floor plans. In the proposed approach, we attempt to follow the control policy as much as possible, and use calls to the motion planner to escape local minima. Trajectories returned from the motion planner are followed using a path-following controller guaranteeing robustness. We demonstrate the utility of our approach with experiments based on floor plans gathered from real buildings.

ICRA Conference 2020 Conference Paper

Informing Multi-Modal Planning with Synergistic Discrete Leads

• Zachary Kingston
• Andrew M. Wells
• Mark Moll
• Lydia E. Kavraki

Robotic manipulation problems are inherently continuous, but typically have underlying discrete structure, e. g. , whether or not an object is grasped. This means many problems are multi-modal and in particular have a continuous infinity of modes. For example, in a pick-and-place manipulation domain, every grasp and placement of an object is a mode. Usually manipulation problems require the robot to transition into different modes, e. g. , going from a mode with an object placed to another mode with the object grasped. To successfully find a manipulation plan, a planner must find a sequence of valid single-mode motions as well as valid transitions between these modes. Many manipulation planners have been proposed to solve tasks with multi-modal structure. However, these methods require mode-specific planners and fail to scale to very cluttered environments or to tasks that require long sequences of transitions. This paper presents a general layered planning approach to multi-modal planning that uses a discrete "lead" to bias search towards useful mode transitions. The difficulty of achieving specific mode transitions is captured online and used to bias search towards more promising sequences of modes. We demonstrate our planner on complex scenes and show that significant performance improvements are tied to both our discrete "lead" and our continuous representation.

GandALF Workshop 2020 Workshop Paper

LTLf Synthesis on Probabilistic Systems

• Andrew M. Wells
• Morteza Lahijanian
• Lydia E. Kavraki
• Moshe Y. Vardi

Many systems are naturally modeled as Markov Decision Processes (MDPs), combining probabilities and strategic actions. Given a model of a system as an MDP and some logical specification of system behavior, the goal of synthesis is to find a policy that maximizes the probability of achieving this behavior. A popular choice for defining behaviors is Linear Temporal Logic (LTL). Policy synthesis on MDPs for properties specified in LTL has been well studied. LTL, however, is defined over infinite traces, while many properties of interest are inherently finite. Linear Temporal Logic over finite traces (LTLf) has been used to express such properties, but no tools exist to solve policy synthesis for MDP behaviors given finite-trace properties. We present two algorithms for solving this synthesis problem: the first via reduction of LTLf to LTL and the second using native tools for LTLf. We compare the scalability of these two approaches for synthesis and show that the native approach offers better scalability compared to existing automaton generation tools for LTL.

ICRA Conference 2019 Conference Paper

Efficient Symbolic Reactive Synthesis for Finite-Horizon Tasks

• Keliang He
• Andrew M. Wells
• Lydia E. Kavraki
• Moshe Y. Vardi

When humans and robots perform complex tasks together, the robot must have a strategy to choose its actions based on observed human behavior. One well-studied approach for finding such strategies is reactive synthesis. Existing approaches for finite-horizon tasks have used an explicit state approach, which incurs high runtime. In this work, we present a compositional approach to perform synthesis for finite-horizon tasks based on binary decision diagrams. We show that for pick-and-place tasks, the compositional approach achieves orders-of-magnitude speed-ups compared to previous approaches. We demonstrate the synthesized strategy on a UR5 robot.

ICRA Conference 2019 Conference Paper

Lazy Evaluation of Goal Specifications Guided by Motion Planning

• Juan David Hernández
• Mark Moll
• Lydia E. Kavraki

Nowadays robotic systems are expected to share workspaces and collaborate with humans. In such collaborative environments, an important challenge is to ground or establish the correct semantic interpretation of a human request. Once such an interpretation is available, the request must be translated into robot motion commands in order to complete the desired task. It is not unusual that a human request cannot be grounded to a unique interpretation, thus leading to an ambiguous request. A simple example is to ask a robot to “put a cup on the table, ” when there are multiple cups available. In order to deal with this kind of ambiguous request, we propose a delayed or lazy variable grounding. The focus of this paper is a motion planning algorithm that, given goal regions that represent different valid groundings, lazily finds a feasible path to any one valid grounding. This algorithm includes a reward-penalty strategy, which attempts to prioritize those goal regions that seem more promising to provide a solution. We validate our approach by solving requests with multiple valid alternatives in both simulation and real-world experiments.

ICRA Conference 2019 Conference Paper

Online Multilayered Motion Planning with Dynamic Constraints for Autonomous Underwater Vehicles

• Eduard Vidal
• Mark Moll
• Narcís Palomeras
• Juan David Hernández
• Marc Carreras
• Lydia E. Kavraki

Underwater robots are subject to complex hydro-dynamic forces. These forces define how the vehicle moves, so it is important to consider them when planning trajectories. However, performing motion planning considering the dynamics on the robot’s onboard computer is challenging due to the limited computational resources available. In this paper an efficient motion planning framework for autonomous underwater vehicles (AUVs) is presented. By introducing a loosely coupled multilayered planning design, our framework is able to generate dynamically feasible trajectories while keeping the planning time low enough for online planning. First, a fast path planner operating in a lower-dimensional projected space computes a lead path from the start to the goal configuration. Then, the lead path is used to bias the sampling of a second motion planner, which takes into account all the dynamic constraints. Furthermore, we propose a strategy for online planning that saves computational resources by generating the final trajectory only up to a finite horizon. By using the finite horizon strategy together with the multilayered approach, the sampling of the second planner focuses on regions where good quality solutions are more likely to be found, significantly reducing the planning time. To provide strong safety guarantees our framework also incorporates the conservative approximations of inevitable collision states (icss). finally, we present simulations and experiments using a real underwater robot to demonstrate the capabilities of our framework.

ICRA Conference 2019 Conference Paper

Using Local Experiences for Global Motion Planning

• Constantinos Chamzas
• Anshumali Shrivastava
• Lydia E. Kavraki

Sampling-based planners are effective in many real-world applications such as robotics manipulation, navigation, and even protein modeling. However, it is often challenging to generate a collision-free path in environments where key areas are hard to sample. In the absence of any prior information, sampling-based planners are forced to explore uniformly or heuristically, which can lead to degraded performance. One way to improve performance is to use prior knowledge of environments to adapt the sampling strategy to the problem at hand. In this work, we decompose the workspace into local primitives, memorizing local experiences by these primitives in the form of local samplers, and store them in a database. We synthesize an efficient global sampler by retrieving local experiences relevant to the given situation. Our method transfers knowledge effectively between diverse environments that share local primitives and speeds up the performance dramatically. Our results show, in terms of solution time, an improvement of multiple orders of magnitude in two traditionally challenging high-dimensional problems compared to state-of-the-art approaches.

AAMAS Conference 2018 Conference Paper

Bounded Policy Synthesis for POMDPs with Safe-Reachability Objectives

• Yue Wang
• Swarat Chaudhuri
• Lydia E. Kavraki

Planning robust executions under uncertainty is a fundamental challenge for building autonomous robots. Partially Observable Markov Decision Processes (POMDPs) provide a standard framework for modeling uncertainty in many applications. In this work, we study POMDPs with safe-reachability objectives, which require that with a probability above some threshold, a goal state is eventually reached while keeping the probability of visiting unsafe states below some threshold. This POMDP formulation is different from the traditional POMDP models with optimality objectives and we show that in some cases, POMDPs with safe-reachability objectives can provide a better guarantee of both safety and reachability than the existing POMDP models through an example. A key algorithmic problem for POMDPs is policy synthesis, which requires reasoning over a vast space of beliefs (probability distributions). To address this challenge, we introduce the notion of a goal-constrained belief space, which only contains beliefs reachable from the initial belief under desired executions that can achieve the given safereachability objective. Our method compactly represents this space over a bounded horizon using symbolic constraints, and employs an incremental Satisfiability Modulo Theories (SMT) solver to efficiently search for a valid policy over it. We evaluate our method using a case study involving a partially observable robotic domain with uncertain obstacles. The results show that our method can synthesize policies over large belief spaces with a small number of SMT solver calls by focusing on the goal-constrained belief space.

IROS Conference 2017 Conference Paper

Reactive synthesis for finite tasks under resource constraints

• Keliang He
• Morteza Lahijanian
• Lydia E. Kavraki
• Moshe Y. Vardi

There are many applications where robots have to operate in environments that other agents can change. In such cases, it is desirable for the robot to achieve a given high-level task despite interference. Ideally, the robot must decide its next action as it observes the changes in the world, i. e. act reactively. In this paper, we consider a reactive planning problem for finite robotic tasks with resource constraints. The task is represented using a temporal logic for finite behaviors and the robot must achieve the task using limited resources under all possible finite sequences of moves of other agents. We present a formulation for this problem and an approach based on quantitative games. The efficacy of the approach is demonstrated through a manipulation case study.

ICRA Conference 2016 Conference Paper

High-dimensional Winding-Augmented Motion Planning with 2D topological task projections and persistent homology

• Florian T. Pokorny
• Danica Kragic
• Lydia E. Kavraki
• Ken Goldberg

Recent progress in motion planning has made it possible to determine homotopy inequivalent trajectories between an initial and terminal configuration in a robot configuration space. Current approaches have however either assumed the knowledge of differential one-forms related to a skeletonization of the collision space, or have relied on a simplicial representation of the free space. Both of these approaches are currently however not yet practical for higher dimensional configuration spaces. We propose 2D topological task projections (TTPs): mappings from the configuration space to 2-dimensional spaces where simplicial complex filtrations and persistent homology can identify topological properties of the high-dimensional free configuration space. Our approach only requires the availability of collision free samples to identify winding centers that can be used to determine homotopy inequivalent trajectories. We propose the Winding Augmented RRT and RRT* (WA-RRT/RRT*) algorithms using which homotopy inequivalent trajectories can be found. We evaluate our approach in experiments with configuration spaces of planar linkages with 2–10 degrees of freedom. Results indicate that our approach can reliably identify suitable topological task projections and our proposed WA-RRT and WA-RRT* algorithms were able to identify a collection of homotopy inequivalent trajectories in each considered configuration space dimension.

IROS Conference 2016 Conference Paper

Planning feasible and safe paths online for autonomous underwater vehicles in unknown environments

• Juan David Hernández
• Mark Moll
• Eduard Vidal
• Marc Carreras
• Lydia E. Kavraki

We present a framework for planning collision-free and safe paths online for autonomous underwater vehicles (AUVs) in unknown environments. We build up on our previous work and propose an improved approach. While preserving its main modules (mapping, planning and mission handler), the framework now considers motion constraints to plan feasible paths, i. e. , those that meet vehicle's motion capabilities. The new framework also incorporates a risk function to avoid navigating close to nearby obstacles, and reuses the last best known solution to eliminate time-consuming pruning routines. To evaluate this approach, we use the Sparus II AUV, a torpedo-shaped vehicle performing autonomous missions in a 2-dimensional workspace. We validate the framework's new features by solving tasks in both simulation and real-world in-water trials and comparing results with our previous approach.

ICAPS Conference 2016 Conference Paper

Task and Motion Policy Synthesis as Liveness Games

• Yue Wang 0026
• Neil T. Dantam
• Swarat Chaudhuri
• Lydia E. Kavraki

We present a novel and scalable policy synthesis approach for robots. Rather than producing single-path plans for a static environment, we consider changing environments with uncontrollable agents, where the robot needs a policy to respond correctly over the infinite-horizon interaction with the environment. Our approach operates on task and motion domains, and combines actions over discrete states with continuous, collision-free paths. We synthesize a task and motion policy by iteratively generating a candidate policy and verifying its correctness. For efficient policy generation, we use grammars for potential policies to limit the search space and apply domain-specific heuristics to generalize verification failures, providing stricter constraints on policy candidates. For efficient policy verification, we construct compact, symbolic constraints for valid policies and employ a Satisfiability Modulo Theories (SMT) solver to check the validity of these constraints. Furthermore, the SMT solver enables quantitative specifications such as energy limits. The results show that our approach offers better scalability compared to a state-of-the-art policy synthesis tool in the tested benchmarks and demonstrate an order-of-magnitude speedup from our heuristics for the tested mobile manipulation domain.

ICRA Conference 2015 Conference Paper

A heuristic approach to finding diverse short paths

• Caleb Voss
• Mark Moll
• Lydia E. Kavraki

We present an algorithm that seeks to find a set of diverse, short paths through a roadmap graph. The usefulness of a such a set is illustrated in robotic motion planning and routing applications wherein a precomputed roadmap of the environment is partially invalidated by some change, for example, relocation of obstacles or reconfiguration of the robot. Our algorithm employs the heuristic that nearby configurations are likely to be invalidated by the same change. To find diverse short paths, the algorithm finds the shortest detour avoiding a collection of balls imposed on the graph as simulated obstacles. Different collections yield different short paths. Paths may then be checked for validity as a cheap alternative to checking or reconstructing the entire roadmap. We describe a formal definition of path set diversity and several measures on which to evaluate our algorithm. We compare the speed and quality of our heuristic algorithm's results against an exact algorithm that computes the optimally shortest set of paths on the roadmap having a minimum diversity. We show that, with tolerable loss in shortness, we produce equally diverse path sets orders of magnitude more quickly.

ICRA Conference 2015 Conference Paper

Towards manipulation planning with temporal logic specifications

• Keliang He
• Morteza Lahijanian
• Lydia E. Kavraki
• Moshe Y. Vardi

Manipulation planning from high-level task specifications, even though highly desirable, is a challenging problem. The large dimensionality of manipulators and complexity of task specifications make the problem computationally intractable. This work introduces a manipulation planning framework with linear temporal logic (LTL) specifications. The use of LTL as the specification language allows the expression of rich and complex manipulation tasks. The framework deals with the state-explosion problem through a novel abstraction technique. Given a robotic system, a workspace consisting of obstacles, manipulable objects, and locations of interest, and a co-safe LTL specification over the objects and locations, the framework computes a motion plan to achieve the task through a synergistic multi-layered planning architecture. The power of the framework is demonstrated through case studies, in which the planner efficiently computes plans for complex tasks. The case studies also illustrate the ability of the framework in intelligently moving away objects that block desired executions without requiring backtracking.

ICRA Conference 2014 Conference Paper

A sampling-based strategy planner for nondeterministic hybrid systems

• Morteza Lahijanian
• Lydia E. Kavraki
• Moshe Y. Vardi

This paper introduces a strategy planner for nondeterministic hybrid systems with complex continuous dynamics. The planner uses sampling-based techniques and game-theoretic approaches to generate a series of plans and decision choices that increase the chances of success within a fixed time budget. The planning algorithm consists of two phases: exploration and strategy improvement. During the exploration phase, a search tree is grown in the hybrid state space by sampling state and control spaces for a fixed amount of time. An initial strategy is then computed over the search tree using a game-theoretic approach. To mitigate the effects of nondeterminism in the initial strategy, the strategy improvement phase extends new tree branches to the goal, using the data that is collected in the first phase. The efficacy of this planner is demonstrated on simulation of two hybrid and nondeterministic car-like robots in various environments. The results show significant increases in the likelihood of success for the strategies computed by the two-phase algorithm over a simple exploration planner.

ICRA Conference 2014 Conference Paper

Fast stochastic motion planning with optimality guarantees using local policy reconfiguration

• Ryan Luna
• Morteza Lahijanian
• Mark Moll
• Lydia E. Kavraki

This work presents a framework for fast reconfiguration of local control policies for a stochastic system to satisfy a high-level task specification. The motion of the system is abstracted to a class of uncertain Markov models known as bounded-parameter Markov decision processes (BMDPs). During the abstraction, an efficient sampling-based method for stochastic optimal control is used to construct several policies within a discrete region of the state space in order for the system to transit between neighboring regions. A BMDP is then used to find an optimal strategy over the local policies by maximizing a continuous reward function; a new policy can be computed quickly if the reward function changes. The efficacy of the framework is demonstrated using a sequence of online tasks, showing that highly desirable policies can be obtained by reconfiguring existing local policies in just a few seconds.

ICRA Conference 2014 Conference Paper

SMT-based synthesis of integrated task and motion plans from plan outlines

• Srinivas Nedunuri
• Sailesh Prabhu
• Mark Moll
• Swarat Chaudhuri
• Lydia E. Kavraki

We present a new approach to integrated task and motion planning (ITMP) for robots performing mobile manipulation. In our approach, the user writes a high-level specification that captures partial knowledge about a mobile manipulation setting. In particular, this specification includes a plan outline that syntactically defines a space of plausible integrated plans, a set of logical requirements that the generated plan must satisfy, and a description of the physical space that the robot manipulates. A synthesis algorithm is now used to search for an integrated plan that falls within the space defined by the plan outline, and also satisfies all requirements. Our synthesis algorithm complements continuous motion planning algorithms with calls to a Satisfiability Modulo Theories (SMT) solver. From the scene description, a motion planning algorithm is used to construct a placement graph, an abstraction of a manipulation graph whose paths represent feasible, low-level motion plans. An SMT-solver is now used to symbolically explore the space of all integrated plans that correspond to paths in the placement graph, and also satisfy the constraints demanded by the plan outline and the requirements. Our approach is implemented in a system called Ro-bosynth. We have evaluated Robosynth on a generalization of an ITMP problem investigated in prior work. The experiments demonstrate that our method is capable of generating integrated plans for a number of interesting variations on the problem.

ICRA Conference 2013 Conference Paper

Anytime solution optimization for sampling-based motion planning

• Ryan Luna
• Ioan Alexandru Sucan
• Mark Moll
• Lydia E. Kavraki

Recent work in sampling-based motion planning has yielded several different approaches for computing good quality paths in high degree of freedom systems: path shortcutting methods that attempt to shorten a single solution path by connecting non-consecutive configurations, a path hybridization technique that combines portions of two or more solutions to form a shorter path, and asymptotically optimal algorithms that converge to the shortest path over time. This paper presents an extensible meta-algorithm that incorporates a traditional sampling-based planning algorithm with offline path shortening techniques to form an anytime algorithm which exhibits competitive solution lengths to the best known methods and optimizers. A series of experiments involving rigid motion and complex manipulation are performed as well as a comparison with asymptotically optimal methods which show the efficacy of the proposed scheme, particularly in high-dimensional spaces.

ICRA Conference 2013 Conference Paper

Automated model approximation for robotic navigation with POMDPs

• Devin K. Grady
• Mark Moll
• Lydia E. Kavraki

Partially-Observable Markov Decision Processes (POMDPs) are a problem class with significant applicability to robotics when considering the uncertainty present in the real world, however, they quickly become intractable for large state and action spaces. A method to create a less complex but accurate action model approximation is proposed and evaluated using a state-of-the-art POMDP solver. We apply this general and powerful formulation to a robotic navigation task under state and sensing uncertainty. Results show that this method can provide a useful action model that yields a policy with similar overall expected reward compared to the true action model, often with significant computational savings. In some cases, our reduced complexity model can solve problems where the true model is too complex to find a policy that accomplishes the task. We conclude that this technique of building problem-dependent approximations can provide significant computational advantages and can help expand the complexity of problems that can be considered using current POMDP techniques.

ICRA Conference 2013 Conference Paper

Resolution Independent Density Estimation for motion planning in high-dimensional spaces

• Bryant Gipson
• Mark Moll
• Lydia E. Kavraki

This paper presents a new motion planner, Search Tree with Resolution Independent Density Estimation (STRIDE), designed for rapid exploration and path planning in high-dimensional systems (greater than 10). A Geometric Near-neighbor Access Tree (GNAT) is maintained to estimate the sampling density of the configuration space, allowing an implicit, resolution-independent, Voronoi partitioning to provide sampling density estimates, naturally guiding the planner towards unexplored regions of the configuration space. This planner is capable of rapid exploration in the full dimension of the configuration space and, given that a GNAT requires only a valid distance metric, STRIDE is largely parameter-free. Extensive experimental results demonstrate significant dimension-dependent performance improvements over alternative state-of-the-art planners. In particular, high-dimensional systems where the free space is mostly defined by narrow passages were found to yield the greatest performance improvements. Experimental results are shown for both a classical 6-dimensional problem and those for which the dimension incrementally varies from 3 to 27.

ICRA Conference 2012 Conference Paper

Accounting for uncertainty in simultaneous task and motion planning using task motion multigraphs

• Ioan Alexandru Sucan
• Lydia E. Kavraki

This paper describes an algorithm that considers uncertainty while solving the simultaneous task and motion planning (STAMP) problem. Information about uncertainty is transferred to the task planning level from the motion planning level using the concept of a task motion multigraph (TMM). TMMs were introduced in previous work to improve the efficiency of solving the STAMP problem for mobile manipulators. In this work, Markov Decision Processes are used in conjunction with TMMs to select sequences of actions that solve the STAMP problem such that the resulting solutions have higher probability of feasibility. Experimental evaluation indicates significantly improved probability of feasibility for solutions to the STAMP problem, compared to algorithms that ignore uncertainty information when selecting possible sequences of actions. At the same time, the efficiency due to TMMs is largely maintained.

IROS Conference 2012 Conference Paper

Low-dimensional projections for SyCLoP

• Matthew R. Maly
• Lydia E. Kavraki

This paper presents an extension to SyCLoP, a multilayered motion planning framework that has been shown to successfully solve high-dimensional problems with differential constraints. SyCLoP combines traditional sampling-based planning with a high-level decomposition of the workspace through which it attempts to guide a low-level tree of motions. We investigate a generalization of SyCLoP in which the high-level decomposition is defined over a given low-dimensional projected subspace of the state space. We begin with a manually-chosen projection to demonstrate that projections other than the workspace can potentially work well. We then evaluate SyCLoP's performance with random projections and projections determined from linear dimensionality reduction over elements of the state space, for which the results are mixed. As we will see, finding a useful projection is a difficult problem, and we conclude this paper by discussing the merits and drawbacks of various types of projections.

ICRA Conference 2011 Conference Paper

Mobile manipulation: Encoding motion planning options using task motion multigraphs

• Ioan Alexandru Sucan
• Lydia E. Kavraki

This paper introduces the concept of a task motion multigraph, a data structure that can be used to reveal a difficulty specific to mobile manipulation: the possibility of planning in different state spaces in order to achieve the same goal. The different options reflect the mobile manipulator's ability to use different hardware components to perform a required task. For instance, a humanoid robot can open a door with its left arm or with its right arm. Thus, motion planning can be performed in the left arm's state space or in the right arm's state space. Given the specification of a task, it is shown how to encode the available motion planning options in a task motion multigraph. An algorithm that computes sequences of motion plans for mobile manipulators using the newly introduced notion is presented and evaluated. The algorithm makes use of information from the task motion multigraph to prioritize the spaces for which motion plans are computed. Experimental results show that reduced planning times can be obtained when considering the available planning options.

IROS Conference 2011 Conference Paper

On the advantages of task motion multigraphs for efficient mobile manipulation

• Ioan Alexandru Sucan
• Lydia E. Kavraki

This paper addresses the problem of computing the sequence of motion plans necessary for a mobile manipulator to execute a given task. In our previous work, we have demonstrated that computational advantages can be obtained when solving this problem by using the notion of a task motion multigraph (TMM). TMMs represent the state spaces that correspond to various hardware components of the robot, and they convey this information to the motion planning level. In this paper, we present and evaluate an algorithm that further exploits TMMs and explores multiple state spaces simultaneously. Since tasks to be performed by mobile manipulators often allow solutions that use only a subset of the robot's hardware components, motion plans can be found in lower dimensional state spaces. The resulting solutions tend to be shorter, more natural and faster to compute. We show that when planning under geometric constraints only, information gained while exploring lower dimensional spaces can be reused to obtain solutions in higher dimensional spaces, if necessary. The reuse of information implicitly provides the ability to compute decoupled motion plans. If solutions are not found while planning in a decoupled fashion, the algorithm resorts to planning in the robot's full state space. Our experiments indicate speedups of 200% and solutions up to four times shorter when compared to an analogous approach that does not employ TMMs.

ICRA Conference 2010 Conference Paper

On the implementation of single-query sampling-based motion planners

• Ioan Alexandru Sucan
• Lydia E. Kavraki

Single-query sampling-based motion planners are an efficient class of algorithms widely used today to solve challenging motion planning problems. This paper exposes the common core of these planners and presents a tutorial for their implementation. A set of ideas extracted from algorithms existing in the literature is presented. In addition, lower level implementation details that are often skipped in papers due to space limitations are discussed. The purpose of the paper is to improve our understanding of single-query sampling-based motion planners and motivate our community to explore avenues of research that lead to significant improvements of such algorithms.

ICRA Conference 2010 Conference Paper

Sampling-based motion planning with temporal goals

• Amit Bhatia 0001
• Lydia E. Kavraki
• Moshe Y. Vardi

This paper presents a geometry-based, multi-layered synergistic approach to solve motion planning problems for mobile robots involving temporal goals. The temporal goals are described over subsets of the workspace (called propositions) using temporal logic. A multi-layered synergistic framework has been proposed recently for solving planning problems involving significant discrete structure. In this framework, a high-level planner uses a discrete abstraction of the system and the exploration information to suggest feasible high-level plans. A low-level sampling-based planner uses the physical model of the system, and the suggested high-level plans, to explore the state-space for feasible solutions. In this paper, we advocate the use of geometry within the above framework to solve motion planning problems involving temporal goals. We present a technique to construct the discrete abstraction using the geometry of the obstacles and the propositions defined over the workspace. Furthermore, we show through experiments that the use of geometry results in significant computational speedups compared to previous work. Traces corresponding to trajectories of the system are defined employing the sampling interval used by the low-level algorithm. The applicability of the approach is shown for second-order nonlinear robot models in challenging workspace environments with obstacles, and for a variety of temporal logic specifications.

IROS Conference 2009 Conference Paper

On the performance of random linear projections for sampling-based motion planning

• Ioan Alexandru Sucan
• Lydia E. Kavraki

Sampling-based motion planners are often used to solve very high-dimensional planning problems. Many recent algorithms use projections of the state space to estimate properties such as coverage, as it is impractical to compute and store this information in the original space. Such estimates help motion planners determine the regions of space that merit further exploration. In general, the employed projections are user-defined, and to the authors' knowledge, automatically computing them has not yet been investigated. In this work, the feasibility of offline-computed random linear projections is evaluated within the context of a state-of-the art sampling-based motion planning algorithm. For systems with moderate dimension, random linear projections seem to outperform human intuition. For more complex systems it is likely that non-linear projections would be better suited.

IROS Conference 2009 Conference Paper

Real-time perception-guided motion planning for a personal robot

• Radu Bogdan Rusu
• Ioan Alexandru Sucan
• Brian P. Gerkey
• Sachin Chitta
• Michael Beetz
• Lydia E. Kavraki

This paper presents significant steps towards the online integration of 3D perception and manipulation for personal robotics applications. We propose a modular and distributed architecture, which seamlessly integrates the creation of 3D maps for collision detection and semantic annotations, with a real-time motion replanning framework. To validate our system, we present results obtained during a comprehensive mobile manipulation scenario, which includes the fusion of the above components with a higher level executive.

ICRA Conference 2008 Conference Paper

Impact of workspace decompositions on discrete search leading continuous exploration (DSLX) motion planning

• Erion Plaku
• Lydia E. Kavraki
• Moshe Y. Vardi

We have recently proposed DSLX, a motion planner that significantly reduces the computational time for solving challenging kinodynamic problems by interleaving continuous state-space exploration with discrete search on a workspace decomposition. An important but inadequately understood aspect of DSLX is the role of the workspace decomposition on the computational efficiency of the planner. Understanding this role is important for successful applications of DSLX to increasingly complex robotic systems. This work shows that the granularity of the workspace decomposition directly impacts computational efficiency: DSLX is faster when the decomposition is neither too fine-nor too coarse-grained. Finding the right level of granularity can require extensive fine-tuning. This work demonstrates that significant computational efficiency can instead be obtained with no fine-tuning by using conforming Delaunay triangulations, which in the context of DSLX provide a natural workspace decomposition that allows an efficient interplay between continuous state-space exploration and discrete search. The results of this work are based on extensive experiments on DSLX using grid, trapezoidal, and triangular decompositions of various granularities to solve challenging first and second-order kinodynamic motion-planning problems.

IROS Conference 2008 Conference Paper

Kinodynamic motion planning with hardware demonstrations

• Ioan Alexandru Sucan
• Jonathan F. Kruse
• Mark Yim
• Lydia E. Kavraki

This paper provides proof-of-concept that state-of-the-art sampling-based motion planners that are tightly integrated with a physics-based simulator can compute paths that can be executed by a physical robotic system. Such a goal has been the subject of intensive research during the last few years and reflects the desire of the motion planning community to produce paths that are directly relevant to realistic mechanical systems and do not need a huge post-processing step in order to be executed on a robotic platform. To evaluate this approach, a recently developed motion planner is used to compute paths for a modular robot constructed from seven modules. These paths are then executed on hardware and compared with the paths predicted by the planner. For the system considered, the planner prediction and the paths achieved by the physical robot match, up to small errors. This work reveals the potential of modern motion planning research and its implications in the design and operation of complex robotic platforms.

IROS Conference 2008 Conference Paper

Replanning: A powerful planning strategy for hard kinodynamic problems

• Konstantinos I. Tsianos
• Lydia E. Kavraki

A series of kinodynamic sampling-based planners have appeared over the last decade to deal with high dimensional problems for robots with realistic motion constraints. Yet, offline sampling-based planners only work in static and known environments, suffer from unbounded memory requirements and the produced paths tend to contain a lot of unnecessary maneuvers. This paper describes an online replanning algorithm which is flexible and extensible. Our results show that using a sampling-based planner in a loop, we can guide the robot to its goal using a low dimensional navigation function. We obtain higher success rates and shorter solution paths in a series of problems using only bounded memory.

IROS Conference 2007 Conference Paper

A decentralized planner that guarantees the safety of communicating vehicles with complex dynamics that replan online

• Kostas E. Bekris
• Konstantinos I. Tsianos
• Lydia E. Kavraki

This paper considers the problem of coordinating multiple vehicles with kinodynamic constraints that operate in the same partially-known environment. The vehicles are able to communicate within limited range. Their objective is to avoid collisions between them and with the obstacles, while the vehicles move towards their goals. An important issue of real-time planning for systems with bounded acceleration is that inevitable collision states must also be avoided. The focus of this paper is to guarantee safety despite the dynamic constraints with a decentralized motion planning technique that employs only local information. We propose a coordination framework that allows vehicles to generate and select compatible sets of valid trajectories and prove that this scheme guarantees collision-avoidance in the specified setup. The theoretical results have been also experimentally confirmed with a distributed simulator where each vehicle replans online with a sampling- based, kinodynamic motion planner and uses message-passing to communicate with neighboring agents.

ICRA Conference 2007 Conference Paper

A Motion Planner for a Hybrid Robotic System with Kinodynamic Constraints

• Erion Plaku
• Lydia E. Kavraki
• Moshe Y. Vardi

The rapidly increasing complexity of tasks robotic systems are expected to carry out underscores the need for the development of motion planners that can take into account discrete changes in the continuous motions of the system. Completion of tasks such as exploration of unknown or hazardous environments often requires discrete changes in the controls and motions of the robot in order to adapt to different terrains or maintain operability during partial failures or other mishaps. The contribution of this work toward this objective is the development of an efficient motion planner for a hybrid robotic system. The controls and motion equations of the robot could change discretely in order to enable the robot to operate in different terrains. The framework in this paper blends discrete searching with sampling-based motion planning for continuous state spaces and is well-suited for robotic systems modeled as hybrid systems with numerous discrete modes and transitions. This multi-layered approach offers considerable improvements over existing methods addressing similar problems, as indicated by the experimental results.

ICRA Conference 2007 Conference Paper

Greedy but Safe Replanning under Kinodynamic Constraints

• Kostas E. Bekris
• Lydia E. Kavraki

We consider motion planning problems for a vehicle with kinodynamic constraints, where there is partial knowledge about the environment and replanning is required. We present a new tree-based planner that explicitly deals with kinodynamic constraints and addresses the safety issues when planning under finite computation times, meaning that the vehicle avoids collisions in its evolving configuration space. In order to achieve good performance we incrementally update a tree data-structure by retaining information from previous steps and we bias the search of the planner with a greedy, yet probabilistically complete state space exploration strategy. Moreover, the number of collision checks required to guarantee safety is kept to a minimum. We compare our technique with alternative approaches as a standalone planner and show that it achieves favorable performance when planning with dynamics. We have applied the planner to solve a challenging replanning problem involving the mapping of an unknown workspace with a nonholonomic platform

ICRA Conference 2007 Conference Paper

OOPS for Motion Planning: An Online, Open-source, Programming System

• Erion Plaku
• Kostas E. Bekris
• Lydia E. Kavraki

The success of sampling-based motion planners has resulted in a plethora of methods for improving planning components, such as sampling and connection strategies, local planners and collision checking primitives. Although this rapid progress indicates the importance of the motion planning problem and the maturity of the field, it also makes the evaluation of new methods time consuming. We propose that a systems approach is needed for the development and the experimental validation of new motion planners and/or components in existing motion planners. In this paper, we present the online, open-source, programming system for motion planning (OOPS MP ), a programming infrastructure that provides implementations of various existing algorithms in a modular, object-oriented fashion that is easily extendible. The system is open-source, since a community-based effort better facilitates the development of a common infrastructure and is less prone to errors. We hope that researchers will contribute their optimized implementations of their methods and thus improve the quality of the code available for use. A dynamic Web interface and a dynamic linking architecture at the programming level allows users to easily add new planning components, algorithms, benchmarks, and experiment with different parameters. The system allows the direct comparison of new contributions with existing approaches on the same hardware and programming infrastructure

ICRA Conference 2006 Conference Paper

Evaluation of Algorithms for bearing-only SLAM

• Kostas E. Bekris
• Max Glick
• Lydia E. Kavraki

An important milestone for building affordable robots that can become widely popular is to address robustly the simultaneous localization and mapping (SLAM) problem with inexpensive, off-the-shelf sensors, such as monocular cameras. These sensors, however, impose significant challenges on SLAM procedures because they provide only bearing data related to environmental landmarks. This paper starts by providing an extensive comparison of different techniques for bearing-only SLAM in terms of robustness under different noise models, landmark densities and robot paths. We have experimented in a simulated environment with a variety of existing online algorithms including Rao-Blackwellized particle filters (RB-PFs). Our experiments suggest that RB-PFs are more robust compared to other existing methods and run considerably faster. Nevertheless, their performance suffers in the presence of outliers. In order to overcome this limitation we proceed to propose an augmentation of RB-PFs with: (a) Gaussian sum filters for landmark initialization and (b) an online, unsupervised outlier rejection policy. This framework exhibits impressive robustness and efficiency even in the presence of outliers

ICRA Conference 2005 Conference Paper

Distributed Sampling-Based Roadmap of Trees for Large-Scale Motion Planning

• Erion Plaku
• Lydia E. Kavraki

High-dimensional problems arising from complex robotic systems test the limits of current motion planners and require the development of efficient distributed motion planners that take full advantage of all the available resources. This paper shows how to effectively distribute the computation of the Sampling-based Roadmap of Trees (SRT) algorithm using a decentralized master-client scheme. The distributed SRT algorithm allows us to solve very high-dimensional problems that cannot be efficiently addressed with existing planners. Our experiments show nearly linear speedups with eighty processors and indicate that similar speedups can be obtained with several hundred processors.

ICRA Conference 2005 Conference Paper

Path Planning for Variable Resolution Minimal-Energy Curves of Constant Length

• Mark Moll
• Lydia E. Kavraki

We present a new approach to path planning for flexible wires. We introduce a method for computing stable configurations of a wire subject to manipulation constraints. These configurations correspond to minimal-energy curves. The representation is adaptive in the sense that the number of parameters automatically varies with the complexity of the underlying curve. We introduce a planner that computes paths from one minimal-energy curve to another such that all intermediate curves are also minimal-energy curves. Using a simplified model for obstacles, we can find minimal-energy curves of fixed length that pass through specified tangents at given control points. Our work has applications in motion planning for surgical suturing and snake-like robots.

ICRA Conference 2004 Conference Paper

Angle-based Methods for Mobile Robot Navigation: Reaching the Entire Plane

• Kostas E. Bekris
• Antonis A. Argyros
• Lydia E. Kavraki

Popular approaches for mobile robot navigation involve range information and metric maps of the workspace. For many sensors, however, such as cameras and wireless hardware, the angle between two features or beacons is easier to measure. With these sensors' features in mind, we initially present a control law, which allows a robot with an omni-directional sensor to reach a subset of the plane by monitoring the angles of only three landmarks. By analyzing the law's properties, a second law has been developed that reaches the complementary set of points. The two methods are then combined in a path planning framework that reaches any possible goal configuration in a planar obstacle-free workspace with three landmarks. The proposed framework could be used together with other techniques, such as obstacle avoidance and topological maps to improve the efficiency of autonomous navigation. Experiments have been conducted on a robotic platform using a panoramic camera that exhibits the effectiveness and accuracy of the proposed techniques. This work provides evidence that navigational tasks can be performed using only a small number of primitive sensor cues and without the explicit computation of range information.

ICRA Conference 2004 Conference Paper

Guided Expansive Spaces Trees: a Search Strategy for Motion- and Cost-constrained State Spaces

• Jeff M. Phillips
• Nazareth Bedrossian
• Lydia E. Kavraki

Motion planning for systems with constraints on controls or the need for relatively straight paths for real-time actions presents challenges for modern planners. This paper presents an approach which addresses these types of systems by building on existing motion planning approaches. Guided Expansive Spaces Trees are introduced to search for a low cost and relatively straight path in a space with motion constraints. Path Gradient Descent, which builds on the idea of Elastic Strips, finds the locally optimal path for an existing path. These techniques are tested on simulations of rendezvous and docking of the space shuttle to the International Space Station and of a 4-foot fan-controlled blimp in a factory setting.

ICRA Conference 2004 Conference Paper

Path Planning for Minimal Energy Curves of Constant Length

• Mark Moll
• Lydia E. Kavraki

In this paper we present a new path planning technique for a flexible wire. We first introduce a new parametrization designed to represent low-energy configurations. Based on this parametrization we can find curves that satisfy endpoint constraints. Next, we present three different techniques for minimizing energy within the self-motion manifold of the curve. We introduce a local planner to find smooth minimal energy deformations for these curves that can be used by a general path planning algorithm. Using a simplified model for obstacles, we can find minimal energy curves of fixed length that pass through specified tangents at given control points. Finally, we show that the parametrization introduced in this paper is a good approximation of true minimal energy curves. Our work has applications in surgical suturing and snake-like robots.

IROS Conference 2003 Conference Paper

Multiple query probabilistic roadmap planning using single query planning primitives

• Kostas E. Bekris
• Brian Y. Chen
• Andrew M. Ladd
• Erion Plaku
• Lydia E. Kavraki

We propose a combination of techniques that solve multiple queries for motion planning problems with single query planners. Our implementation uses a probabilistic roadmap method (PRM) with bidirectional rapidly exploring random trees (BI-RRT) as the local planner. With small modifications to the standard algorithms, we obtain a multiple query planner, which is significantly faster and more reliable than its component parts. Our method provides a smooth spectrum between the PRM and BI-RRT techniques and obtains the advantages of both. We observed that the performance differences are most notable in planning instances with several rigid nonconvex robots in a scene with narrow passages. Our work is in the spirit of non-uniform sampling and refinement techniques used in earlier work on PRM.

ICRA Conference 2002 Conference Paper

Generalizing the Analysis of PRM

• Andrew M. Ladd
• Lydia E. Kavraki

This paper presents it novel analysis of the probabilistic roadmap method (PRM) for path planning. We formulate the problem in terms of computing the transitive closure of a relation over a probability space and give a bound in terms of the number of intermediate points for some path and the probability of choosing a point from a certain set. Explicit geometric assumptions are not necessary to complete this analysis and consequently it provides some unification of the previous work as well as generalizing new path planning problems, two of which, 2k-DOF kinodynamic point robots and deformable robots with force field control, are presented in this paper.

ICRA Conference 2002 Conference Paper

Simulated Knot Tying

• Jeff M. Phillips
• Andrew M. Ladd
• Lydia E. Kavraki

Applications such as suturing in medical simulations require the modeling of knot tying in physically realistic rope. The paper describes the design and implementation of such a system. Our model uses a spline of linear springs, adaptive subdivision and a dynamics simulation. Collisions are discrete event simulated and follow the impulse model. Although some care must be taken to maintain stable knots, we demonstrate our simple model is sufficient for this task. In particular, we do not use friction or explicit constraints to maintain the knot. As examples, we tie an overhand knot and a reef knot.

IROS Conference 2002 Conference Paper

Using wireless Ethernet for localization

• Andrew M. Ladd
• Kostas E. Bekris
• Guillaume Marceau
• Algis Rudys
• Dan S. Wallach
• Lydia E. Kavraki

IEEE 802. 11b wireless Ethernet is rapidly becoming the standard for in-building and short-range wireless communication. Many mobile devices such as mobile robots, laptops and PDAs already use this protocol for wireless communication. Many wireless Ethernet cards measure the signal strength of incoming packets. This paper investigates the feasibility of implementing a localization system using this sensor. Using a Bayesian localization framework, we show experiments demonstrating that off-the-shelf wireless hardware can accurately be used for location sensing and tracking with about one meter precision in a wireless-enabled office building.

ICRA Conference 2001 Conference Paper

A Geometric Approach to Designing a Programmable Force Field with a Unique Stable Equilibrium for Parts in the Plane

• Attawith Sudsang
• Lydia E. Kavraki

In automated assembly, before parts can be put together, they often have to be appropriately oriented and positioned. The device performing this task is generally referred to as a part feeder. A new class of devices for non-prehensile distributed manipulation, such as MEMS actuator arrays, vibrating plates, etc. , provide an alternative to traditional mechanical platforms for part feeding. These devices can be abstracted as programmable vector fields. Manipulation plans for these devices can therefore be considered as strategies for applying a sequence of fields to bring parts to some desired configurations. Typically, to uniquely orient and position a part, several fields have to be sequentially employed. Previously, it has been proven that there exists a combination of the unit radial field and a constant field that induces a unique stable equilibrium for almost any part. However, that work focuses mainly on an existential proof and fails to address how to compute the field for a given part. We propose a radically different field with a proof confirming that the field induces a unique stable equilibrium for almost any part. This proof leads us to a method for computing a single field for orienting a given part, together with the corresponding stable equilibrium configuration of the part.

ICRA Conference 2001 Conference Paper

Decomposition-based Motion Planning: A Framework for Real-time Motion Planning in High-dimensional Spaces

• Oliver Brock
• Lydia E. Kavraki

Research in motion planning has been striving to develop faster planning algorithms in order to be able to address a wider range of applications. In this paper a novel real-time motion planning framework, called decomposition-based motion planning, is proposed. It is particularly well suited for planning problems that arise in service and field robotics. It decomposes the original planning problem into simpler sub-problems, whose successive solution empirically results in a large reduction of the overall complexity. A particular implementation of decomposition-based planning is proposed. Experiments with an eleven degree-of-freedom mobile manipulator are presented.

ICRA Conference 2001 Conference Paper

Molecular Docking: A Problem with Thousands of Degrees of Freedom

• Miguel L. Teodoro
• George N. Phillips
• Lydia E. Kavraki

This paper reports on the problem of docking a highly flexible small molecule to the pocket of a highly flexible receptor macromolecule. The prediction of the intermolecular complex is of vital importance for the development of new therapeutics as docking can alter the chemical behavior of the receptor macromolecule. We first present current methods for docking, which have several limitations. Some of these methods consider only the flexibility of the ligand solving a problem with a few tens of degrees of freedom. When the receptor flexibility is taken into account several hundreds or even thousands of degrees of freedom need to be considered. Most methods take into account only a small number of these degrees of freedom by using chemical knowledge specific to the problem. We show how to use a singular value decomposition of molecular dynamics trajectories to automatically obtain information about the global flexibility of the receptor and produce interesting conformations that can be used for docking purposes.

IROS Conference 2001 Conference Paper

Part orientation with a force field: orienting multiple shapes using a single field

• Attawith Sudsang
• Lydia E. Kavraki

In automated assembly, before parts can be put together, they often have to be appropriately oriented and positioned. The device performing this task is generally referred to as a part feeder. A new class of devices for non-prehensible distributed manipulation, such as MEMS actuator arrays, vibrating plates, etc. , provides an alternative to traditional mechanical platforms for part feeding. These devices can be abstracted as programmable vector fields. Manipulation plans for these devices can therefore be considered as strategies for applying a sequence of fields to bring parts to some desired configurations. Typically, to uniquely orient and position a part, several fields have to be sequentially employed. In previous work (2001), we have shown that this objective can be accomplished using a single field. The work characterizes such a field for a given part. In this paper, we discover another interesting property of the field. In particular, we show that for a finite set of parts (with different shapes), we can specify a single field that can uniquely orient and position every part in the set. A force field device implementing this field therefore may be used as a part feeder for every part in the set without any reconfiguration.

ICRA Conference 2000 Conference Paper

A Framework for Using the Workspace Medial Axis in PRM Planners

• Christopher Holleman
• Lydia E. Kavraki

Probabilistic roadmap (PRM) planners have been very successful in path planning for a wide variety of problems, especially applications involving robots with many degrees of freedom. These planners randomly sample the configuration space, building up a roadmap that connects the samples. A major problem is finding valid configurations in tight areas, and many methods have been proposed to more effectively sample these regions. By constructing a skeleton-like subset of the free regions of the workspace, these heuristics can be strengthened. The skeleton provides a concise description of the workspace topology and an efficient means of finding points with maximal clearance from the obstacles. We examine the medial axis as a skeleton, including a method to compute an approximation to it. The medial axis is a two-equidistant surface in the workspace. We form a heuristic for finding difficult configurations using the medial axis, and demonstrate its effectiveness in a planner for rigid objects in a 3D workspace.

IROS Conference 2000 Conference Paper

A two level fuzzy PRM for manipulation planning

• Christian L. Nielsen
• Lydia E. Kavraki

This paper presents an algorithm which extends the probabilistic roadmap (PRM) framework to handle manipulation planning. This is done by using a two level approach, a PRM of PRMs. The first level builds a manipulation graph, whose nodes represent stable placements of the manipulated objects while the edges represent transfer and transit actions. The actual motion planning for the transfer and transit paths is done by PRM planners at the second level. The approach is made possible by the introduction of a new kind of roadmap, called the fuzzy roadmap. The fuzzy roadmap contains edges which are not verified by a local planner during construction. Instead, each edge is assigned a number which represents the probability that it is feasible. Later, if the edge is part of a solution path, the edge is checked for collisions. The overall effect is that our roadmaps evolve iteratively until they contain a solution. The use of fuzzy roadmaps in both levels of our manipulation planner offers many advantages. At the first level, a fuzzy roadmap represents the manipulation graph and addresses the problem of having probabilistically complete planners at the second level. At the second level, fuzzy roadmaps drastically reduce the number of collision checks. The paper contains experimental results demonstrating the feasibility and efficiency of our scheme.

ICRA Conference 2000 Conference Paper

Deformable Volumes in Path Planning Applications

• Elliot Anshelevich
• Scott Owens
• Florent Lamiraux
• Lydia E. Kavraki

This paper addresses the problem of path planning for a class of deformable volumes under fairly general manipulation constraints. The underlying geometric model for the volume is provided by a mass-spring representation. It is augmented by a realistic mechanical model. The latter permits the computation of the shape of the considered object with respect to the grasping constraints by minimizing the energy function of the deformation of the object. Previous research in planning for deformable objects considered the case of elastic plates and proposed a randomized framework for planning paths for plates under manipulation constraints. The present paper modifies and extends the previously proposed framework to handle simple volumes. Our planner builds a roadmap in the configuration space. The nodes of the roadmap are equilibrium configurations of the considered volume under the manipulation constraints, while its edges correspond to quasi-static equilibrium paths. Paths are found by searching the roadmap. We present experimental results that illustrate our approach.

IROS Conference 2000 Conference Paper

Part assembly using static and dynamic force fields

• Jiangchun Luo
• Lydia E. Kavraki

Part assembly is an important goal of part manipulation. Among other techniques, programmable force fields have been introduced for part manipulation. For part assembly, more than one part needs to be manipulated. This can create problems since there can be interactions between the parts such as impact and friction. Modern technology is beginning to provide the means to control the magnitude and frequency of each actuator of the implemented force field. Thus dynamic and localized force fields can be used for part manipulation. This paper presents a novel strategy to assemble two parts with a sequence of static and dynamic programmable force fields. The strategy involves some initial sensing. Uncertainties occurring in the motion of the parts are taken into account to make the proposed strategy more robust.

ICRA Conference 2000 Conference Paper

Path Planning Using Lazy PRM

• Robert Bohlin
• Lydia E. Kavraki

Describes an approach to probabilistic roadmap planners (PRMs). The overall theme of the algorithm, called Lazy PRM, is to minimize the number of collision checks performed during planning and hence minimize the running time of the planner. Our algorithm builds a roadmap in the configuration space, whose nodes are the user-defined initial and goal configurations and a number of randomly generated nodes. Neighboring nodes are connected by edges representing paths between the nodes. In contrast with PRMs, our planner initially assumes that all nodes and edges in the roadmap are collision-free, and searches the roadmap at hand for a shortest path between the initial and the goal node. The nodes and edges along the path are then checked for collision. If a collision with the obstacles occurs, the corresponding nodes and edges are removed from the roadmap. Our planner either finds a new shortest path, or first updates the roadmap with new nodes and edges, and then searches for a shortest path. The above process is repeated until a collision-free path is returned. Lazy PRM is tailored to efficiently answer single planning queries, but can also be used for multiple queries. Experimental results presented in the paper show that our lazy method is very efficient in practice.

ICRA Conference 2000 Conference Paper

Positioning and Orienting a Class of Symmetric Parts Using a Combination of a Unit-Radial and a Constant Force Fields

• Florent Lamiraux
• Lydia E. Kavraki

Part positioning and orientation is a key issue in manufacturing. Extensive recent work has investigated a series of force fields for part positioning and orientation. Typically, a strategy that brings a part to a unique equilibrium consists of several force fields that are employed in sequence. Bohringer and Donald conjectured a few years ago that the combination of a unit radial field with a constant field would give rise to a unique equilibrium. Such a field is extremely interesting as it positions and orients parts without the need of sensing or a clock. We (2000) have proved this conjecture for nonsymmetric parts. In this paper, we focus our attention on symmetric parts and show that some of them can be uniquely positioned and oriented using the same field. Our work further explores the capabilities and limits of force fields and provides additional evidence that force fields are a powerful tool for parts manipulation.

ICRA Conference 2000 Conference Paper

Randomized Planning for Short Inspection Paths

• Tim Danner
• Lydia E. Kavraki

Addresses the following inspection problem: given a known workspace and a robot with vision capabilities compute a short path path for the robot such that each point on boundary of the workspace is visible from some point on the path. Autonomous inspection, such as by a flying camera, or a virtual reality architectural walkthrough, could be guided by a solution to the above inspection problem. Visibility constraints on both maximum viewing distance and maximum angle of incidence are considered to better model real sensors. An algorithm is presented for planar workspaces which operates in two steps: selecting art gallery-style guards and connecting them to form an inspection path. Experimental results for this algorithm are discussed. Next, the algorithm is extended to three dimensions and inspection paths are shown.

ICRA Conference 1999 Conference Paper

A Probabilistic Roadmap Approach for Systems with Closed Kinematic Chains

• 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 to rigid and elastic objects, and articulated robots without closed chains. It provides a framework for path planning problems that must satisfy closure constraints in addition to standard collision constraints. This expands the power of the probabilistic roadmap technique to include a variety of problems such as manipulation planning using two open-chain manipulators that cooperatively grasp an object, forming a system with a closed chain, and planning for reconfigurable robots where the robot links may be rearranged in a loop to ease manipulation or locomotion. We generate the vertices and edges in our probabilistic roadmap. We focus on the problem of planning the motions for a collection of attached links in a 2D environment with obstacles. The approach has been implemented and successfully demonstrated on several examples.

IROS Conference 1999 Conference Paper

A probabilistic roadmap planner for flexible objects with a workspace medial-axis-based sampling approach

• Leonidas J. Guibas
• Christopher Holleman
• Lydia E. Kavraki

Probabilistic roadmap planners have been used with success to plan paths for flexible objects such as metallic plates or plastic flexible pipes. This paper improves the performance of these planners by using the medial axis of the workspace to guide the random sampling. At a preprocessing stage, the medial axis of the workspace is computed using a recent efficient algorithm. Then the flexible object is fitted at random points along the medial axis. The energy of all generated configurations is minimized and the planner proceeds to connect them with low-energy quasi-static paths in a roadmap that captures the connectivity of the free space. Given an initial and a final configuration, the planner connects these to the roadmap and searches the roadmap for a path. Our experimental results show that the new sampling scheme is successful in identifying critical deformations of the object along solution paths which results in a significant reduction of the computation time. Our work on planning for flexible objects has applications in industrial settings, virtual reality environments, and medicine.

ICRA Conference 1999 Conference Paper

Path Planning for Elastic Plates Under Manipulation Constraints

• Florent Lamiraux
• Lydia E. Kavraki

Addresses the problem of path planning for a thin elastic metal plate under fairly general manipulation constraints. The underlying geometric model for the plate is provided by a Bezier representation. The geometric model is augmented by a realistic mechanical model. We assume that the plate is manipulated in accordance with a set of user-defined grasping constraints that specify the position and orientation of two opposite edges. Our mechanical model permits the computation of the shape of the plate with respect to the grasping constraints by minimizing the energy function of the deformation of the plate. Paths are computed by a planner that is based on the principle of probabilistic roadmaps. The planner builds a roadmap in the configuration space. The nodes of the roadmap are equilibrium configurations of the plate under the grasping constraints, while its edges correspond to quasi-static equilibrium paths. Paths are found by searching the roadmap. Several experimental results illustrate our approach.

ICRA Conference 1998 Conference Paper

Planning Paths for a Flexible Surface Patch

• Christopher Holleman
• Lydia E. Kavraki
• Joe D. Warren

This paper presents a probabilistic planner capable of finding paths for a flexible surface patch. The planner is based on the probabilistic roadmap approach to path planning while the surface patch is modeled as a low degree Bezier surface. We assume that we are dealing with an elastic part and define an approximate energy model for the part. The energy function penalizes excessive shear and bending of the part and we assume that low-energy configurations correspond to reversible elastic deformations of the part. The planner captures the connectivity of a space by building a roadmap, a network of simple paths connecting configurations selected in the space using randomized techniques. We report on the implementation of our planner and show experimental results with examples where the surface patch is required to move through a small hole in its workspace. Our work is a first step towards considering the physical properties of parts when planning paths.

ICRA Conference 1997 Conference Paper

Part orientation with programmable vector fields: two stable equilibria for most parts

• Lydia E. Kavraki

Part manipulation is an important but also time-consuming operation in industrial automation. Recent work explores alternative solutions to the mechanical parts feeders which have been traditionally used to sort and orient parts for assembly. One of the proposed alternatives is the use of programmable vector fields. The fields are realized on a plane on which the part is placed. The forces exerted on the part's contact surface translate and rotate the part to an equilibrium orientation. Certain vector fields can be implemented in the microscale with actuator arrays and in the macroscale with transversely vibrating plates. Although current technology is still limited, the dexterity that programmable vector fields offer has prompted researchers to further explore their capabilities. This paper presents a vector field that can simultaneously orient and pose most parts into two stable equilibrium configurations. The equilibrium configurations are easily computed a priori given the part to be oriented. Our analysis makes no assumptions about the shape of the part or its connectivity except that it moves as a rigid body. The proposed vector field offers the great advantage of stability of the equilibrium configurations under small perturbations of the part which is key for the orientation of toleranced parts.

ICRA Conference 1996 Conference Paper

Analysis of probabilistic roadmaps for path planning

• Lydia E. Kavraki
• Mihail N. Kolountzakis
• Jean-Claude Latombe

Provides an analysis of a path planning method which uses probabilistic roadmaps. This method has proven very successful in practice, but the theoretical understanding of its performance is still limited. Assuming that a path /spl gamma/ exists between two configurations a and b of the robot, we study the dependence of the failure probability to connect a and b on (i) the length of /spl gamma/, (ii) the distance function of /spl gamma/ from the obstacles, and (iii) the number of nodes N of the probabilistic roadmap constructed. Importantly, our results do not depend strongly on local irregularities of the configuration space, as was the case with previous analysis. These results are illustrated with a simple but illuminating example. In this example, we provide estimates for N, the principal parameter of the method, in order to achieve failure probability within prescribed bounds. We also compare, through this example, the different approaches to the analysis of the planning method.

STOC Conference 1995 Conference Paper

Randomized query processing in robot path planning (Extended Abstract)

• Lydia E. Kavraki
• Jean-Claude Latombe
• Rajeev Motwani 0001
• Prabhakar Raghavan

ICRA Conference 1994 Conference Paper

Randomized Preprocessing of Configuration Space for Fast Path Planning

• Lydia E. Kavraki
• Jean-Claude Latombe

This paper presents a new approach to path planning for robots with many degrees of freedom (DOF) operating in known static environments. The approach consists of a preprocessing and a planning stage. Preprocessing, which is done only once for a given environment, generates a network of randomly, but properly selected, collision-free configurations (nodes). Planning then connects any given initial and final configurations of the robot to two nodes of the network and computes a path through the network between these two nodes. Experiments show that after paying the preprocessing cost (on the order of hundreds of seconds), planning is extremely fast (on the order of a fraction of a second for many difficult examples involving a 10-DOF robot). The approach is particularly attractive for many-DOF robots which have to perform many successive point-to-point motions in the same environment. >

IROS Conference 1994 Conference Paper

Randomized preprocessing of configuration space for path planning: articulated robots

• Lydia E. Kavraki
• Jean-Claude Latombe

This paper describes the application of a recent approach to path planning for robots with many degrees of freedom (DOF) to articulated robots moving in two or three dimensional static environments. The planning approach, which itself is not restricted to articulated robots, consists of a preprocessing and a planning stage. The preprocessing is done only once for a given environment and generates a connected network of randomly, but properly selected, collision-free configurations (nodes). The planning then connects any given initial and final configurations of the robot to two nodes of the network and computes a path through the network between these two nodes. We show that after paying the preprocessing cost, planning is extremely fast for many difficult examples involving 7-DOF and 12-DOF robots. The approach is particularly attractive for many-DOF robots which have to perform many successive point-to-point motions in the same environment. >

ICRA Conference 1994 Conference Paper

Treatment Planning for a Radiosurgical System with General Kinematics

• Achim Schweikard
• Rhea Tombropoulos
• Lydia E. Kavraki
• John R. Adler Jr.
• Jean-Claude Latombe

In radiosurgery a beam of radiation is used as an ablative surgical instrument to destroy brain tumors. Treatment planning consists of computing a sequence of beam configurations for delivering a necrotic dose to the tumor, without damaging healthy tissue or particularly critical structures. In current systems, kinematic limitations severely constrain beam motion. This often results in inappropriate dose distributions. A new radiosurgical system has been implemented to overcome this disadvantage. In this system, a compact radiation source of high energy is moved by a 6-dof robotic arm. We describe algorithms for computing a motion with specified characteristics for this new system. Treatment plans used at test sites with earlier systems are compared to plans computed with the described algorithms. The experience reported shows that full kinematic flexibility combined with treatment planning algorithms allows for better protection of healthy tissue and higher dosage in tumors. >