Validating the behavior of autonomous Cyber-Physical Systems (CPS) and AI agents, which rely on automated controllers, is an objective of great importance. In recent years, Neural-Network (NN) controllers have been demonstrating great promise and experiencing tremendous popularity. Unfortunately, such learned controllers are often not certified and can cause the system to suffer from unpredictable or unsafe behavior. To mitigate this issue, a great effort has been dedicated to automated verification of systems. Specifically, works in the category of “black-box testing” rely on repeated system simulations to find a falsifying counterexample—a system run that violates a specification. As running high-fidelity simulations is computationally demanding, the goal of falsification approaches is to minimize the simulation effort needed to return a falsifying example. This often proves to be a great challenge, especially when the tested controller is well trained. This work contributes a novel falsification approach for autonomous systems under formal specification operating in uncertain environments. We are especially interested in CPS operating in rich, semantically defined, open environments, which yield high-dimensional, simulation-dependent sensor observations as inputs to the controller. Our approach introduces a novel reformulation of the falsification problem as the problem of planning a trajectory for a “meta-system,” which wraps and encapsulates the examined system; we call this approach: meta-planning. This approach results in testing fewer inputs, compared to serial input sampling, while making minimal assumptions on the system, and posing no limitation on the specification, environment, or controller, which is treated as a black-box. It also avoids redundant calculations and requires less effort for each test, by invoking only incremental updates to the autonomous-system’s trajectory at each iteration, using partial simulations. This formulation can be solved with standard sampling-based motion-planning techniques (like RRT), can gradually integrate domain knowledge to improve the search, based on its availability, and can even work with no domain knowledge at all. We support these ideas with an experimental study on falsification of an obstacle-avoiding autonomous car with a NN controller, where meta-planning demonstrates superior performance over alternative approaches.

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.

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.

The mapping of T-cell-receptors (TCRs) to their cognate peptides is crucial to improving cancer immunotherapy. Numerous computational methods and machine learning tools have been proposed to aid in the task. Yet, accurately constructing this map computationally remains a difficult problem. Most prior work has sought to predict TCR-peptide-MHC (TCR-pMHC) binding specificity by analyzing the amino acid sequences of the TCRs and peptides. However, recent advancements in crystallography, cryo-EM, and in silico protein modeling have provided researchers with the necessary data to analyze the 3D structures of TCRs, peptides, and MHCs. Current research suggests that information contained in the 3D structure of the TCRs and pMHCs can explain instances of TCR specificity that are not explained by sequence alone. As protein structure data continues to become more accurate and easier to obtain, structure-based methodologies for predicting TCR-pMHC binding will become increasingly important. We present STAG, a novel graph-based machine learning architecture for predicting TCR-pMHC binding specificity using 3D structure data. We show that STAG achieves comparable or better performance than existing methods while utilizing only spatial and physicochemical features from modeled protein structures.

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.

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.

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.

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.

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.

Task and motion planning represents a powerful set of hybrid planning methods that combine reasoning over discrete task domains and continuous motion generation. Traditional reasoning necessitates task domain models and enough information to ground actions to motion planning queries. Gaps in this knowledge often arise from sources such as occlusion or imprecise modeling. This work generates task and motion plans that include actions cannot be fully grounded at planning time. During execution, such an action is handled by a provided human-designed or learned closed-loop behavior. Execution combines offline planned motions and online behaviors till reaching the task goal. Failures of behaviors are fed back as constraints to find new plans. Forty real-robot trials and motivating demonstrations are performed to evaluate the proposed framework and compare it against state-of-the-art. Results show faster execution time, less number of actions, and more success in problems where diverse gaps arise. The experiment data are shared for researchers to simulate these settings. The work shows promise in expanding the applicable class of realistic partially grounded problems that robots can address.

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.

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.

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.

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.

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.

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.

An ongoing nurse labor shortage has the potential to impact patient care well-being in the entire healthcare system. Moreover, more complex and sophisticated nursing care is required today for patients in hospitals forcing hospital-based nurses to carry out frequent training and assessment procedures, both to onboard new nurses and to validate skills of existing staff that guarantees best practices and safety. In this paper we recognize an opportunity for the development and integration of intelligent robot tutoring technology into nursing education to tackle the growing challenges of nurse deficit. To this end, we identify specific research problems in the area of human-robot interaction that will need to be addressed to enable robot tutors for nurse training.

Proteins are dynamic macromolecules that perform vital functions in cells. A protein structure determines its function, but this structure is not static, as proteins change their conformation to achieve various functions. Understanding the conformational landscapes of proteins is essential to understand their mechanism of action. Sets of carefully chosen conformations can summarize such complex landscapes and provide better insights into protein function than single conformations. We refer to these sets as representative conformational ensembles. Recent advances in computational methods have led to an increase in the number of available structural datasets spanning conformational landscapes. However, extracting representative conformational ensembles from such datasets is not an easy task and many methods have been developed to tackle it. Our new approach, EnGens (short for ensemble generation), collects these methods into a unified framework for generating and analyzing representative protein conformational ensembles. In this work, we: (1) provide an overview of existing methods and tools for representative protein structural ensemble generation and analysis; (2) unify existing approaches in an open-source Python package, and a portable Docker image, providing interactive visualizations within a Jupyter Notebook pipeline; (3) test our pipeline on a few canonical examples from the literature. Representative ensembles produced by EnGens can be used for many downstream tasks such as protein-ligand ensemble docking, Markov state modeling of protein dynamics and analysis of the effect of single-point mutations.

