This paper investigates an object detection problem using a mobile robot equipped with a vision sensor. The main novelty of this work is an approach that combines localization of the robot relative to an object believed to be the target and confirmation of this object's identity. Since the position of the robot relative to the candidate target is never exactly known, we model this position by a probability distribution over a set of cells forming a decomposition of the workspace around the candidate target. By performing a series of moves the robot acquires several images and runs a target detector module on each image. Its goal is not only to reach a position where the target detector can confirm the target with high confidence (as this approach would be prone to false positives). It is also to reach a position where, with high probability, the target detector will confirm with high confidence that the candidate target is actually the target. This twofold goal reduces drastically the likelihood of false positives. The target confirmation problem is modeled as a Partially-Observable Markov Decision Process (POMDP), which is solved using Stochastic Dynamic Programming (SDP).

ABSTRACT Building occupants perceive information about the surrounding environment and navigate for safety during emergency evacuation (egress). They often choose their actions by interacting with their social groups and observing the actions of the surrounding crowd. Most egress simulators, however, ignore individuals' crowd perceptions and social interactions. This paper presents a novel platform, SAFEgress (Social Agent For Egress), in which building occupants are modeled as agents who decide their evacuation actions on the basis of their knowledge of the building and their interactions with the social groups and the neighboring crowd. Results from the SAFEgress prototype show that both agents' familiarity with the building and social influence can significantly impact egress performance. By simulating different occupants' behaviors, architects and facility managers may better understand the influence of human and social factors on evacuation and consequently design safer buildings and egress procedures. Copyright © 2014 John Wiley & Sons, Ltd.

BACKGROUND: Hydrogen bonds (H-bonds) play a key role in both the formation and stabilization of protein structures. They form and break while a protein deforms, for instance during the transition from a non-functional to a functional state. The intrinsic strength of an individual H-bond has been studied from an energetic viewpoint, but energy alone may not be a very good predictor. METHODS: This paper describes inductive learning methods to train protein-independent probabilistic models of H-bond stability from molecular dynamics (MD) simulation trajectories of various proteins. The training data contains 32 input attributes (predictors) that describe an H-bond and its local environment in a conformation c and the output attribute is the probability that the H-bond will be present in an arbitrary conformation of this protein achievable from c within a time duration Δ. We model dependence of the output variable on the predictors by a regression tree. RESULTS: Several models are built using 6 MD simulation trajectories containing over 4000 distinct H-bonds (millions of occurrences). Experimental results demonstrate that such models can predict H-bond stability quite well. They perform roughly 20% better than models based on H-bond energy alone. In addition, they can accurately identify a large fraction of the least stable H-bonds in a conformation. In most tests, about 80% of the 10% H-bonds predicted as the least stable are actually among the 10% truly least stable. The important attributes identified during the tree construction are consistent with previous findings. CONCLUSIONS: We use inductive learning methods to build protein-independent probabilistic models to study H-bond stability, and demonstrate that the models perform better than H-bond energy alone.

Molecular dynamics (MD) simulation is a well-established method for studying protein motion at the atomic scale. However, it is computationally intensive and generates massive amounts of data. One way of addressing the dual challenges of computation efficiency and data analysis is to construct simplified models of long-timescale protein motion from MD simulation data. In this direction, we propose to use Markov models with hidden states, in which the Markovian states represent potentially overlapping probabilistic distributions over protein conformations. We also propose a principled criterion for evaluating the quality of a model by its ability to predict long-timescale protein motions. Our method was tested on 2D synthetic energy landscapes and two extensively studied peptides, alanine dipeptide and the villin headpiece subdomain (HP-35 NleNle). One interesting finding is that although a widely accepted model of alanine dipeptide contains six states, a simpler model with only three states is equally good for predicting long-timescale motions. We also used the constructed Markov models to estimate important kinetic and dynamic quantities for protein folding, in particular, mean first-passage time. The results are consistent with available experimental measurements.

We report our first experiences with Leaving Flatland, an exploratory project that studies the key challenges of closing the loop between autonomous perception and action on challenging terrain. We propose a comprehensive system for localization, mapping, and planning for the RHex mobile robot in fully 3D indoor and outdoor environments. This system integrates Visual Odometry-based localization with new techniques in real-time 3D mapping from stereo data. The motion planner uses a new decomposition approach to adapt existing 2D planning techniques to operate in 3D terrain. We test the map-building and motion-planning subsystems on real and synthetic data, and show that they have favorable computational performance for use in high-speed autonomous navigation.

Cognitive informatics (CI) is the transdisciplinary enquiry of cognitive and information sciences that investigates into the internal information processing mechanisms and processes of the brain and natural intelligence, and their engineering applications via an interdisciplinary approach. CI develops a coherent set of fundamental theories and denotational mathematics, which form the foundation for most information and knowledge based science and engineering disciplines such as computer science, cognitive science, neuropsychology, systems science, cybernetics, software engineering, knowledge engineering, and computational intelligence. This paper reviews the central doctrine of CI and its applications. The theoretical framework of CI is described on the architecture of CI and its denotational mathematic means. A set of theories and formal models of CI is presented in order to explore the natural and computational intelligence. A wide range of applications of CI are described in the areas of cognitive computers, cognitive properties of knowledge, simulations of human cognitive behaviors, cognitive complexity of software, autonomous agent systems, and computational intelligence.