Robotic manipulation is inherently continuous, but typically has an underlying discrete structure, such as if an object is grasped. Many problems like these aremultimodal, such as pick-and-place tasks where every object grasp and placement is amode. Multimodal problems require finding a sequence oftransitionsbetween modes—for example, a particular sequence of object picks and placements. However, many multimodal planners fail to scale when motion planning is difficult (e.g., in clutter) or the task has a long horizon (e.g., rearrangement). This work presents solutions for multimodal scalability in both these areas. For motion planning, we present an experience-based planning frameworkalefwhich reuses experience from similar modes both online and from training data. For task satisfaction, we present a layered planning approach that uses a discreteleadto bias search toward useful mode transitions, informed by weights over mode transitions. Together, these contributions enable multimodal planners to tackle complex manipulation tasks that were previously infeasible or inefficient, and provide significant improvements in scenes with high-dimensional robots.

We integrate sampling-based planning techniques with funnel-based feedback control to develop KDF, a new framework for solving the kinodynamic motion-planning problem via funnel control. The considered systems evolve subject to complex, nonlinear, and uncertain dynamics (also known as differential constraints). First, we use ageometricplanner to obtain a high-level safe path in a user-defined extended free space. Second, we develop a low-level funnel control algorithm that guarantees safe tracking of the path by the system. Neither the planner nor the control algorithm uses information on the underlying dynamics of the system, which makes the proposed scheme easily distributable to a large variety of different systems and scenarios. Intuitively, the funnel control module is able to implicitly accommodate the dynamics of the system, allowing hence the deployment of purely geometrical motion planners. Extensive computer simulations and hardware experiments with a 6-DOF robotic arm validate the proposed approach.

Reactive synthesis from high-level specifications that combine hard constraints expressed in Linear Temporal Logic (LTL) with soft constraints expressed by discounted sum (DS) rewards has applications in planning and reinforcement learning. An existing approach combines techniques from LTL synthesis with optimization for the DS rewards but has failed to yield a sound algorithm. An alternative approach combining LTL synthesis with satisficing DS rewards (rewards that achieve a threshold) is sound and complete for integer discount factors, but, in practice, a fractional discount factor is desired. This work extends the existing satisficing approach, presenting the first sound algorithm for synthesis from LTL and DS rewards with fractional discount factors. The utility of our algorithm is demonstrated on robotic planning domains.

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.

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.

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.

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.

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.

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.

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 3 D 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 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.

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.

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.

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 (LTLf). 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.

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.

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.

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.

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.

The framework of partially observable Markov decision processes (POMDPs) offers a standard approach to model uncertainty in many robot tasks. Traditionally, POMDPs are formulated with optimality objectives. In this article, we study a different formulation of POMDPs withBoolean objectives. For robotic domains that require a correctness guarantee of accomplishing tasks, Boolean objectives are natural formulations. We investigate the problem of POMDPs with a common Boolean objective:safe reachability, requiring that the robot eventually reaches a goal state with a probability above a threshold while keeping the probability of visiting unsafe states below a different threshold. Our approach builds upon the previous work that represents POMDPs with Boolean objectives using symbolic constraints. We employ a satisfiability modulo theories (SMTs) solver to efficiently search for solutions, i.e., policies or conditional plans that specify the action to take contingent on every possible event. A full policy or conditional plan is generally expensive to compute. To improve computational efficiency, we introduce the notion ofpartial conditional plansthat cover sampled events to approximate a full conditional plan. Our approach constructs a partial conditional plan parameterized by areplanning probability. We prove that the failure rate of the constructed partial conditional plan is bounded by the replanning probability. Our approach allows users to specify an appropriate bound on the replanning probability to balance efficiency and correctness. Moreover, we update this bound properly to quickly detect whether the current partial conditional plan meets the bound and avoid unnecessary computation. In addition, to further improve the efficiency, we cache partial conditional plans for sampled belief states and reuse these cached plans if possible. We validate our approach in several robotic domains. The results show that our approach outperforms a previous policy synthesis approach for POMDPs with safe-reachability objectives in these domains.Note to Practitioners—This article was motivated by two observations. On the one hand, in robotics applications where uncertainty in sensing and actions is present, the solution to the classical partially observable Markov decision process (POMDP) formulation is expensive to compute in general. On the other hand, in certain practical scenarios, formulations other than the classical POMDP make a lot of sense and can provide flexibility in balancing efficiency and correctness. This article considers a modified POMDP formulation that includes a Boolean objective, namely safe reachability. This article uses the notion of a partial conditional plan. Rather than explicitly enumerating all possible observations to construct a full conditional plan, this work samples a subset of all observations to ensure bounded replanning probability. Our theoretical and empirical results show that the failure rate of the constructed partial conditional plan is bounded by the replanning probability. Moreover, these partial conditional plans can be cached to further improve the performance. Our results suggest that for domains where replanning is easy, increasing the replanning probability bound usually leads to better scalability, and for domains where replanning is difficult or impossible in some states, we can decrease the bound and allocate more computation time to achieve a higher success rate. Hence, in certain cases, the practitioner can take advantage of their knowledge of the problem domain to scale to larger problems. Preliminary physical experiments suggest that this approach is applicable to real-world robotic domains, but it requires a discrete representation of the workspace. How to deal with continuous workspace directly is an interesting future direction.

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.

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.