Several applications in biology - e.g., incorporation of protein flexibility in ligand docking algorithms, interpretation of fuzzy X-ray crystallographic data, and homology modeling - require computing the internal parameters of a flexible fragment (usually, a loop) of a protein in order to connect its termini to the rest of the protein without causing any steric clash. One must often sample many such conformations in order to explore and adequately represent the conformational range of the studied loop. While sampling must be fast, it is made difficult by the fact that two conflicting constraints - kinematic closure and clash avoidance - must be satisfied concurrently. This paper describes two efficient and complementary sampling algorithms to explore the space of closed clash-free conformations of a flexible protein loop. The "seed sampling" algorithm samples broadly from this space, while the "deformation sampling" algorithm uses seed conformations as starting points to explore the conformation space around them at a finer grain. Computational results are presented for various loops ranging from 5 to 25 residues. More specific results also show that the combination of the sampling algorithms with a functional site prediction software (FEATURE) makes it possible to compute and recognize calcium-binding loop conformations. The sampling algorithms are implemented in a toolkit (LoopTK), which is available at https://simtk.org/home/looptk.

Free-space dilation is an effective approach for narrow passage sampling, a well-recognized difficulty in probabilistic roadmap (PRM) planning. Key to this approach are methods for dilating the free space and for determining the amount of dilation needed. This paper presents a new method of dilation by shrinking the geometric models of robots and obstacles. Compared with existing work, the new method is more efficient in both running time and memory usage. It is also integrated with collision checking, a key operation in PRM planning. The efficiency of the dilation method enables a new PRM planner which quickly constructs a series of dilated free spaces and automatically determine the amount of dilation needed. Experiments show that both the dilation method and the planner work well in complex geometric environments. In particular, the planner reliably solved the most difficult version of the alpha puzzle, a benchmark test for PRM planners

This paper presents a method of generating natural-looking motion primitives for humanoid robots. An optimization-based approach is used to generate these primitives, but the objective function is tailored to each one and complexity is reduced by identifying relevant degrees of freedom. Several examples are shown in simulation: for an arm movement to reach an object, it is better to minimize the acceleration of key parts of the robot over its entire trajectory; for a single step on flat ground, it is better to minimize the torque and instantaneous angular momentum at every posture. The primitives are precomputed off-line, but might be used by on-line planner either to provide a fixed set of maneuvers or to bias a probabilistic, sample-based search for motions

Probabilistic sampling-based motion planners are unable to detect when no feasible path exists. A common heuristic is to declare a query infeasible if a path is not found in a fixed amount of time. In applications where many queries must be processed – for instance, robotic manipulation, multi-limbed locomotion, and contact motion – a critical question arises: what should this time limit be? This paper presents a machine-learning approach to deal with this question. In an off-line learning phase, a classifier is trained to quickly predict the feasibility of a query. Then, an improved multi-step motion planning algorithm uses this classifier to avoid wasting time on infeasible queries. This approach has been successfully demonstrated in simulation on a four-limbed, free-climbing robot.

The efficiency of probabilistic roadmap (PRM) planners drops dramatically in spaces with narrow passages. This paper presents a new method - small-step retraction - that helps PRM planners find paths through such passages. The method consists of slightly fattening the robot's free space, constructing a roadmap in the fattened free space, and repairing colliding portions of this roadmap by retracting them out of collision. The fattened free space is not explicitly computed. Instead, the robot links and/or obstacles are thinned around their medial axis. A robot configuration lies in fattened free space if the thinned objects do not collide at this configuration. Two repair strategies are used. The "optimist" strategy waits until a complete path has been found in fattened free space before repairing it. The "pessimist" strategy repairs the roadmap as it is being built. The former is faster, but the latter is more reliable. A simple combination yields an integrated planner that is both fast and reliable.

Static collision checking amounts to testing a given configuration of objects for overlaps. In contrast, the goal of dynamic checking is to determine whether all configurations along a continuous path are collision-free. While there exist effective methods for static collision detection, dynamic checking still lacks methods that are both reliable and efficient. A common approach is to sample paths at some fixed, prespecified resolution and statically test each sampled configuration. But this approach is not guaranteed to detect collision whenever one occurs, and trying to increase its reliability by refining the sampling resolution along the entire path results in slow checking. This paper introduces a new method for testing path segments in c-space or collections of such segments, that is both reliable and efficient. This method locally adjusts the sampling resolution by comparing lower bounds on distances between objects in relative motion with upper bounds on lengths of curves traced by points of these moving objects. Several additional techniques and heuristics increase the checker's efficiency in scenarios with many moving objects (e.g., articulated arms and/or multiple robots) and high geometric complexity. The new method is general, but particularly well suited for use in probabilistic roadmap (PRM) planners, where it is critical to determine as quickly as possible whether given path segments collide, or not. Extensive tests, in particular on randomly generated path segments and on multisegment paths produced by PRM planners, show that the new method compares favorably with a fixed-resolution approach at "suitable" resolution, with the enormous advantage that it never fails to detect collision.

This paper presents a general framework for planning the quasi-static motion of a three-limbed climbing robot in vertical natural terrain. The problem is to generate a sequence of continuous one-step motions between consecutive holds that will allow the robot to reach a particular goal hold. A detailed algorithm is presented to compute a one-step motion considering the equilibrium constraint only. The overall framework combines this local planner with a heuristic search technique to generate a complete plan. An online implementation of the algorithm is demonstrated in simulation.

A new motion planning framework is presented that enables multiple mobile robots with limited ranges of sensing and communication to maneuver and achieve goals safely in dynamic environments. To combine the respective advantages of centralized and de-centralized planning, this framework is based on the concept of centralized planning within dynamic robot networks. As the robots move in their environment, localized robot groups form networks, within which world models and robot goals can be shared. Whenever a network is formed, new information then becomes available to all robots in this network. With this new information, each robot uses a fast, centralized planner to compute new coordinated trajectories on the fly. Planning over several robot networks is decentralized and distributed. Both simulated and real-robot experiments have validated the approach.

This paper considers the following multi-goal motion planning problem: a robot arm must reach several goal configurations in some sequence, but this sequence is not given. Instead, the robot's planner must compute an optimal or near-optimal path through the goals. This problem occurs, for instance, in spot-welding, inspection, and measurement tasks. It combines two computationally hard sub-problems: the shortest-path and traveling-salesman problems. This paper describes a greedy algorithm that operates under the assumption that the number of goals is relatively small (a few dozen at most) and the computational cost of finding a good path between two goals dominates that of finding a good tour in a graph with edges of given costs. Although the algorithm computes a quadratic number of goal-to-goal paths in the worst case, it is much faster in practice.

The kinematic chain is a ubiquitous and extensively studied representation in robotics as well as a useful model for studying the motion of biological macro-molecules. Both fields stand to benefit from algorithms for efficient maintenance and collision detection in such chains. This paper introduces a novel hierarchical representation of a kinematic chain allowing for efficient incremental updates and relative position calculation. A hierarchy of oriented bounding boxes is superimposed on this representation, enabling high performance collision detection, self-collision testing, and distance computation. This representation has immediate applications in the field of molecular biology, for speeding up molecular simulations and studies of folding paths of proteins. It could be instrumental in path planning applications for robots with many degrees of freedom, also known as hyper-redundant robots. A comparison of the performance of the algorithm with the current state of the art in collision detection is presented for a number of benchmarks.

This paper describes a new approach to keep a moving target into the field of view of a robot, despite obstacles. Unlike previous work, this approach does not assume that a complete or partial model of the target's behavior is available, nor that a map of the obstacles is given. At approximately 10 IIz, the robot constructs a local map of the environment from range data, localizes the target in this map, and computes its new velocity command. This command is selected to minimize a function that measures the risk that the target may escape the robot's field of view by crossing an occlusion ray created by an obstacle. The risk function defined in this paper combines a reactive term, whose minimization handles immediate threats, and a look-ahead term, whose minimization improves the robot's future ability to react to evading motions of the target. The experimental robotic system has been remarkably successful at tracking a target performing brisk maneuvers and swift turns behind obstacles.

Many applications require continuous monitoring of a moving target by a controllable vision system. Although the goal of tracking objects is not new, traditional techniques usually ignore the presence of obstacles and focus on imaging and target recognition issues. For a target moving among obstacles, the goal of tracking involves a complex motion problem: a controllable observer must anticipate that the target may become occluded by an obstacle and move to prevent such an event from occurring. The paper describes a strategy for computing the motions of a mobile robot operating in a 2-D workspace without prior knowledge of the target's intention or the distribution of obstacles in the scene. The proposed algorithm governs the motion of the observer based on current measurements of the target's position and the location of the local obstacles. The approach is combinatorial in the sense that the algorithm explicitly computes a description of the geometric arrangement between the target and the observer's visibility region produced by the local obstacles. The algorithm computes a continuous control law based on this description. The new tracking strategy has been implemented in a real-time robotic system.

Real-time surgical simulation often requires computing the deformations of visco-elastic human-body tissue and generating both graphic and haptic renderings. As human users are more sensitive to small haptic discrepancies than visual ones, good force rendering requires a refresh rate of 500 Hz or more, which is far beyond the capabilities of current simulators. Moreover, if the simulator runs on a remote server, limited bandwidth, network latency and variance further compromise the quality of haptic rendering. To address these problems, a new interpolation-extrapolation data structure called the forcegrid is proposed, which makes it possible to approximate forces at rates greater than 500 Hz, regardless of the complexity of the simulated object. The forcegrid is designed for haptic interaction with continuous contact. It is a regular grid defined over the virtual workspace, in which every vertex contains a force. An extrapolation algorithm updates this force at every simulation cycle, while an interpolation algorithm computes the force to be rendered on the haptic device at the desired rate. The forcegrid has been successfully tested on various virtual deformable objects.

Describes experiments with a probabilistic roadmap planner (PRM) on a spot-welding station with 2 to 6 robot manipulators combining 12 to 36 degrees of freedom. When performing centralized planning, the planner has proven to be reliable and fast. When performing decoupled planning, it was not significantly faster, but it was much less reliable, failing to find a solution 30 to 75% of the times in 6-robot examples. This is an important result as it invalidates the assumption that the loss of completeness in performing decoupled planning is not very substantial in practice and indicates that centralized planning is a more desirable approach-at least in applications like spot-welding, which requires rather tight robot coordination.