BACKGROUND: The rapid growth of available knowledge on metabolic processes across thousands of species continues to expand the possibilities of producing chemicals by combining pathways found in different species. Several computational search algorithms have been developed for automating the identification of possible heterologous pathways; however, these searches may return thousands of pathway results. Although the large number of results are in part due to the large number of possible compounds and reactions, a subset of core reaction modules is repeatedly observed in pathway results across multiple searches, suggesting that some subpaths between common compounds were more consistently explored than others.To reduce the resources spent on searching the same metabolic space, a new meta-algorithm for metabolic pathfinding, Hub Pathway search with Atom Tracking (HPAT), was developed to take advantage of a precomputed network of subpath modules. To investigate the efficacy of this method, we created a table describing a network of common hub metabolites and how they are biochemically connected and only offloaded searches to and from this hub network onto an interactive webserver capable of visualizing the resulting pathways. RESULTS: A test set of nineteen known pathways taken from literature and metabolic databases were used to evaluate if HPAT was capable of identifying known pathways. HPAT found the exact pathway for eleven of the nineteen test cases using a diverse set of precomputed subpaths, whereas a comparable pathfinding search algorithm that does not use precomputed subpaths found only seven of the nineteen test cases. The capability of HPAT to find novel pathways was demonstrated by its ability to identify novel 3-hydroxypropanoate (3-HP) synthesis pathways. As for pathway visualization, the new interactive pathway filters enable a reduction of the number of displayed pathways from hundreds down to less than ten pathways in several test cases, illustrating their utility in reducing the amount of presented information while retaining pathways of interest. CONCLUSIONS: This work presents the first step in incorporating a precomputed subpath network into metabolic pathfinding and demonstrates how this leads to a concise, interactive visualization of pathway results. The modular nature of metabolic pathways is exploited to facilitate efficient discovery of alternate pathways.

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.

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.

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.

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.

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.

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.

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.

This paper introduces a motion-planning framework for a hybrid system with general continuous dynamics to satisfy a temporal logic specification consisting of cosafety and safety components in a partially unknown environment. The framework employs a multilayered synergistic planner to generate trajectories that satisfy the specification and adopt an iterative replanning strategy to deal with unknown obstacles. When the discovery of an obstacle renders the specification unsatisfiable, a division between the constraints in the specification is considered. The cosafety component of the specification is treated as a soft constraint, whose partial satisfaction is allowed, while the safety component is viewed as a hard constraint, whose violation is forbidden. To partially satisfy the cosafety component, inspirations are taken from indoor-robotic scenarios, and three types of (unexpressed) restrictions on the ordering of subtasks in the specification are considered. For each type, a partial satisfaction method is introduced, which guarantees the generation of trajectories that do not violate the safety constraints while attending to partially satisfying the cosafety requirements with respect to the chosen restriction type. The efficacy of the framework is illustrated through case studies on a hybrid car-like robot in an office environment.

The specification of complex motion goals through temporal logics is increasingly favored in robotics to narrow the gap between task and motion planning. A major limiting factor of such logics, however, is their Boolean satisfaction condition. To relax this limitation, we introduce a method for quantifying the satisfaction of co-safe linear temporal logic specifications, and propose a planner that uses this method to synthesize robot trajectories with the optimal satisfaction value. The method assigns costs to violations of specifications from user-defined proposition costs. These violation costs define a distance to satisfaction and can be computed algorithmically using a weighted automaton. The planner utilizes this automaton and an abstraction of the robotic system to construct a product graph that captures all possible robot trajectories and their distances to satisfaction. Then, a plan with the minimum distance to satisfaction is generated by employing this graph as the high-level planner in a synergistic planning framework. The efficacy of the method is illustrated on a robot with unsatisfiable specifications in an office environment.

It is well-known that inhibitors of protein kinases bind with very different selectivity profiles. This is also the case for inhibitors of many other protein families. A better understanding of binding selectivity would enhance the design of drugs that target only a subfamily, thereby minimizing possible side-effects. The increased availability of protein 3D structures has made it possible to study the structural variation within a given protein family. However, not every structural variation is related to binding specificity. We propose a greedy algorithm that computes a subset of residue positions in a multiple sequence alignment such that structural and chemical variation in those positions helps explain known binding affinities. By providing this information, the main purpose of the algorithm is to provide experimentalists with possible insights into how the selectivity profile of certain inhibitors is achieved, which is useful for lead optimization. In addition, the algorithm can also be used to predict binding affinities for structures whose affinity for a given inhibitor is unknown. The algorithm's performance is demonstrated using an extensive dataset for the human kinome, which includes a large and important set of drug targets. We show that the binding affinity of 38 different kinase inhibitors can be explained with consistently high precision and accuracy using the variation of at most six residue positions in the kinome binding site.

Sampling-based motion planning algorithms from the field of robotics have been very successful in exploring the conformational space of proteins. However, studying the flexibility of large proteins with hundreds or thousands of Degrees of Freedom (DoFs) remains a big challenge. Large proteins are also highly-constrained systems, which makes them more challenging for standard robotic approaches. So-called "expansive" motion planning algorithms were specifically developed to address highly-dimensional and highly-constrained problems. Many such planners employ a low-dimensional projection to estimate exploration coverage and direct their search based on this information. We believe that such a projection plays an essential role in the success of these planners. This paper shows how the low-dimensional projection used by expansive planners can be tailored with respect to a given molecular system to enhance the process of conformational sampling. We introduce a methodology to generate an expert projection using any available information about a given protein. We evaluate this methodology on several conformational search problems involving proteins with hundreds of DoFs. Our experiments demonstrate that incorporating expert knowledge into the projection can significantly benefit the exploration process.

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.

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.

Partially observable Markov decision processes (POMDPs) are used in many robotic task classes from soccer to household chores. Determining an approximately optimal action policy for POMDPs is PSPACE-complete, and the exponential growth of computation time prohibits solving large tasks. This paper describes two techniques to extend the range of robotic tasks that can be solved using a POMDP. Our first technique reduces the motion constraints of a robot and, then, uses state-of-the-art robotic motion planning techniques to respect the true motion constraints at runtime. We then propose a novel task decomposition that can be applied to some indoor robotic tasks. This decomposition transforms a long time horizon task into a set of shorter tasks. We empirically demonstrate the performance gain provided by these two techniques through simulated execution in a variety of environments. Comparing a direct formulation of a POMDP to solving our proposed reductions, we conclude that the techniques proposed in this paper can provide significant enhancement to current POMDP solution techniques, extending the POMDP instances that can be solved to include large continuous-state robotic tasks.

A framework capable of computing optimal control policies for a continuous system in the presence of both action and environment uncertainty is presented in this work. The framework decomposes the planning problem into two stages: an offline phase that reasons only over action uncertainty and an online phase that quickly reacts to the uncertain environment. Offline, a bounded-parameter Markov decision process (BMDP) is employed to model the evolution of the stochastic system over a discretization of the environment. Online, an optimal control policy over the BMDP is computed. Upon the discovery of an unknown environment feature during policy execution, the BMDP is updated and the optimal control policy is efficiently recomputed. Depending on the desired quality of the control policy, a suite of methods is presented to incorporate new information into the BMDP with varying degrees of detail online. Experiments confirm that the framework recomputes high-quality policies in seconds and is orders of magnitude faster than existing methods.

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.

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.

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.

This paper considers the problem of motion planning for a hybrid robotic system with complex and nonlinear dynamics in a partially unknown environment given a temporal logic specification. We employ a multi-layered synergistic framework that can deal with general robot dynamics and combine it with an iterative planning strategy. Our work allows us to deal with the unknown environmental restrictions only when they are discovered and without the need to repeat the computation that is related to the temporal logic specification. In addition, we define a metric for satisfaction of a specification. We use this metric to plan a trajectory that satisfies the specification as closely as possible in cases in which the discovered constraint in the environment renders the specification unsatisfiable. We demonstrate the efficacy of our framework on a simulation of a hybrid second-order car-like robot moving in an office environment with unknown obstacles. The results show that our framework is successful in generating a trajectory whose satisfaction measure of the specification is optimal. They also show that, when new obstacles are discovered, the reinitialization of our framework is computationally inexpensive.

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.

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.

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.

The protein kinases are a large family of enzymes that play fundamental roles in propagating signals within the cell. Because of the high degree of binding site similarity shared among protein kinases, designing drug compounds with high specificity among the kinases has proven difficult. However, computational approaches to comparing the 3-dimensional geometry and physicochemical properties of key binding site residue positions have been shown to be informative of inhibitor selectivity. The Combinatorial Clustering Of Residue Position Subsets (ccorps) method, introduced here, provides a semi-supervised learning approach for identifying structural features that are correlated with a given set of annotation labels. Here, ccorps is applied to the problem of identifying structural features of the kinase atp binding site that are informative of inhibitor binding. ccorps is demonstrated to make perfect or near-perfect predictions for the binding affinity profile of 8 of the 38 kinase inhibitors studied, while only having overall poor predictive ability for 1 of the 38 compounds. Additionally, ccorps is shown to identify shared structural features across phylogenetically diverse groups of kinases that are correlated with binding affinity for particular inhibitors; such instances of structural similarity among phylogenetically diverse kinases are also shown to not be rare among kinases. Finally, these function-specific structural features may serve as potential starting points for the development of highly specific kinase inhibitors.

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.

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.

This paper presents a kinodynamic motion planner, i.e., Kinodynamic Motion Planning by Interior-Exterior Cell Exploration (KPIECE), which is specifically designed for systems with complex dynamics, where integration backward in time is not possible, and speed of computation is important. A grid-based discretization is used to estimate the coverage of the state space. The coverage estimates help the planner detect the less-explored areas of the state space. An important characteristic of this discretization is that it keeps track of the boundary of the explored region of the state space and focuses exploration on the less covered parts of this boundary. Extensive experiments show that KPIECE provides significant computational gain over existing state-of-the-art methods and allows us to solve some harder, previously unsolvable problems. For some problems, KPIECE is shown to be up to two orders of magnitude faster than existing methods and use up to 40 times less memory. A shared memory parallel implementation is presented as well. This implementation provides better speedup than an embarrassingly parallel implementation by taking advantage of the evolving multicore technology.

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.

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.