Classic techniques for simulating molecular motion, such as the Monte Carlo and molecular dynamics methods, generate individual motion pathways one at a time and spend most of their time trying to escape from the local minima of the energy landscape of a molecule. Their high computational cost prevents them from being used to analyze many pathways. We introduce Stochustic Roadmap Sirrrcllation (SRS), a new approach for exploring the kinetics of molecular motion by simultaneously examining multiple pathways encoded compactly in a graph, called a roadmap. A roadmap is computed by sampling a molecule's conformation space at random. The computation does not suffer from the localminima problem encountered with existing methods. Each path in the roadmap represents a potential motion pathway and is associated with a probability indicating the likelihood that the molecule follows this pathway. By viewing the roadmap as a Markov chain, we can efficiently compute properties of molecular motion over the entire molecular energy landscape. We also prove that, in the limit, SRS converges to the same distribution as Monte Carlo simulation. To test the effectiveness of our approach, we apply it to the computation of the transmission coefficients for protein folding, an important order parameter that measures the kinetic distance of a protein's conformation to its native state Our computational studies show that SRS obtains more accurate results and achieves several orders- of- magnitude reduction in computation time, compared with Monte Carlo simulatio.

Presents algorithms for animating deformable objects in real time. We focus on computing the deformation of an object subject to external forces and detecting collisions among deformable and rigid objects. The targeted application domain is surgical training. This application relies more on visual realism than exact, patient-specific deformation, but requires that computations be performed in real time. This is in contrast with pre-operative surgical planning, where computations may be done offline but must provide accurate results. To achieve real-time performance, the proposed algorithms take advantage of the fact that most deformations are local, human-body tissues are well damped, and motions of surgical instruments are relatively slow. They have been integrated into a virtual reality system for simulating the suturing of small blood vessels (microsurgery).

Probabilistic roadmaps are an effective tool to compute the connectivity of the collision-free subset of high-dimensional robot configuration spaces. This paper extends them to capture the pertinent features of continuous functions over high-dimensional spaces. We focus here on computing energetically favorable motions of bio-molecules. A molecule is modeled as an articulated structure moving in an energy field. The set of all its 3D placements is the molecule's conformational space, over which the energy field is defined. A probabilistic conformational roadmap (PCR) tries to capture the connectivity of the low-energy subset of a conformational space, in the form of a network of weighted local pathways. The weight of a pathway measures the energetic difficulty for the molecule to move along it. The power of a PCR derives from its ability to compactly encode a large number of energetically favorable molecular pathways, each defined as a sequence of contiguous local pathways. This paper describes general techniques to compute and query PCRs, and presents implementations to study ligand-protein binding and protein folding.

This paper presents a randomized motion planner for kinodynamic asteroid avoidance problems, in which a robot must avoid collision with moving obstacles under kinematic, dynamic constraints and reach a specified goal state. Inspired by probabilistic-roadmap (PRM) techniques, the planner samples the state x time space of a robot by picking control inputs at random in order to compute a roadmap that captures the connectivity of the space. However, the planner does not precompute a roadmap as most PRM planners do. Instead, for each planning query, it generates, on the fly, a small roadmap that connects the given initial and goal state. In contrast to PRM planners, the roadmap computed by our algorithm is a directed graph oriented along the time axis of the space. To verify the planner's effectiveness in practice, we tested it both in simulated environments containing many moving obstacles and on a real robot under strict dynamic constraints. The efficiency of the planner makes it possible for a robot to respond to a changing environment without knowing the motion of moving obstacles well in advance.

Presents a brief overview of an algorithm for interactively animating object grasping and manipulation tasks for human figures. The technique is designed to efficiently generate feasible single-arm manipulation motions given high-level task commands. For moving an object, the motions necessary for a human arm to reach and grasp the object, re-position it and return the arm to rest are generated automatically within a few seconds on average. The method synthesizes motion "on-the-fly" by directly searching the configuration space of the arm. Goal configurations for the arm are computed using an inverse kinematics algorithm that attempts to select a natural posture. A collision-free trajectory connecting the arm's initial configuration to the goal configuration is computed using a randomized path planner. A high-level description of the methods is given, along with results from some computed examples using a human character model.

The paper presents a simple and efficient method of modeling synthetic vision, memory, and learning for autonomous animated characters in real time virtual environments. The model is efficient in terms of both storage requirements and update times, and can be flexibly combined with a variety of higher level reasoning modules or complex memory rules. The design is inspired by research in motion planning, control, and sensing for autonomous mobile robots. We apply this framework to the problem of quickly synthesizing from navigation goals the collision-free motions for animated human figures in changing virtual environments. We combine a low level path planner, a path following controller and cyclic motion capture data to generate the underlying animation. Graphics rendering hardware is used to simulate the visual perception of a character, providing a feedback loop to the overall navigation strategy. The synthetic vision and memory update rules can handle dynamic environments where objects appear, disappear, or move around unpredictably. The resulting model is suitable for a variety of real time applications involving autonomous animated characters.

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.