SUMMARY: The LabelHash server and tools are designed for large-scale substructure comparison. The main use is to predict the function of unknown proteins. Given a set of (putative) functional residues, LabelHash finds all occurrences of matching substructures in the entire Protein Data Bank, along with a statistical significance estimate and known functional annotations for each match. The results can be downloaded for further analysis in any molecular viewer. For Chimera, there is a plugin to facilitate this process. AVAILABILITY: The web site is free and open to all users with no login requirements at http://labelhash.kavrakilab.org

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.

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.

MOTIVATION: Finding novel or non-standard metabolic pathways, possibly spanning multiple species, has important applications in fields such as metabolic engineering, metabolic network analysis and metabolic network reconstruction. Traditionally, this has been a manual process, but the large volume of metabolic data now available has created a need for computational tools to automatically identify biologically relevant pathways. RESULTS: We present new algorithms for finding metabolic pathways, given a desired start and target compound, that conserve a given number of atoms by tracking the movement of atoms through metabolic networks containing thousands of compounds and reactions. First, we describe an algorithm that identifies linear pathways. We then present a new algorithm for finding branched metabolic pathways. Comparisons to known metabolic pathways demonstrate that atom tracking enables our algorithms to avoid many unrealistic connections, often found in previous approaches, and return biologically meaningful pathways. Our results also demonstrate the potential of the algorithms to find novel or non-standard pathways that may span multiple organisms. AVAILABILITY: The software is freely available for academic use at: http://www.kavrakilab.org/atommetanet. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

BACKGROUND: Structural variations caused by a wide range of physico-chemical and biological sources directly influence the function of a protein. For enzymatic proteins, the structure and chemistry of the catalytic binding site residues can be loosely defined as a substructure of the protein. Comparative analysis of drug-receptor substructures across and within species has been used for lead evaluation. Substructure-level similarity between the binding sites of functionally similar proteins has also been used to identify instances of convergent evolution among proteins. In functionally homologous protein families, shared chemistry and geometry at catalytic sites provide a common, local point of comparison among proteins that may differ significantly at the sequence, fold, or domain topology levels. RESULTS: This paper describes two key results that can be used separately or in combination for protein function analysis. The Family-wise Analysis of SubStructural Templates (FASST) method uses all-against-all substructure comparison to determine Substructural Clusters (SCs). SCs characterize the binding site substructural variation within a protein family. In this paper we focus on examples of automatically determined SCs that can be linked to phylogenetic distance between family members, segregation by conformation, and organization by homology among convergent protein lineages. The Motif Ensemble Statistical Hypothesis (MESH) framework constructs a representative motif for each protein cluster among the SCs determined by FASST to build motif ensembles that are shown through a series of function prediction experiments to improve the function prediction power of existing motifs. CONCLUSIONS: FASST contributes a critical feedback and assessment step to existing binding site substructure identification methods and can be used for the thorough investigation of structure-function relationships. The application of MESH allows for an automated, statistically rigorous procedure for incorporating structural variation data into protein function prediction pipelines. Our work provides an unbiased, automated assessment of the structural variability of identified binding site substructures among protein structure families and a technique for exploring the relation of substructural variation to protein function. As available proteomic data continues to expand, the techniques proposed will be indispensable for the large-scale analysis and interpretation of structural data.

BACKGROUND: There is an increasing number of proteins with known structure but unknown function. Determining their function would have a significant impact on understanding diseases and designing new therapeutics. However, experimental protein function determination is expensive and very time-consuming. Computational methods can facilitate function determination by identifying proteins that have high structural and chemical similarity. RESULTS: We present LabelHash, a novel algorithm for matching substructural motifs to large collections of protein structures. The algorithm consists of two phases. In the first phase the proteins are preprocessed in a fashion that allows for instant lookup of partial matches to any motif. In the second phase, partial matches for a given motif are expanded to complete matches. The general applicability of the algorithm is demonstrated with three different case studies. First, we show that we can accurately identify members of the enolase superfamily with a single motif. Next, we demonstrate how LabelHash can complement SOIPPA, an algorithm for motif identification and pairwise substructure alignment. Finally, a large collection of Catalytic Site Atlas motifs is used to benchmark the performance of the algorithm. LabelHash runs very efficiently in parallel; matching a motif against all proteins in the 95% sequence identity filtered non-redundant Protein Data Bank typically takes no more than a few minutes. The LabelHash algorithm is available through a web server and as a suite of standalone programs at http://labelhash.kavrakilab.org. The output of the LabelHash algorithm can be further analyzed with Chimera through a plugin that we developed for this purpose. CONCLUSIONS: LabelHash is an efficient, versatile algorithm for large-scale substructure matching. When LabelHash is running in parallel, motifs can typically be matched against the entire PDB on the order of minutes. The algorithm is able to identify functional homologs beyond the twilight zone of sequence identity and even beyond fold similarity. The three case studies presented in this paper illustrate the versatility of the algorithm.

To efficiently solve challenges related to motion-planning problems with dynamics, this paper proposes treating motion planning not just as a search problem in a continuous space but as a search problem in a hybrid space consisting of discrete and continuous components. A multilayered framework is presented which combines discrete search and sampling-based motion planning. This framework is called synergistic combination of layers of planning ( SyCLoP) hereafter. Discrete search uses a workspace decomposition to compute leads, i.e., sequences of regions in the neighborhood that guide sampling-based motion planning during the state-space exploration. In return, information gathered by motion planning, such as progress made, is fed back to the discrete search. This combination allows SyCLoP to identify new directions to lead the exploration toward the goal, making it possible to efficiently find solutions, even when other planners get stuck. Simulation experiments with dynamical models of ground and flying vehicles demonstrate that the combination of discrete search and motion planning in SyCLoP offers significant advantages. In fact, speedups of up to two orders of magnitude were obtained for all the sampling-based motion planners used as the continuous layer of SyCLoP.

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.

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.

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.

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.

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.

BACKGROUND: Structural genomics projects such as the Protein Structure Initiative (PSI) yield many new structures, but often these have no known molecular functions. One approach to recover this information is to use 3D templates - structure-function motifs that consist of a few functionally critical amino acids and may suggest functional similarity when geometrically matched to other structures. Since experimentally determined functional sites are not common enough to define 3D templates on a large scale, this work tests a computational strategy to select relevant residues for 3D templates. RESULTS: Based on evolutionary information and heuristics, an Evolutionary Trace Annotation (ETA) pipeline built templates for 98 enzymes, half taken from the PSI, and sought matches in a non-redundant structure database. On average each template matched 2.7 distinct proteins, of which 2.0 share the first three Enzyme Commission digits as the template's enzyme of origin. In many cases (61%) a single most likely function could be predicted as the annotation with the most matches, and in these cases such a plurality vote identified the correct function with 87% accuracy. ETA was also found to be complementary to sequence homology-based annotations. When matches are required to both geometrically match the 3D template and to be sequence homologs found by BLAST or PSI-BLAST, the annotation accuracy is greater than either method alone, especially in the region of lower sequence identity where homology-based annotations are least reliable. CONCLUSION: These data suggest that knowledge of evolutionarily important residues improves functional annotation among distant enzyme homologs. Since, unlike other 3D template approaches, the ETA method bypasses the need for experimental knowledge of the catalytic mechanism, it should prove a useful, large scale, and general adjunct to combine with other methods to decipher protein function in the structural proteome.

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

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 (OOPSMP), 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

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.

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.

Nonlinear dimensionality reduction methods often rely on the nearest-neighbors graph to extract low-dimensional embeddings that reliably capture the underlying structure of high-dimensional data. Research however has shown that computing nearest neighbors of a point from a high-dimensional data set generally requires time proportional to the size of the data set itself, rendering the computation of the nearest-neighbors graph prohibitively expensive.

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

We present a new approach to path planning for deformable linear (one-dimensional) objects such as flexible wires. We introduce a method for efficiently computing stable configurations of a wire subject to manipulation constraints. These configurations correspond to minimal-energy curves. By restricting the planner to minimal-energy curves, the execution of a path becomes easier. Our curve 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. This planner can be used as a powerful local planner in a sampling-based roadmap method. This makes it possible to compute a roadmap of the entire "shape space," which is not possible with previous approaches. 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 cable routing, and motion planning for surgical suturing and snake-like robots

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.

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.

MOTIVATION: Conformational searches in molecular docking are a time-consuming process with wide range of applications. Favorable conformations of the ligands that successfully bind with receptors are sought to form stable ligand-receptor complexes. Usually a large number of conformations are generated and their binding energies are examined. We propose adding a geometric screening phase before an energy minimization procedure so that only conformations that geometrically fit in the binding site will be prompted for energy calculation. RESULTS: Geometric screening can drastically reduce the number of conformations to be examined from millions (or higher) to thousands (or lower). The method can also handle cases when there are more variables than geometric constraints. An early-stage implementation is able to finish the geometric filtering of conformations for molecules with up to nine variables in 1 min. To the best of our knowledge, this is the first time such results are reported deterministically. CONTACT: [email protected].

This paper shows how to effectively combine a sampling-based method primarily designed for multiple-query motion planning [probabilistic roadmap method (PRM)] with sampling-based tree methods primarily designed for single-query motion planning (expansive space trees, rapidly exploring random trees, and others) in a novel planning framework that can be efficiently parallelized. Our planner not only achieves a smooth spectrum between multiple-query and single-query planning, but it combines advantages of both. We present experiments which show that our planner is capable of solving problems that cannot be addressed efficiently with PRM or single-query planners. A key advantage of our planner is that it is significantly more decoupled than PRM and sampling-based tree planners. Exploiting this property, we designed and implemented a parallel version of our planner. Our experiments show that our planner distributes well and can easily solve high-dimensional problems that exhaust resources available to single machines and cannot be addressed with existing planners.

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.

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.

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.