Article A general framework for assembly planning: the motion space approach Share on Authors: Dan Halperin Department of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel Department of Computer Science, Tel Aviv University, Tel Aviv 69978, IsraelView Profile , Jean-Claude Latombe Department of Computer Science, Stanford University, Stanford, CA Department of Computer Science, Stanford University, Stanford, CAView Profile , Randall H. Wilson Eastman Kodak Company, Albuquerque, NM Eastman Kodak Company, Albuquerque, NMView Profile Authors Info & Claims SCG '98: Proceedings of the fourteenth annual symposium on Computational geometryJune 1998 Pages 9–18https://doi.org/10.1145/276884.276886Online:07 June 1998Publication History 8citation507DownloadsMetricsTotal Citations8Total Downloads507Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

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.

We consider the path-planning problem for a robot pushing an object in an environment containing obstacles. This new variant of the classical robot path-planning problem has several interesting geometric aspects, which we explore. We focus on the setting where the robot makes a point contact with the object which is assumed to be a unit disk, while the obstacles are assumed to be polygonal.

This paper analyzes the variations of the relative positions of the parts composing an assembly when part dimensions span their specified tolerance zones. We focus on the simplified case where each part is modeled as a toleranced polygon defined as follows: each edge of this polygon is supported by a line of fixed orientation lying anywhere in a strip bounded by two extreme lines; these lines are themselves defined in a coordinate system attached to the part. The relative placements of parts in an assembly A are defined by spatial relations, such as edge e of part P is parallel to edge f of part Q, at distance d. We define the relative position of any two parts, P and Q, in an instance of A as the transform (a translation in our case) between the coordinate systems attached to these parts. Because of the possible variations in the geometry of each individual part, the relative position of P and Q is not constant over multiple instances of A. Hence, the question: what is the range of possible relative positions of any two parts in A? This paper describes an efficient algorithm to solve this problem. Experimental results obtained with an assembly sequence planner that incorporates this algorithm are also presented.

We introduce the notion of expansiveness to characterize a family of robot configuration spaces whose connectivity can be effectively captured by a roadmap of randomly-sampled milestones. The analysis of expansive configuration spaces has inspired us to develop a new randomized planning algorithm. This algorithm tries to sample only the portion of the configuration space that is relevant to the current query, avoiding the cost of precomputing a roadmap for the entire configuration space. Thus, it is well-suited for problems where a single query is submitted for a given environment. The algorithm has been implemented and successfully applied to complex assembly maintainability problems from the automotive industry.

We introduce the problem of computing robot motion strategies that maintain visibility of a moving target in a cluttered workspace. Both motion constraints (as considered in standard motion planning) and visibility constraints (as considered in visual tracking) must be satisfied. Additional criteria, such as the total distance traveled, can be optimized. The general problem is divided into two categories, on the basis of whether the target is predictable. For the predictable case, an algorithm that computes optimal, numerical solutions is presented. For the more challenging case of a partially-predictable target, two online algorithms are presented that each attempt to maintain future visibility with limited prediction. One strategy maximizes the probability that the target will remain in view in a subsequent time step, and the other maximizes the minimum time in which the target could escape the visibility region. We additionally discuss issues resulting from our implementation and experiments on a mobile robot system.

This paper introduces a visibility-based motion planning problem in which the task is to coordinate the motions of one or more robots that have omnidirectional vision sensors, to eventually "see" a target that is unpredictable, has unknown initial position, and is capable of moving arbitrarily feast. A visibility region is associated with each robot, and the goal is to guarantee that the target will ultimately lie in at least one visibility region. Both a formal characterization of the general problem and several interesting problem instances are presented. A complete algorithm for computing the motion strategy of the robots is also presented, and is based on searching a finite cell complex that is constructed on the basis of critical information changes. A few computed solution strategies are shown. Several bounds on the minimum number of needed robots are also discussed.

The goal of assembly sequencing is to plan a feasible series of operations to construct a product from its individual parts. Previous research has investigated assembly sequencing under the assumption that parts have nominal geometry. This paper considers the case where parts have toleranced geometry. Its main contribution is an efficient procedure that decides if a product admits an assembly sequence with infinite translations (i.e. translations that can be extended arbitrarily far along a fixed direction), that is feasible for all possible instances of the components within the specified tolerances. If the product admits one such sequence, the procedure can also generate it. For the cases where there exists no such assembly sequence, another procedure is proposed which generates assembly sequences that are feasible only for some values of the toleranced dimensions. If this procedure produces no such sequence, then no instance of the product is assemblable. These two procedures are described for 2D assemblies made of polygonial parts and for 3D assemblies made of polyhedral parts. So far, only the first has been implemented (for the planar case). This work assumes a simple, but non-trivial tolerance language that falls short of capturing all imperfections of a manufacturing process. In particular, it assumes that faces and edges have perfect relative orientations. Thus, it is only one step towards dealing with tolerances in assembly sequencing.

Inspired by the success of the distributed computing community in apply logics of knowledge and time to reasoning about distributed protocols, we aim for a similarly powerful and high-level abstraction when reasoning about control problems involving uncertainty. This paper concentrates on robot motion planning with uncertainty in both control and sensing, a problem that has already been well studied within the robotics community. First, a new and natural problem in this domain is defined: does there exists a sound and complete termination condition for a motion, given initial and goal locations? If yes, how to construct it? Then we define a high-level language, a logic of time and knowledge, which we use to reason about termination conditions and to state general conditions for the existence of sound and complete termination conditions in a broad domain. Finally, we show that sound termination conditions that are optimal in a precise sense provide a natural example of knowledge-based programs with multiple implementations.

We examine various complexity measures for two-handed assembly sequences. For many products there exists an exponentially large set of valid sequences, and a natural goal is to use automated systems to select wisely from the choices. Since assembly sequencing is a preprocessing phase for a long and expensive manufacturing process, any work towards finding a "better" assembly sequence is of great value when it comes time to assemble the physical product in mass quantities. We take a step in this direction by introducing a formal framework for studying the optimization of several complexity measures. This framework focuses on the combinatorial aspect of the family of valid assembly sequences, while temporarily separating out the specific geometric assumptions inherent to the problem. With an exponential number of possibilities, finding the true optimal cost solution is non-trivial. In the most general case, our results show that even finding an approximate solution is hard. Furthermore, we can show several hardness results, even in simple geometric settings. Future work is directed towards using this model to study how the original geometric assumptions can be reintroduced to prove stronger approximation results.

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

Path planning has been widely studied by computer scientists. However, it is a very simplified version of the motion planning problems occurring in robotics. This paper examines extensions yielding two important issues: controllability and recognizability. The controllability issue arises when the number of controls is smaller than the number of independent parameters defining the robot's configuration: Can the motions span the configuration space? The recognizability issue occurs when there are errors in control and sensing: Can the robot recognize goal achievement? Both issues have interesting impact on the computational complexity of motion planning. This paper will also discuss a new path planning scheme based on random sampling of configuration space, to deal with many-degree-of-freedom robots. The blend of controllability, recognizability, and complexity issues discussed in this paper is unique to robotics and its study is key to the development of autonomous robots.

It is important to set landmarks when a robot needs to navigate in a certain environment and to measure its own location; however, it has not been discussed well how to arrange landmarks in the optimal way until now. We, therefore, demonstrate the possibility of design of the optimal arrangement of artificial landmarks. First, we make it clear the optimization problem with regard to the arrangement of landmarks. Second, as one example of the artificial landmarks, we introduce a signboard system. Third, we propose a methodology to evaluate arrangement of landmarks assuming an obstacled rectangular environment. Fourth, we apply the algorithm of spatial competition to the optimal arrangement of landmarks. Finally, simulation results indicate that even though our method is not global optimization approach we can obtain closely optimal and practical arrangement with the minimum number of landmarks which satisfies the necessary condition.

We study the following problem: Given a collection A of polyhedral parts in 3D, determine whether there exists a subset S of the parts that can be moved as a rigid body by an infinitesimal translation and rotation, without colliding with the rest of the parts, AS. A negative result implies that the object whose constituent parts are the collection A cannot be taken apart with two hands. A positive result, together with the list of movable parts in S and a direction of motion for S, can be used by an assembly sequence planner. This problem has attracted considerable attention within and outside the robotics community. We devise an efficient algorithm to solve this problem. Our solution is based on the ability to focus on selected portions of the tangent space of rigid motions and efficiently access these portions. The algorithm is complete (in the sense that it is guaranteed to find a solution if one exists), simple, and improves significantly over the best previously known solutions. We report experimental results with an implementation of our algorithm.

In a dynamic and partially unpredictable environment, robot motion planning must be on-line. The planner receives a continuous flow of information about occurring events and generates new plans, while previously planned motions are being executed. This paper describes an on-line planner for two cooperating arms whose task is to grab parts on a conveyor belt and transfer them to their respective goals, while avoiding collision with obstacles. Parts arrive on the belt in random order, at any time. This scenario is typical of manufacturing cells serving machine-tools, assembling products, or packaging objects. The proposed approach breaks the overall planning problem into subproblems, each involving a low-dimensional configuration or configuration x time space, and orchestrates very fast primitives solving these subproblems. The resulting planner has been implemented and extensively tested both in a simulated environment and with a real dual-arm system. Its competitiveness has been evaluated against an oracle making (almost) the best decision at any one time. The planner compares extremely well.

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

In robotics uncertainty exists at both planning and execution time. Effective planning must make sure that enough information becomes available to the sensors during execution, to allow the robot to correctly identify the states it traverses. It requires selecting a set of states, associating a motion command with every state, and synthesizing functions to recognize state achievement. These three tasks are often interdependent, causing existing planners to be either unsound, incomplete, and/or computationally impractical. In this paper we partially break this interdependence by assuming the existence of landmark regions in the workspace. We define such regions as “islands of perfection” where position sensing and motion control are accurate. Using this notion, we propose a sound and complete planner of polynomial complexity. Creating landmarks may require some prior engineering of the robot and/or its environment. Though we believe that such engineering is unavoidable in order to build reliable practical robot systems, its cost must be reduced as much as possible. With this goal in mind, we also investigate how some of our original assumptions can be eliminated. In particular, we show that sensing and control do not have to be perfect in landmark regions. We also study the dependency of a plan on control uncertainty and we show that the structure of a reliable plan only changes at critical values of this uncertainty. Hence, any uncertainty reduction between two consecutive such values is useless. The proposed planner has been implemented. Experimentation has been successfully conducted both in simulation and using a NOMAD-200 mobile robot.

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