We demonstrate a system built using probabilistic techniques that allows for remarkably accurate localization across our entire office building using nothing more than the built-in signal intensity meter supplied by standard 802.11 cards. While prior systems have required significant investments of human labor to build a detailed signal map, we can train our system by spending less than one minute per office or region, walking around with a laptop and recording the observed signal intensities of our building's unmodified base stations. We actually collected over two minutes of data per office or region, about 28 man-hours of effort. Using less than half of this data to train the localizer, we can localize a user to the precise, correct location in over 95% of our attempts, across the entire building. Even in the most pathological cases, we almost never localize a user any more distant than to the neighboring office. A user can obtain this level of accuracy with only two or three signal intensity measurements, allowing for a high frame rate of localization results. Furthermore, with a brief calibration period, our system can be adapted to work with previously unknown user hardware. We present results demonstrating the robustness of our system against a variety of untrained time-varying phenomena, including the presence or absence of people in the building across the day. Our system is sufficiently robust to enable a variety of location-aware applications without requiring special-purpose hardware or complicated training and calibration procedures.

IEEE 802.11b wireless Ethernet is becoming the standard for indoor wireless communication. This paper proposes the use of measured signal strength of Ethernet packets as a sensor for a localization system. We demonstrate that off-the-shelf hardware can accurately be used for location sensing and real-time tracking by applying a Bayesian localization framework.

This paper presents a 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 on the expected number iterations of PRM required to find a path, in terms of the number of intermediate points and the probability of choosing a point from a certain set. Explicit geometric assumptions are not necessary to complete this analysis. As a result, the analysis provides some unification of previous work. We provide an upper bound which could be refined using details specific to a given problem. This bound is of the same form as that proved in previous analyses, but has simpler prerequisites and is proved on a more general class of problems. Using our framework, we analyze some new path-planning problems, 2k-degree-of-freedom kinodynamic point robots, polygonal robots with contact, and deformable robots with force field control. These examples make explicit use of generality in our approach that did not exist in previous frameworks.

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.

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.

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.

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.

A key subproblem in the construction of location-aware systems is the determination of the position of a mobile device. This paper describes the design, implementation and analysis of a system for determining position inside a building from measured RF signal strengths of packets on an IEEE 802.11b wireless Ethernet network. Previous approaches to location awareness with RF signals have been severely hampered by non-linearity, noise and complex correlations due to multi-path effects, interference and absorption. The design of our system begins with the observation that determining position from complex, noisy and non-linear signals is a well-studied problem in the field of robotics. Using only off-the-shelf hardware, we achieve robust position estimation to within a meter in our experimental context and after adequate training of our system. We can also coarsely determine our orientation and can track our position as we move. By applying recent advances in probabilistic inference of position and sensor fusion from noisy signals, we show that the RF emissions from base stations as measured by off-the-shelf wireless Ethernet cards are sufficiently rich in information to permit a mobile device to reliably track its location.

Proteins are involved either directly or indirectly in all biological processes in living organisms. It is now widely accepted that conformational changes of proteins can critically affect their ability to bind other molecules and that any progress in modeling protein motion and flexibility will contribute to the understanding of key biological functions. However, modeling protein flexibility has proven a very difficult task. Experimental laboratory methods such as X-ray crystallography produce rather few structures, while computational methods such as Molecular Dynamics are too slow for routine use with large systems. A medium sized protein typically has a few thousands of degrees of freedom. This paper shows how to obtain a reduced basis representation of protein flexibility. We use the Principal Component Analysis method, a dimensionality reduction technique, to transform the original high dimensional representation of protein motion into a lower dimensional representation that captures the dominant modes of motions of the protein. Although there is inevitably some loss in accuracy, we show that we can obtain conformations that have been observed in laboratory experiments, starting from different initial conformations and working in a drastically reduced search space.

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.

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.

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.

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.

We extend randomized path planning algorithms to the case of articulated robots that have closed kinematic chains. This is an important class of problems, which includes applications such as manipulation planning using multiple open-chain manipulators that cooperatively grasp an object and planning for reconfigurable robots in which links might be arranged in a loop to ease manipulation or locomotion. Applications also exist in areas beyond robotics, including computer graphics, computational chemistry, and virtual prototyping. Such applications typically involve high degrees of freedom and a parameterization of the configurations that satisfy closure constraints is usually not available. We show how to implement key primitive operations of randomized path planners for general closed kinematics chains. These primitives include the generation of random free configurations and the generation of local paths. To demonstrate the feasibility of our primitives for general chains, we show their application to recently developed randomized planners and present computed results for high-dimensional problems.

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.

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.

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.

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.

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.

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.

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.

Programmable force fields are a representation of a class of devices for distributed, nonprehensile manipulation for applications in parts feeding, sorting, positioning, and assembly. They generate force vector fields in which the parts move until they reach a stable equilibrium pose. Research has yielded open-loop strategies to uniquely position, orient, and sort parts. These strategies typically consist of several fields employed in sequence to achieve a desired final pose. The length of the sequence depends on the complexity of the part. We show that unique part poses can be achieved with just one field. First, we exhibit a single field that positions and orients any part (except certain symmetric parts) into two stable equilibrium poses. Then, we show that for any part there exists a field in which the part reaches a unique stable equilibrium pose (again, except for symmetric parts). Besides giving an optimal upper bound for unique parts positioning and orientation, our work gives further evidence that programmable force fields are a powerful tool for parts manipulation. Our second result also leads to the design of "universal parts feeders", proving an earlier conjecture about their existence. We argue that universal parts feeders are relatively easy to build, and we report on extensive simulation results which indicate that these devices may work very well in practice. We believe that the results in this paper could be the basis for a new generation of efficient, open-loop, parallel parts feeders.

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.

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.

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.