This paper considers the automatic generation of motion paths for several cooperating robot arms to manipulate a movable object between two configurations among obstacles. To avoid collisions the robots may have to change their grasp of the object, for example, by passing it from one arm to another. The case where the movable object can only be moved by two arms acting simultaneously is also considered. An approach for solving this planning problem is described and illustrated with a robot system made of three arms moving in a 3D environment. Experiments with a planner implementing this approach show that it is not only fast, but also reliable in finding collision-free paths.>

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

We apply manipulation planning to computer animation. A new path planner is presented that automatically computes the collision-free trajectories for several cooperating arms to manipulate a movable object between two configurations. This implemented planner is capable of dealing with complicated tasks where regrasping is involved. In addition, we present a new inverse kinematics algorithm for the human arms. This algorithm is utilized by the planner for the generation of realistic human arm motions as they manipulate objects. We view our system as a tool for facilitating the production of animation.

In which order can a product be assembled or disassembled? How many hands are required? How many degrees of freedom? What parts should be withdrawn to allow the removal of a specified subassembly? To answer such questions automatically, important theoretical issues in geometric reasoning must be addressed. This paper investigates the planning of assembly algorithms specifying (dis) assembly operations on the components of a product and the ordering of these operations. It also presents measures to evaluate the complexity of these algorithms and techniques to estimate the inherent complexity of a product. The central concept underlying these planning and complexity evaluation techniques is that of a “non-directional blocking graph”, a qualitative representation of the internal structure of an assembly product. This representation describes the combinatorial set of parts interactions in polynomial space. It is obtained by identifying physical criticalities where geometric interferences among parts change. It is generated from an input geometric description of the product. The main application considered in the paper is the creation of smart environments to help designers create products that are easier to manufacture and service. Other possible applications include planning for rapid prototyping and autonomous robots.

Failures in mobile robot navigation are often caused by errors in localizing the robot relative to its environment. This paper explores the idea that these errors can be considerably reduced by planning paths taking the robot through positions where pertinent features of the environment can be sensed. It introduces the notion of a "sensory uncertainty field" (SUF). For every possible robot configuration q, this field estimates the distribution of possible errors in the robot configuration that would be computed by a localization function matching the data given by the sensors against an environment model, if the robot was at q. A planner is proposed which uses a precomputed SUF to generate paths that minimize expected errors or any other criterion combining, say, path length and errors. This paper describes in detail the computation of a specific SUF for a mobile robot equipped with a classical line-striping camera/laser range sensor. It presents an implemented SUF-based motion planner for this robot and shows paths generated by this planner. Navigation experiments were conducted with mobile robots using paths generated by the SUF-based planner and other paths. The former paths were tracked with greater precision than the others. The final section of the paper discusses additional research issues related to SUF-based planning.>

Stereotaxic radiosurgery is a procedure that uses a beam of radiation as an ablative surgical instrument to destroy brain tumors (or more generally, brain lesions). The beam is produced by a linear accelerator that is moved by a mechanical gantry. Radiation is concentrated by crossfiring at the tumor from multiple directions, to reduce the amount of energy deposited in healthy tissues. Because access to and exit from the tumor is obstructed along some directions by critical structures (e.g., brain stem, optic nerves), planning the path of the beam is often difficult and time-consuming. This paper describes a computer-based planner developed to interactively assist the surgeon generate a satisfactory treatment, given the spatial distribution of the brain tissues obtained with medical imaging. This planner has been experimented on using 11 cases previously processed at the Stanford Medical Center. A dosimetric comparison with the manually generated plans for these cases was carried but. Although still limited, results indicate that automatic planning can significantly improve energy deposition. It can also shorten the overall treatment, hence reducing the patient's pain and allowing the radiosurgery equipment to be used for more patients. Stereotaxic radiosurgery is an example of so-called "bloodless surgery." Computer-based planning techniques are expected to facilitate further development of this safer, less painful, and more cost effective type of surgery.>

The problem of dual-arm manipulation planning is to plan the path of two cooperating robot arms to carry a moveable object from a given initial configuration to a given goal configuration amidst obstacles. The authors survey previous work in manipulation planning and relate it to this analysis. A formal configuration space presentation of the problem is given. Three implemented planners are described. These three planners operated in a two-dimensional workspace and addressed increasingly difficult versions of the dual-arm manipulation problem. They were implemented in the C language. Execution times given were obtained by running them on a DEC 5000 workstation.>

The authors introduce an approach to motion planning with uncertainty for mobile robots. Given a model of the robot's environment, a sensory uncertainty field (SUF) is computed over the robot's configuration space. At every configuration q, the SUF is an estimate of the uncertainty in the sensed configuration that would be computed by matching the data given by the robot sensors against the environment model, if the robot was at the configuration q. A planner then makes use of the computed SUF to generate paths that minimize the expected errors. The computation of a SUF is described for a classical line-striping camera/laser range sensor. An implemented SUF-based motion planner for a robot equipped with this sensor is presented.>

An approach to robot path planning that consists of incrementally building a graph connecting the local minima of a potential field defined in the robot's configuration space and concurrently searching this graph until a goal configuration is attained is proposed. Unlike the so-called global path planning methods, this approach does not require an expensive computation step before the search for a path can actually start, and it searches a graph that is usually much smaller than the graph searched by the so-called local methods. A collection of effective techniques to implement this approach is described. They are based on the use of multiscale pyramids of bitmap arrays for representing both the robot's workspace and configuration space. This distributed representation makes it possible to construct potential fields numerically, rather than analytically. A path planner based on these techniques has been implemented. Experiments with this planner show that it is both very fast and capable of handling many degrees of freedom.>