Computational tools have greatly expedited the pharmaceutical drug design process in recent years. One common task in this process is the search of a large library for small molecules that can achieve both a low-energy conformation and a prescribed pharmacophore. The pharmacophore expresses constraints on the 3D structure of the molecule by specifying relative atom positions that should be maintained to increase the likelihood that the molecule will bind with the receptor site. This paper presents a pharmacophore-based database screening system that has been designed, implemented, and tested on a molecular database. The key ingredient in this system is a simple, randomized conformational search technique that attempts to simultaneously reduce energy and maintain pharmacophore constraints. This enables efficient identification of molecules in a database that are likely to dock with a given protein, which can serve as a powerful aid in the search for better drug candidates.

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.

This paper describes a randomized approach for finding invari-ants in a set of flexible ligands (drug molecules) that underlies an integrated software system called RAPID currently under development. An invariant is a collection of features embed-ded in <3 which is present in one or more of the possible low-energy conformations of each ligand. Such invariants of chemically distinct molecules are useful for computational chemists since they may represent candidate pharmacophores. A pharmacophore contains the parts of the ligand that are pri-marily responsible for its interaction and binding with a specific receptor. It is regarded as an inverse image of a receptor and is used as a template for building more effective pharmaceutical drugs. The identification of pharmacophores is crucial in drug design since the structure of the targeted receptor is frequently unknown, but a number of molecules that interact with the receptor have been discovered by experiments. It is expected that our techniques and the results produced by our system will prove useful in other applications such as molecular database screening and comparative molecular field analysis.

The subject of this paper is the analysis of a randomized preprocessing scheme that has been used for query processing in robot path planning. The attractiveness of the scheme stems from its general applicability to virtually any path-planning problem, and its empirically observed success. In this paper we initiate a theoretical basis for explaining this empirical success. Under a simple assumption about the configuration space, we show that it is possible to perform preprocessing following which queries can be answered quickly. En route, we consider related problems on graph connectivity in the evasiveness model and art-gallery theorems.

We provide 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: 1) the length of /spl gamma/; 2) the distance function of /spl gamma/ from the obstacles; 3) 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.

This paper describes a randomized approach for finding invariant in a set of flexible Iigands (drug molecules) that underlies an integrated software system called RAPID currently underdevelopment.An invariant is a collection of features embedded in 3?3 which is present in one or more of the possible low-energy conformations of each Iigand.Such invariants of chemically distinct molecules are useful for computational chemists since they may represent candidate pharmacophores.A pharmacophore contains the parts of the Iigand that are primarily responsible for its interaction and binding with a specific receptor.It is regarded as an inverse image of a receptor and is used as a template for building more effective pharmaceutical drugs.The identification of pharmacophores is crucial in drug design since the structure of the targeted receptor is frequently unknown, but a number of molecules that interact with the receptor have been discovered by experiments.It is expected that our techniques and the results produced by our system will prove useful in other applications such as molecular database screening and comparative molecular field analysis.

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.

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.

A new motion planning method for robots in static workspaces is presented. This method proceeds in two phases: a learning phase and a query phase. In the learning phase, a probabilistic roadmap is constructed and stored as a graph whose nodes correspond to collision-free configurations and whose edges correspond to feasible paths between these configurations. These paths are computed using a simple and fast local planner. In the query phase, any given start and goal configurations of the robot are connected to two nodes of the roadmap; the roadmap is then searched for a path joining these two nodes. The method is general and easy to implement. It can be applied to virtually any type of holonomic robot. It requires selecting certain parameters (e.g., the duration of the learning phase) whose values depend on the scene, that is the robot and its workspace. But these values turn out to be relatively easy to choose, Increased efficiency can also be achieved by tailoring some components of the method (e.g., the local planner) to the considered robots. In this paper the method is applied to planar articulated robots with many degrees of freedom. Experimental results show that path planning can be done in a fraction of a second on a contemporary workstation (/spl ap/150 MIPS), after learning for relatively short periods of time (a few dozen seconds).

The subject of this paper is the analysis of a randomized preprocessing scheme that has been used for query processing in robot path planning. The attractiveness of the scheme stems from its general applicability to virtually any path-planning problem, and its empirically observed success. In this paper we initiate a theoretical basis for explaining this empirical success. Under a simple assumption about the configuration space, we show that it is possible to perform preprocessing following which queries can be answered quickly. En route, we consider related problems on graph connectivity in the evasiveness model, and art-gallery theorems. Robotics Laboratory, Department of Computer Science, Stanford University, Stanford, CA 94305-2140. Partially supported by ARPA grant N00014-92-J-1809 and ONR grant N00014-94-1-0721. y Department of Computer Science, Stanford University, Stanford, CA 94305-2140. Supported by an Alfred P. Sloan Research Fellowship, an IBM Faculty Development Award,...

This paper presents a new method for computing the configuration-space map of obstacles that is used in motion-planning algorithms. The method derives from the observation that, when the robot is a rigid object that can only translate, the configuration space is a convolution of the workspace and the robot. This convolution is computed with the use of the fast Fourier transform (FFT) algorithm. The method is particularly promising for workspaces with many and/or complicated obstacles, or when the shape of the robot is not simple. It is an inherently parallel method that can significantly benefit from existing experience and hardware on the FFT.>

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.>

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.>

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.>