It is shown that the well-known controllability rank condition theorem is applicable to nonholonomic multibody robots, even when there are inequality constraints on the velocity. This makes it possible to subsume and generalize several controllability results published in the robotics literature concerning nonholonomic mobile robots, and to infer new results. Also described is an implemented planner based on these results. Experimental results obtained with this planar are given.>

Motion planning with uncertainty in control and sensing raises two basic issues, goal reachability and goal recognizability, which subtly interact. A partial analysis of this interaction is presented. It is shown that the capability of a motion command to recognize goal achievement is augmented by providing the termination condition of the motion command with the knowledge of the region in which the motion command is known to start (initial state) and the knowledge of the termination condition itself (final state). The increase in the recognition power of the termination condition is illustrated with a simple preimage construction example. The size of the preimage grows when one adds the initial and the final states in the knowledge of the termination condition. Although these results are preliminary it is expected that they will eventually help in the design of more powerful motion planners in the presence of uncertainty.>

An implemented system for designing pipe layouts automatically using robot path planning techniques is described. The authors introduce a new approach to pipe layout design automation in which pipe routes are treated as paths left behind by rigid objects (robots). They have implemented this approach in a basic pipe router, which is also described, and have extended this router in order to make it capable of treating a variety of other constraints which are typical of practical pipe layout design problems. These constraints relate to the process carried out in the pipes, to the design of their mechanical support, and to the constructability and the ease of operation and maintenance of the designed pipe systems.>

This paper describes a type of contingency-tolerant navigation system for an autonomous mobile robot performing transportation tasks in an office-like environment. A prior model of the environment is available, but this model is incomplete. The system combines a planning component that makes use of the available knowledge to plan a lesser-committed motion plan and a reaction component that pilots the robot according to this plan through the unexpected obstacles detected by the robot's sensors. These two components embody practical answers to several important questions such as what a lesser-committed motion plan is, how it can be represented and used; and how computations should be organized so that the most common situations are handled quickly. The navigation system described has been implemented and a robot called GOFER tested on.>

Most of the research in robot motion planning has focused on finding a collision-free path connecting two configurations of the robot among obstacles, under the assumptions that geometric models are complete and accurate and that robot control is perfect. In this paper we consider the problem of planning motion strategies in the presence of uncertainty in both control and sensing, using the preimage backchaining approach. Though attractive, this approach raises difficult computational issues. One of them, preimage computation, is the main topic of this paper. We describe two practical methods for computing preimages for a robot having a two-dimensional Euclidean configuration space. We also propose a combination of these two methods which yields the most powerful practical method devised so far for computing preimages. A motion planner based on these methods has been implemented and experimental results are given in this paper. We discuss non-implemented improvements of this planner, including a new way to embed knowledge in a motion command in order to produce larger preimages.

The authors consider one of the most popular approaches to path planning: hierarchical approximate cell decomposition. This approach consists of constructing successive decompositions of the robot's configuration space into rectangloid cells and searching the connectivity graph built at each level of decomposition for a path. Despite its conceptual simplicity, an efficient implementation of this approach raises many delicate questions that have not yet been addressed. The major contributions this work are (1) a novel approach to cell decomposition based on constraint reformulation and (2) a new algorithm for hierarchical search with a mechanism for recording failure conditions. These algorithms have been implemented in a path planner, and experiments with this planner have been carried out on various examples. These experiments show that the proposed planner is significantly (approximately 10 times) faster than previous planners based on the same general approach.>

A stochastic technique is described for planning collision-free paths of robots with many degrees of freedom (DOFs). The algorithm incrementally builds a graph connecting the local minima of a potential function defined in the robot's configuration space and concurrently searches the graph until a goal configuration is attained. A local minimum is connected to another one by executing a random motion that escapes the well of the first minimum, succeeded by a gradient motion that follows the negated gradient of the potential function. All the motions are executed in a grid shown through the robot's configuration space. The random motions are implemented as random walks which are known to converge toward Brownian motions when the steps of the walks tend toward zero. The local minima graph is searched using a depth-first strategy with random backtracking. In the technique, the planner does not explicitly represent the local-minima graph. The path-planning algorithm has been fully implemented and has run successfully on a variety of problems involving robots with many degrees of freedom.>

Robot path planning consists of approximating the set of free configurations of the robot by a collection of rectangloid cells at successive levels of approximation and, at each level, searching the graph representing the adjacency relation among these cells. A set of algorithms which specifically address the main two computational issues underlying this approach, cell decomposition and graph searching, has been developed. The authors have implemented a planner which incorporates these algorithms and have experimented with it on examples. The experiments show that the planner is significantly faster than previous planners based on the same general approach. The authors focus on the planner's cell-decomposition algorithms. They use a constraint reformulation technique that consists of approximating the obstacles intersecting the cell to be decomposed by a collection of rectangloids and computing their complements in the cell. Two types of approximations are used, bounding and bounded approximations. This technique produces much less cells than previously proposed techniques, resulting in smaller search graphs. Experimental results are presented.>