Immersive telepresence, when a user views the video stream of a 360° camera in a remote environment using a Head Mounted Display (HMD), has great potential to improve the sense of being in a remote environment. In most cases of immersive robotic telepresence, the camera is mounted on a mobile robot which increases the portion of the environment that the remote user can explore. However, robot motions can induce unpleasant symptoms associated with Virtual Reality (VR) sickness, degrading the overall user experience. Previous research has shown that unwinding the rotations of the robot, that is, decoupling the rotations that the camera undergoes due to robot motions from what is seen by the user, can increase user comfort and reduce VR sickness. However, that work considered a virtual environment and a simulated robot. In this work, to test whether the same hypotheses hold when the video stream from a real camera is used, we carried out a user study ($n=36$) in which the unwinding rotations method was compared against coupled rotations in a task completed through a panoramic camera mounted on a robotic arm. Furthermore, within an inspection task which involved translations and rotations in three dimensions, we tested whether unwinding the robot rotations impacted the performance of users. The results show that the users found the unwinding rotations method to be more comfortable and preferable, and that a reduced level of VR sickness can be achieved without a significant impact on task performance.

According to previous research, humans are generally poor at adapting to earth-discrepant gravity, especially in Virtual Reality (VR), which cannot simulate the effects of gravity on the physical body. Most of the previous VR research on gravity adaptation has used perceptual or interception tasks, although adaptation to these tasks seems to be especially challenging compared to tasks with a more pronounced motor component. This article describes the results of two between-subjects studies ( n = 60 and n = 42) that investigated adaptation to increased gravity simulated by an interactive VR experience. The experimental procedure was identical in both studies: In the adaptation phase, one group was trained to throw a ball at a target using Valve Index motion controllers in gravity that was simulated at five times of earth’s gravity (hypergravity group), whereas another group threw at a longer-distance target under normal gravity (normal gravity group) so both groups had to exert the same amount of force when throwing (approximated manually in Study 1 and mathematically in Study 2). Then, in the measurement phase, both groups repeatedly threw a virtual ball at targets in normal gravity. In this phase, the trajectory of the ball was hidden at the moment of release so that the participants had to rely on their internal model of gravity to hit the targets rather than on visual feedback. Target distances were placed within the same range for both groups in the measurement phase. According to our preregistered hypotheses, we predicted that the hypergravity group would display worse overall throwing accuracy and would specifically overshoot the target more often than the normal gravity group. Our experimental data supported both hypotheses in both studies. The findings indicate that training an interactive task in higher simulated gravity led participants in both studies to update their internal gravity models, and therefore, some adaptation to higher gravity did indeed occur. However, our exploratory analysis also indicates that the participants in the hypergravity group began to gradually regain their throwing accuracy throughout the course of the measurement phase.

We present a general approach for determining the unknown (or uncertain) position and orientation of a sensor mounted on a robot in a known environment, using only a few distance measurements (between 2 to 6 typically), which is advantageous, among others, in sensor cost, and storage and information-communication resources. In-between the measurements, the robot can perform predetermined local motions in its workspace, which are useful for narrowing down the candidate poses of the sensor. We demonstrate our approach for planar workspaces, and show that, under mild transversality assumptions, already two measurements are sufficient to reduce the set of possible poses to a set of curves (one-dimensional objects) in the three-dimensional configuration space of the sensor$\mathbb{R}^{2}\times \mathbb{S}^{1},$and three or more measurements reduce the set of possible poses to a finite collection of points. However, analytically computing these potential poses for non-trivial intermediate motions between measurements raises substantial hardships and thus we resort to numerical approximation. We reduce the localization problem to a carefully tailored procedure of intersecting two or more implicitly defined two-manifolds, which we carry out to any desired accuracy, proving guarantees on the quality of the approximation. We demonstrate the real-time effectiveness of our method even at high accuracy on various scenarios and different allowable intermediate motions. We also present experiments with a physical robot. Our open-source software and supplementary materials are available at https://bitbucket.org/taucgl/vb-fdml-public.

This paper presents methods for dramatically improving the performance of sampling-based kinodynamic planners. The key component is a complete, exact steering method that produces a time-optimal trajectory between any states for a vector of synchronized double integrators. This method is applied in three ways: 1) to generate RRT edges that quickly solve the two-point boundary-value problems, 2) to produce a (quasi)metric for more accurate Voronoi bias in RRTs, and 3) to iteratively time-optimize a given collision-free trajectory. Experiments are performed for state spaces with up to 2000 dimensions, resulting in improved computed trajectories and orders of magnitude computation time improvements over using ordinary metrics and constant controls.

In this paper, we show that Virtual Reality (VR) sickness is associated with a reduction in attention, which was detected with the P3b Event-Related Potential (ERP) component from electroencephalography (EEG) measurements collected in a dual-task paradigm. We hypothesized that sickness symptoms such as nausea, eyestrain, and fatigue would reduce the users' capacity to pay attention to tasks completed in a virtual environment, and that this reduction in attention would be dynamically reflected in a decrease of the P3b amplitude while VR sickness was experienced. In a user study, participants were taken on a tour through a museum in VR along paths with varying amounts of rotation, shown previously to cause different levels of VR sickness. While paying attention to the virtual museum (the primary task), participants were asked to silently count tones of a different frequency (the secondary task). Control measurements for comparison against the VR sickness conditions were taken when the users were not wearing the Head-Mounted Display (HMD) and while they were immersed in VR but not moving through the environment. This exploratory study shows, across multiple analyses, that the effect mean amplitude of the P3b collected during the task is associated with both sickness severity measured after the task with a questionnaire (SSQ) and with the number of counting errors on the secondary task. Thus, VR sickness may impair attention and task performance, and these changes in attention can be tracked with ERP measures as they happen, without asking participants to assess their sickness symptoms in the moment.

We propose unwinding the rotations experienced by the user of an immersive telepresence robot to improve comfort and reduce VR sickness of the user. By immersive telepresence we refer to a situation where a 360° camera on top of a mobile robot is streaming video and audio into a head-mounted display worn by a remote user possibly far away. Thus, it enables the user to be present at the robot's location, look around by turning the head and communicate with people near the robot. By unwinding the rotations of the camera frame, the user's viewpoint is not changed when the robot rotates. The user can change her viewpoint only by physically rotating in her local setting; as visual rotation without the corresponding vestibular stimulation is a major source of VR sickness, physical rotation by the user is expected to reduce VR sickness. We implemented unwinding the rotations for a simulated robot traversing a virtual environment and ran a user study (N=34) comparing unwinding rotations to user's viewpoint turning when the robot turns. Our results show that the users found unwound rotations more preferable and comfortable and that it reduced their level of VR sickness. We also present further results about the users' path integration capabilities, viewing directions, and subjective observations of the robot's speed and distances to simulated people and objects.

This paper considers the problem of enabling the user to modify the path of a telepresence robot. The robot is capable of autonomously navigating to a goal predefined by the user, but the user might still want to modify the path, for example, to go further away from other people, or to go closer to landmarks she wants to see on the way. We propose Human-Influenced Dynamic Window Approach (HI-DWA), a shared control method aimed for telepresence robots based on Dynamic Window Approach (DWA) that allows the user to influence the control input given to the robot. To verify the proposed method, we performed a user study (N=32) in Virtual Reality (VR) to compare HI-DWA with switching between autonomous navigation and manual control for controlling a simulated telepresence robot moving in a virtual environment. Results showed that users reached their goal faster using HI-DWA controller and found it easier to use. Preference between the two methods was split equally. Qualitative analysis revealed that a major reason for the participants that preferred switching between two modes was the feeling of control. We also analyzed the effect of different input methods, joystick and gesture, on the preference and perceived workload.

This paper introduces mathematical models of touch sensors for mobile robots based on visibility. Serving a purpose similar to the pinhole camera model for computer vision, the introduced models are expected to provide a useful, idealized characterization of task-relevant information that can be inferred from their outputs or observations. Possible tasks include navigation, localization and mapping when a mobile robot is deployed in an unknown environment. These models allow direct comparisons to be made between traditional depth sensors, highlighting cases in which touch sensing may be interchangeable with time of flight or vision sensors, and char-acterizing unique advantages provided by touch sensing. The models include contact detection, compression, load bearing, and deflection. The results could serve as a basic building block for innovative touch sensor designs for mobile robot sensor fusion systems.

In this paper, we present an implementation of a leaning-based control of a differential drive telepresence robot and a user study in simulation, with the goal of bringing the same functionality to a real telepresence robot. The participants used a balance board to control the robot and viewed the virtual environment through a head-mounted display. The main motivation for using a balance board as the control device stems from Virtual Reality (VR) sickness; even small movements of your own body matching the motions seen on the screen decrease the sensory conflict between vision and vestibular organs, which lies at the heart of most theories regarding the onset of VR sickness. To test the hypothesis that the balance board as a control method would be less sickening than using joysticks, we designed a user study (N=32, 15 women) in which the participants drove a simulated differential drive robot in a virtual environment with either a Nintendo Wii Balance Board or joysticks. However, our pre-registered main hypotheses were not supported; the joystick did not cause any more VR sickness on the participants than the balance board, and the board proved to be statistically significantly more difficult to use, both subjectively and objectively. Analyzing the open-ended questions revealed these results to be likely connected, meaning that the difficulty of use seemed to affect sickness; even unlimited training time before the test did not make the use as easy as the familiar joystick. Thus, making the board easier to use is a key to enable its potential; we present a few possibilities towards this goal.

We propose augmenting immersive telepresence by adding a virtual body, representing the user's own arm motions, as realized through a head-mounted display and a 360-degree camera. Previous research has shown the effectiveness of having a virtual body in simulated environments; however, research on whether seeing one's own virtual arms increases presence or preference for the user in an immersive telepresence setup is limited. We conducted a study where a host introduced a research lab while participants wore a head-mounted display which allowed them to be telepresent at the host's physical location via a 360-degree camera, either with or without a virtual body. We first conducted a pilot study of 20 participants, followed by a pre-registered 62 participant confirmatory study. Whereas the pilot study showed greater presence and preference when the virtual body was present, the confirmatory study failed to replicate these results, with only behavioral measures suggesting an increase in presence. After analyzing the qualitative data and modeling interactions, we suspect that the quality and style of the virtual arms, and the contrast between animation and video, led to individual differences in reactions to the virtual body which subsequently moderated feelings of presence.

This paper considers a fundamental, optimal path planning problem that requires simultaneously minimizing path length and maximizing obstacle clearance. We show that in even simple planar settings with point and disc obstacles, the set of alternative solutions such that no one is clearly better than another (the set of Pareto-optimal solutions) is uncountably infinite. In spite of this difficulty, we introduce a complete, efficient algorithm that computes the Pareto front and a data structure that finitely represents the complete set of all Pareto- optimal paths. Particular optimal paths can then be selected from the computed data structure during execution, based on any additional conditions or considerations.

This paper considers how the motions of a telepresence robot moving autonomously affect a person immersed in the robot through a head-mounted display. In particular, we explore the preference, comfort, and naturalness of elements of piecewise linear paths compared to the same elements on a smooth path. In a user study, thirty-six subjects watched panoramic videos of three different paths through a simulated museum in virtual reality and responded to questionnaires regarding each path. Preference for a particular path was influenced the most by comfort, forward speed, and characteristics of the turns. Preference was also strongly associated with the users’ perceived naturalness, which was primarily determined by the ability to see salient objects, the distance to the walls and objects, as well as the turns. Participants favored the paths that had a one meter per second forward speed and rated the path with the least amount of turns as the most comfortable.

This paper applies the principles of Virtual Reality (VR) to robots, rather than living organisms. A simulator, of either physical states or information states, renders outputs to custom displays that fool the robot's sensors. This enables a robot to experience a combination of real and virtual sensor inputs, combining the efficiency of simulation and the benefits of real world sensor inputs. Thus, the robot can be taken through targeted experiences that are more realistic than pure simulation, yet more feasible and controllable than pure real-world experiences. We define two distinctive methods for applying VR to robots, namely black box and white box; based on these methods we identify potential applications, such as testing and verification procedures that are better than simulation, the study of spoofing attacks and anti-spoofing techniques, and sample generation for machine learning. A general mathematical framework is presented, along with a simple experiment, detailed examples, and discussion of the implications.

This paper identifies a new phenomenon: when users interact with simulated objects in a virtual environment where the user is much smaller than usual, there is a mismatch between the object physics that they expect and the object physics that would be correct at that scale. We report the findings of our study investigating the relationship between perceived realism and a physically accurate approximation of reality in a virtual reality experience in which the user has been scaled down by a factor of ten. We conducted a within-subjects experiment in which 44 subjects performed a simple interaction task with objects under two different physics simulation conditions. In one condition, the objects, when dropped and thrown, behaved accurately according to the physics that would be correct at that reduced scale in the real world, our true physics condition. In the other condition, the movie physics condition, the objects behaved in a similar manner as they would if no scaling of the user had occurred. We found that a significant majority of the users considered the latter condition to be the more realistic one. We argue that our findings have implications for many virtual reality and telepresence applications involving operation with simulated or physical objects in small scales.

Objective: In recent years, the training of novice medical professionals with simulated environments such as virtual reality (VR) and augmented reality (AR) has increased dramatically. However, the usability of these technologies is limited due to the complexity involved in creating the clinical content. To be comparable to a clinical environment, the simulation platform should include real-world learning parameters such as patient physiology, emotions, and clinical team behaviors. Incorporating such nondeterministic parameters has historically required faculty to possess advanced programming skills. Lack of effective software for instructors to easily develop VR curriculum content is a hurdle in developing VR based curriculum. Method: We address this challenge through a software platform that simplifies the creation of Interactive Mixed Reality (IMR) scenarios. Three educational components we were able to embed into an IMR scenario includes 1) integrated 360-degree video recording of a clinical encounter to provide a first-person perspective, 2) rich annotated knowledge content, and 3) assessment questionnaire. We developed a sepsis prevention education scenario using the IMR software to demonstrate the potential of enhancing simulated medical training by accelerating clinical exposure for novice students. Result: An IRB approved study was conducted with a group of 28 novice students to evaluate the efficacy of the IMR technology. The participants provided feedback by answering demographics, NASA-TLX and system usability scale questionnaires. Significance: Our software is a step towards improving VR based education content development process. Conclusion: The studies conducted here provide preliminary evidence that the IMR software is a usable technology based on the NASA-TLX and system usability studies conducted. Future work will compare our new educational strategy for medical training with live simulation scenarios inside a hospital room and a simple video-based curriculum.

In this study we compare two conditions of visual detail - modern graphics and detail reduction through cel-shading - in experiencing Cybersickness during virtual movement along a preprogrammed path within a scene depicting a real-world outdoor museum viewed with Oculus CV1. The Cybersickness experience was quantified with the Fast-Motion-Sickness (FMS) scale and the Simulator Sickness Questionnaire (SSQ). We found weak evidence for realistic graphics being more sickness-inducing. Also, FMS scores peaked whenever a participant was entering a building.

Differential drive robots, such as robotic vacuums, often have at least two motion primitives: the ability to travel forward in straight lines, and rotate in place upon encountering a boundary. They are often equipped with simple sensors such as contact sensors or range finders, which allow them to measure and control their heading angle with respect to environment boundaries. We aim to find minimal control schemes for creating stable, periodic “patrolling” dynamics for robots that drive in straight lines and “bounce” off boundaries at controllable angles. As a first step toward analyzing high-level mobile robot dynamics in more general environments, we analyze the location and stability of periodic orbits in regular polygons. The contributions of this paper are: 1) proving the existence of periodic trajectories in n-sided regular polygons and showing the range of bounce angles that will produce such trajectories; 2) an analysis of their stability and robustness to modeling errors; and 3) a closed form solution for the points where the robot collides with the environment boundary while patrolling. We present simulations confirming our theoretical results.

We study optimal multirobot path planning on graphs (MPP) over four minimization objectives: the makespan (last arrival time), the maximum (single-robot traveled) distance, the total arrival time, and the total distance. Having established previously that these objectives are distinct and NP-hard to optimize, in this paper, we focus on efficient algorithmic solutions for solving these optimal MPP problems. Toward this goal, we first establish a one-to-one solution mapping between MPP and a special type of multiflow network. Based on this equivalence and integer linear programming (ILP), we design novel and complete algorithms for optimizing over each of the four objectives. In particular, our exact algorithm for computing optimal makespan solutions is a first that is capable of solving extremely challenging problems with robot-vertex ratios as high as 100%. Then, we further improve the computational performance of these exact algorithms through the introduction of principled heuristics, at the expense of slight optimality loss. The combination of ILP model based algorithms and the heuristics proves to be highly effective, allowing the computation of 1.x-optimal solutions for problems containing hundreds of robots, densely populated in the environment, often in just seconds.

This paper presents strategies for controlling the distribution of large numbers of minimalist robots (ones containing no sensors or computers). The strategies are implemented by varying area, speed, gate length, or gate configuration in environments composed of regions connected by gates and modelled by Continuous Time Markov chains. We demonstrate the effectiveness and practical feasibility of our strategies through physical experiments and simulation. We use Continuous Stochastic Logic to verify high level properties of our system and to evaluate the accuracy of our model. Also, we prove that our model is accurate and that our algorithms are efficient with respect to the number of regions and number of bodies.

We present methods for efficiently maintaining human head orientation using low-cost MEMS sensors. We particularly address gyroscope integration and compensation of dead reckoning errors using gravity and magnetic fields. Although these problems have been well-studied, our performance criteria are particularly tuned to optimize user experience while tracking head movement in the Oculus Rift Development Kit, which is the most widely used virtual reality headset to date. We also present novel predictive tracking methods that dramatically reduce effective latency (time lag), which further improves the user experience. Experimental results are shown, along with ongoing research on positional tracking.

This paper addresses the problem of exploring an unknown, planar, polygonal and simply connected environment. A saliency object (i.e. a landmark) is located in the environment. The collision-free subset of the robot's configuration space is simply connected or it might have several connected components. The robot is a differential drive system shaped as a disc. The robot has limited sensing, namely it is incapable of measuring any distance or angle, or performing self localization. The exploration problem consists in discovering the environment with the robot's sensor. To solve this problem, a motion policy is developed based on simple sensor feedback and a complete exploration strategy is represented as a Moore Machine. The proposed exploration strategy guarantees that the robot will discover the largest possible region of the environment. Consequently, the robot will find the landmark or declare that an exploration strategy to find it does not exist.

A problem is introduced in which a moving body (robot, human, animal, vehicle, and so on) travels among obstacles and binary detection beams that connect between obstacles or barriers. Each beam can be viewed as a virtual sensor that may have many possible alternative implementations. The task is to determine the possible body paths based only on sensor observations that each simply report that a beam crossing occurred. This is a basic filtering problem encountered in many settings, under a variety of sensing modalities. Filtering methods are presented that reconstruct the set of possible paths at three levels of resolution: (1) the possible sequences of regions (bounded by beams and obstacles) visited, (2) equivalence classes of homo-topic paths, and (3) the possible numbers of times the path winds around obstacles. In the simplest case, all beams are disjoint, distinguishable, and directed. More complex cases are then considered, allowing for any amount of beams overlapping, indistinguishability, and lack of directional information. The method was implemented in simulation. An inexpensive, low-energy, easily deployable architecture was also created which implements the beam model and validates the methods of the article with experiments.

Determining the existence of a collision-free path between two points is one of the most fundamental questions in robotics. However, in situations where crossing an obstacle is costly but not impossible, it may be more appropriate to ask for the path that crosses the fewest obstacles. This may arise in both autonomous outdoor navigation (where the obstacles are rough but not completely impassable terrain) or indoor navigation (where the obstacles are doors that can be opened if necessary). This problem, the minimum constraint removal problem, is at least as hard as the underlying path existence problem. In this paper, we demonstrate that the minimum constraint removal problem is NP-hard for navigation in the plane even when the obstacles are all convex polygons, a case where the path existence problem is very easy.

In this paper, we study the structure and computational complexity of optimal multi-robot path planning problems on graphs. Our results encompass three formulations of the discrete multi-robot path planning problem, including a variant that allows synchronous rotations of robots along fully occupied, disjoint cycles on the graph. Allowing rotation of robots provides a more natural model for multi-robot path planning because robots can communicate.Our optimality objectives are to minimize the total arrival time, the makespan (last arrival time), and the total distance. On the structure side, we show that, in general, these objectives demonstrate a pairwise Pareto optimal structure and cannot be simultaneously optimized. On the computational complexity side, we extend previous work and show that, regardless of the underlying multi-robot path planning problem, these objectives are all intractable to compute. In particular, our NP-hardness proof for the time optimal versions, based on a minimal and direct reduction from the 3-satisfiability problem, shows that these problems remain NP-hard even when there are only two groups of robots (i.e. robots within each group are interchangeable).

What kind of tasks are robots with extremely simple control laws capable of performing? Consider a point robot that navigates by aligning itself to a certain fixed angle relative to the environment boundary, then driving in a straight line. Even without knowing the robot's exact location, basic, noisy odometry and counting sensors can be used to narrow down the robot's possible locations over time. This paper describes methods of determining the possible locations of the robot after the robot has moved a sufficient distance or has impacted the boundary a sufficient number of times.

For the task of transferring a group of robots from one formation to another on a connected graph with unit edge lengths, we provide an efficient hierarchical algorithm that can complete goal assignment and path planning for 10,000 robots on a 250,000 vertex grid in under one second. In the extreme, our algorithm can handle up to one million robots on a grid with one billion vertices in approximately 30 minutes. Perhaps more importantly, we prove that with high probability, the algorithm supplies paths with total distance within a constant multiple of the optimal total distance. Furthermore, our hierarchical method also allows these paths to be scheduled with a tight completion time guarantee. In practice, our implementation yields a total path distance less than two times of the true optimum and a much shorter completion time.

We present a framework based on graph search for navigation in the plane with a variety of topological constraints. The method is based on modifying a standard graph-based navigation approach to keep an additional state variable that encodes topological information about the path. The topological information is represented by a sequence of virtual sensor beam crossings. By considering classes of beam crossing sequences to be equivalent under certain equivalence relations, we obtain a general method for planning with topological constraints that subsumes existing approaches while admitting more favorable representational characteristics. We provide experimental results that validate the approach and show how the planner can be used to find loop paths for autonomous surveillance problems, simultaneously satisfying minimum-cost objectives and in dynamic environments. As an additional application, we demonstrate the use of our planner on the PR2 robot for automated building of 3D object models.

The problem of optimal feedback planning under prediction uncertainties among static obstacles is considered. A discrete-time stochastic state transition model is defined over a continuous state space. A relation to a continuous “nearby” deterministic model is proven for small time steps; the cost-to-go function of the stochastic model is approximated with that of the deterministic model, and the approximation error is found to be proportional to the time step. This motivates using numerical methods, which are vastly available for solving deterministic problems, to approximate the original stochastic problem. We demonstrate this application using a Simplicial Label Correcting Algorithm. This algorithms uses a piecewise linear discretization to compute the shortest-path plan on a simplicial complex. Additionally, the theoretical error bound between the approximate solution and the exact solution is derived and confirmed during numerical experiments. This paper provides a rigorous analysis as well as algorithmic and implementation details of the proposed model for the stochastic shortest path problem in continuous spaces with obstacles.

Recent work has produced methods to solve the winding-constrained optimal feedback navigation problem. Given the start and the goal positions and the winding constraints, the solution to this problem is a feedback vector field such that, when integrated from the start, the trajectory is the shortest path connecting the start and the goal which satisfies given constraints. Such constraints intuitively restrict the direction and the number of times the path winds around given planar regions. We formulate a continuous version of this problem that contrasts with the discrete treatments previously presented. This leads to a geometrical characterization of the problem for which simplicial complex approximation is particularly useful. Thus, it yields theoretical insight as well as a practical algorithm for approximating the continuous problem using an efficient and high-accuracy heuristic-driven front propagation method on simplicial meshes. Experimental results are given evaluating the solution quality and efficiency of the method versus methods based on the discrete formulation and without using heuristics.

In this paper, we study the problem of optimal multi-robot path planning (MPP) on graphs. We propose two multiflow based integer linear programming (ILP) models that compute minimum last arrival time and minimum total distance solutions for our MPP formulation, respectively. The resulting algorithms from these ILP models are complete and guaranteed to yield true optimal solutions. In addition, our flexible framework can easily accommodate other variants of the MPP problem. Focusing on the time optimal algorithm, we evaluate its performance, both as a stand alone algorithm and as a generic heuristic for quickly solving large problem instances. Computational results confirm the effectiveness of our method.

This paper examines the problem of determining the distribution of a number of indistinguishable moving bodies located in regions separated by sensor beams that can detect whether a body moves across them. We characterize the conditions under which an exact distribution of bodies can be determined, and compute bounds on the expected number of sensor observations required to determine this exact distribution for a certain movement model of the bodies.

A robot navigates in a polygonal region populated by a set of partially distinguishable landmarks. The robot's motion primitives consist of actions of the form “drive toward a landmark of class x”. To effectively navigate, the robot must always be able to see a landmark. Also, if the robot sees two landmarks of the same class, its motion primitives become ambiguous. Finally, if the robot wishes to navigate from landmark s0to landmark sgoalwith a simple graph search algorithm, then there must be a sequence of landmarks [s0, s1, s2, ..., sk= sgoal], in which landmark siis visible from si-1. Given these three conditions, how many landmark classes are required for navigation in a given polygon P? We call this minimum number of landmark classes the connected landmark class number, denotedχCL(P). We study this problem for the monotone polygons, an important family of polygons that are frequently generated as intermediate steps in other decomposition algorithms. We demonstrate that for all odd k, there exists a monotone polygon Mkwith 3 over 4 (k2+ 2k + 1) vertices such thatχCL(P) ≥ k. We also demonstrate that for any n-vertex monotone polygon P,χCL(P) ≤ n/3 + 12.

This paper introduces and solves a problem of maintaining the distribution of hidden targets that move outside the field of view while a sensor sweep is being performed, resulting in a generalization of the sensing aspect of visibility-based pursuit-evasion games. Our solution first applies information space concepts to significantly reduce the general complexity so that information is processed only when the shadow region (all points invisible to the sensors) changes combinatorially or targets pass in and out of the field of view. The cases of distinguishable, partially distinguishable, and completely indistinguishable targets are handled. Depending on whether the targets move nondeterministically or probabilistically, more specific classes of problems are formulated. For each case, efficient filtering algorithms are introduced, implemented, and demonstrated that provide critical information for tasks such as counting, herding, pursuit evasion, and situational awareness.

Suppose that two members of a finite point guard set S within a polygon P must be given different colors if their visible regions overlap, and that every point in P is visible from some point in S. The chromatic art gallery problem, introduced in [7], asks for the minimum number of colors required to color any guard set (not necessarily a minimal guard set) of P. We study two related problems. First, given a polygon P and a guard set S of P, can the members of S be efficiently and optimally colored so that no two members of S that have overlapping visibility regions have the same color? Second, given a polygon P and a set of candidate guard locations N, is it possible to efficiently and optimally choose the guard set S ⊆ N that requires the minimum number of colors? We provide an algorithm that solves the first question in polynomial time, and demonstrate the NP-hardness of the second question. Both questions are motivated by common robot tasks such as mapping and surveillance.

Given a story from an agent (sensor outputs from a robot or a tale told by a human) and recordings from a spare network of heterogeneous sensors, this paper provides efficient algorithms that validate whether it is possible to reconstruct a path compatible with the sensor recordings that is also "close" to the agent's story. In solving the proposed problems, we show that effective exploitation of a unique finite automaton structure yields time complexity linear in both the length of the story and the length of the sensor observation history. Besides immediate applicability towards security and forensics problems, the idea of behavior validation using external sensors also appears promising in complementing design time model verification.

We consider the problem of determining the paths of multiple, unpredictable moving bodies in a cluttered environment using weak detection sensors that provide simple crossing information. Each sensor is a beam that, when broken, provides the direction of the crossing (one bit) and nothing else. Using a simple network of beams, the individual paths are separated and reconstructed as well as possible, up to combinatorial information about the route taken. In this setup, simple filtering algorithms are introduced, and a low-cost hardware implementation that demonstrates the practicality of the approach is shown. The results may apply in settings such as verification of multirobot system execution, surveillance and security, and unobtrusive behavioral monitoring for wildlife and the elderly.

This paper considers a robot that moves in a plane and is only able to sense the distance order of landmarks with respect to its current position. The robot has no access to either metric information about the location of landmarks and its own position, or to odometry or speed controls. We propose several algorithms for the robot that allow it to navigate to certain points in the plane and to learn global information about the landmark locations. We, furthermore, demonstrate example tasks, such as convex hull computation, that can be performed using this information.

This paper introduces space-filling trees and analyzes them in the context of sampling-based motion planning. Space-filling trees are analogous to space-filling curves, but have a branching, tree-like structure, and are defined by an incremental process that results in a tree for which every point in the space has a finite-length path that converges to it. In contrast to space-filling curves, individual paths in the tree are short, allowing any part of the space to be quickly reached from the root. We compare some basic constructions of space-filling trees to Rapidly-exploring Random Trees (RRTs), which underlie a number of popular algorithms used for sampling-based motion planning. We characterize several key tree properties related to path quality and the overall efficiency of exploration and conclude with a number of open mathematical questions.

This paper considers the Euclidean shortest path problem among obstacles in ℝn. Adaptations of Dijkstra's and A* algorithms are introduced that compute the approximate cost-to-go function over a simplicial complex embedded in the free space. Interpolation methods are carefully designed and analyzed so that they are proven to converge numerically to the optimal cost-to-go function. As the result, the computed function produces approximately optimal trajectories. The methods are implemented and demonstrated on 2D and 3D examples. As expected, the simplicial A* algorithm significantly improves performance over the simplicial Dijkstra's algorithm.

This paper defines and analyzes a simple robot with local sensors that moves in an unknown polygonal environment. The robot can execute wall-following motions and can traverse the interior of the environment only when following parallel to an edge. The robot has no global sensors that would allow precise mapping or localization. Special information spaces are introduced for this particular model. Using these, strategies are presented to solve several tasks: 1) counting vertices, 2) computing the path winding number, 3) learning a combinatorial map, which is called the cut ordering, that encodes partial geometric information, and 4) solving pursuit-evasion problems.

We present exploration and mapping strategies for a mobile robot moving among a finite collection of convex obstacles in the plane. The obstacles are unknown to the robot, which does not have access to coordinates and cannot measure distances or angles. The robot has a unique sensor, called the gap sensor, that tracks the direction of the depth discontinuities in the robot's visibility region. Furthermore, the robot can only move towards depth discontinuities. As the robot moves, the depth discontinuities split and merge, and these changes are encoded in a Gap Navigation Tree. We present a strategy for this robot that is guaranteed to explore the whole environment, but that cannot decide whether the exploration has been completed. If in addition it is assumed that the robot has access to a pebble, which is an identifiable point that the robot can manipulate, then we prove that the robot can decide (in polynomial time in the number of obstacles) whether the environment has been completely explored. For this, the robot is able to distinguish every obstacle using only the gap sensor and a single pebble. These results are a continuation of our previous work on gap sensing for multiply connected environments, in which we reduce the sensing requirements for the robot by constraining the shape of the obstacles.

This paper introduces a Bayesian filter that is specifically designed for counting targets that move outside of the field of view while performing a sensor sweep. Information space concepts are used to dramatically reduce the filter complexity so that information is processed only when the shadow region (all points invisible to the sensors) changes combinatorially or targets pass in and out of view. Previous work assumed perfect observations; however, this paper extends the approach to enable probabilistic disturbances. Practical algorithms are introduced, implemented, and demonstrated for computing the filter outputs based on realistic data.

A novel criterion is introduced for assessing the diversity of a collection of paths or trajectories. The main idea is the notion of survivability, which measures the likelihood that numerous paths are obstructed by the same obstacle. This helps to improve robustness with respect to collision, which is an important challenge in the design of real-time planning algorithms. Efficient algorithms are presented for computing the survivability criterion and for selecting a subset of paths that optimize survivability from a larger collection. The algorithms are implemented and solutions are illustrated for two different systems. Chi-square tests are used to show uniform coverage obtained by using the computed paths in a simple breadth-first search. Random obstacle placement is used to show superior robustness of these primitives compared to uniform sampling of the control space.

This paper introduces a sensor-based planning algorithm that uses less sensing information than any others within the family of bug algorithms. The robot is unable to access precise information regarding position coordinates, angular coordinates, time, or odometry, but is nevertheless able to navigate itself to a goal among unknown piecewise-analytic obstacles in the plane. The only sensor providing real values is an intensity sensor, which measures the signal strength emanating from the goal. The signal intensity function may or may not be symmetric; the main requirement is that the level sets are concentric images of simple closed curves, i.e. topological circles. Convergence analysis and distance bounds are established for the presented approach.

We present a global vector field computation algorithm in configuration spaces for smooth feedback motion planning. Our algorithm performs approximate cell decomposition in the configuration space and approximates the free space using rectanguloid cells. We compute a smooth local vector field for each cell in the free space and address the issue of the smooth composition of the local vector fields between the non-uniform adjacent cells. We show that the integral curve over the computed vector field is guaranteed to converge to the goal configuration, be collision-free, and maintain Cinfinsmoothness. As compared to prior approaches, our algorithm works well on non-convex robots and obstacles.We demonstrate its performance on planar robots with 2 or 3 DOFs, articulated robots composed of 3 serial links and multi-robot systems with 6 DOFs.

Researchers have addressed the localization problem for mobile robots using many different kinds of sensors, including rangefinders, cameras, and odometers. In this paper, we consider localization using a robot that is virtually "blind", having only a clock and contact sensor at its disposal. This represents a drastic reduction in sensing requirements, even in light of existing work that considers localization with limited sensing. We present probabilistic techniques that represent and update the robot's position uncertainty and algorithms to reduce this uncertainty. We demonstrate the experimental effectiveness of these methods using a Roomba autonomous vacuum cleaner robot in laboratory environments.

This paper addresses problems of inferring the locations of moving agents from combinatorial data extracted by robots that carry sensors. The agents move unpredictably and may be fully distinguishable, partially distinguishable, or completely indistinguishable. The key is to introduce information spaces that extract and maintain combinatorial sensing information. This leads to monitoring the changes in connected components of the shadow region, which is the set of points not visible to any sensors at a given time. When used in combination with a path generator for the robots, the approach solves problems such as counting the number of agents, determining movements of teams of agents, and solving pursuit-evasion problems. An implementation with examples is presented.

Sampling-based nonholonomic and kinodynamic planning iteratively constructs solutions with sampled controls. A constructed trajectory is returned as an acceptable solution if its ldquogaps,rdquo including discontinuities within the trajectory and mismatches between the terminal and goal states, are within a given gap tolerance. For a given coarseness in the sampling of the control space, finding a trajectory with a small gap tolerance might be either impossible or extremely expensive. In this paper, we propose an efficient trajectory perturbation method, which complements existing steering and perturbation methods, enabling these sampling-based algorithms to quickly obtain solutions by reducing large gaps in constructed trajectories. Our method uses system symmetry, e.g., invariance of dynamics with respect to certain state transformations, to achieve efficient gap reduction by evaluating trajectory final state with a constant-time operation, and, naturally, generating the admissible perturbed trajectories. Simulation results demonstrate dramatic performance improvement for unidirectional, bidirectional, and PRM-based sampling-based algorithms with the proposed enhancement with respect to their basic counterparts on different systems: one with the second-order dynamics, one with nonholonomic constraints, and one with two different modes.

Computing optimal paths for mobile robots is an interesting and important problem. This paper presents a method to compute the shortest path for a differential-drive mobile robot, which is a disc, among piecewise smooth and convex obstacles. To obtain a well-defined notion of shortest, the total amount of wheel rotation is optimized. We use recent characterization of minimum wheel-rotation paths for differential-drive mobile robots with no obstacles. We reduce the search for the shortest path to the search on a finite nonholonomic visibility graph. Edges of the graph are either minimum wheel-rotation trajectories inside the free space or trajectories on the boundary of obstacle region. Vertices of the graph are initial and goal configurations and points on the boundary of obstacle region. We call the search graph a nonholonomic visibility graph because the jump condition of the Pontryagin maximum principle gives a necessary condition which is reminiscent of bitangency in well-known visibility graphs. To the best of our knowledge, this is the first progress on the problem

This paper characterizes the information space of a robot moving in the plane with limited sensing. The robot has a landmark detector, which provides the cyclic order of the landmarks around the robot, and it also has a touch sensor, that indicates when the robot is in contact with the environment boundary. The robot cannot measure any precise distances or angles, and does not have an odometer or a compass. We propose to characterize the information space associated with such robot through the swap cell decomposition. We show how to construct such decomposition through its dual, called the swap graph, using two kinds of feedback motion commands based on the landmarks sensed.

We introduce a method for constructing provably safe smooth feedback laws for car-like robots in obstacle-cluttered polygonal environments. The robot is taken to be a point with motion that must satisfy bounded path curvature constraints. We construct a global feedback plan (or control policy) by partitioning the environment into convex cells, computing a discrete plan on the resulting cell complex, and generating local control laws on the state space that are safe, consistent with the high level plan, and satisfy smoothness conditions. The trajectories of the resulting global feedback plan are smooth and stabilize the position of the robot in the plane, neglecting the orientation.

Robots must complete their tasks in spite of unreliable actuators and limited, noisy sensing. In this paper, we consider the information requirements of such tasks. What sensing and actuation abilities are needed to complete a given task? Are some robot systems provably "more powerful" than others? Can we find meaningful equivalence classes of robot systems? This line of research is inspired by the theory of computation, which has produced similar results for abstract computing machines. The basic idea is a dominance relation over robot systems that formalizes the idea that some robots are stronger than others. We show that this definition is directly related to the robots' ability to complete tasks. Our prior work in this area assumes perfect control and sensing, requires that the robot begin with a single fixed initial condition within a known environment, and models of time as a sequence of variable-length discrete stages, rather than as a continuum. In this paper, we substantially improve upon that earlier work by addressing these problems.

Localization is a fundamental problem for many kinds of mobile robots. Sensor systems of varying ability have been proposed and successfully used to solve the problem. This paper probes the lower limits of this range by describing three extremely simple robot models and addresses the active localization problem for each. The robot, whose configuration is composed of its position and orientation, moves in a fully-known, simply connected polygonal environment. We pose the localization task as a planning problem in the robot's information space, which encapsulates the uncertainty in the robot's configuration. We consider robots equipped with: 1) angular and linear odometers; 2) a compass and contact sensor and; 3) an angular odometer and contact sensor. We present localization algorithms for models 1 and 2 and show that no algorithm exists for model 3. An implementation with simulation examples is presented.

This paper considers what can be accomplished using a mobile robot that has limited sensing. For navigation and mapping, the robot has only one sensor, which tracks the directions of depth discontinuities. There are no coordinates, and the robot is given a motion primitive that allows it to move toward discontinuities. The robot is incapable of performing localization or measuring any distances or angles. Nevertheless, when dropped into an unknown planar environment, the robot builds a data structure, called the gap navigation tree, which enables it to navigate optimally in terms of Euclidean distance traveled. In a sense, the robot is able to learn the critical information contained in the classical shortest-path roadmap, although surprisingly it is unable to extract metric information. We prove these results for the case of a point robot placed into a simply connected, piecewise-analytic planar environment. The case of multiply connected environments is also addressed, in which it is shown that further sensing assumptions are needed. Due to the limited sensor given to the robot, globally optimal navigation is impossible; however, our approach achieves locally optimal (within a homotopy class) navigation, which is the best that is theoretically possible under this robot model.

The cost of nearest-neighbor (NN) calls is one of the bottlenecks in the performance of sampling-based motion-planning algorithms. Therefore, it is crucial to develop efficient techniques for NN searching in configuration spaces arising in motion planning. In this paper, we present and implement an algorithm for performing NN queries in Cartesian products of R, S1, and RP3, the most common topological spaces in the context of motion planning. Our approach extends the algorithm based on kd-trees, called ANN, developed by Arya and Mount for Euclidean spaces. We prove the correctness of the algorithm and illustrate substantial performance improvement over the brute-force approach and several existing NN packages developed for general metric spaces. Our experimental results demonstrate a clear advantage of using the proposed method for both probabilistic roadmaps and rapidly exploring random trees

Characterizing optimal paths for mobile robots is an interesting, important, and challenging endeavor. Not only they are interesting with respect to the optimized criteria, but also they offer a family of motion primitives that can be used for motion planning in the presence of obstacles. This paper presents characterization of shortest paths for differential-drive mobile robots, with the goal of classifying solutions in the spirit of Dubins curves and Reeds-Shepp curves for car-like robots. To obtain a well-defined notion of shortest., the total amount of wheel rotation is optimized. Using Pontryagin maximum principle and other tools, we establish the existence of optimal trajectories, and derive the set of optimal paths. Some Reeds-Shepp curves appear in the set of optimal paths, whereas there are optimal paths which are different from Reeds-Shepp curves. To the best of our knowledge, this is the first progress on the problem

In this paper, we present an incremental, multiresolution motion planning algorithm designed for systems with differential constraints. Planning for these systems is more difficult than ordinary path planning due to the presence of momentum (drift) or nonholonomic velocity constraints. Given a motion planning problem for such a system and that a solution to the problem exists, then a finite reachability graph containing a solution trajectory is guaranteed to exist, under very reasonable conditions. In general, this graph can be generated using sufficiently dense input space sampling, sufficiently small time step, and sufficiently large tree depth. We show how to find and search such a tree in an incremental, multiresolution way. We prove the completeness of our algorithm, discuss related practical concerns, and show experimental results for several systems

We present a localization method for robots equipped with only a compass, a contact sensor and a map of the environment. In this framework, a localization strategy can be described as a sequence of directions in which the robot moves maximally. We show that a localizing sequence exists for any simply connected polygonal environment by presenting an algorithm for computing such a sequence. We have implemented the algorithm and we present several computed examples. We also show that the sensing model is minimal by showing that replacement of the compass by an angular odometer precludes the possibility of performing localization.

Sampling-based planners have solved difficult problems in many applications of motion planning in recent years. In particular, techniques based on the Rapidly-exploring Random Trees (RRTs) have generated highly successful single-query planners. Even though RRTs work well on many problems, they have weaknesses which cause them to explore slowly when the sampling domain is not well adapted to the problem. In this paper we characterize these issues and propose a general framework for minimizing their effect. We develop and implement a simple new planner which shows significant improvement over existing RRT-based planners. In the worst cases, the performance appears to be only slightly worse in comparison to the original RRT, and for many problems it performs orders of magnitude better.

Sampling based planners have become increasingly efficient in solving the problems of classical motion planning and its applications. In particular, techniques based on the rapidly-exploring random trees (RRTs) have generated highly successful single-query planners. Recently, a variant of this planner called dynamic-domain RRT was introduced by Yershova et al. (2005). It relies on a new sampling scheme that improves the performance of the RRT approach on many motion planning problems. One of the drawbacks of this method is that it introduces a new parameter that requires careful tuning. In this paper we analyze the influence of this parameter and propose a new variant of the dynamic-domain RRT, which iteratively adapts the sampling domain for the Voronoi region of each node during the search process. This allows automatic tuning of the parameter and significantly increases the robustness of the algorithm. The resulting variant of the algorithm has been tested on several path planning problems.

Although sampling-based planning algorithms have been extensively used to approximately solve motion planning problems with differential constraints, gaps usually appear in their solution trajectories due to various factors. Higher precision may be requested, but as we show in this paper, this dramatically increases the computational cost. In practice, this could mean that a solution would not be found in a reasonable amount of time. In this paper, we substantially improve the performance of an RRT-based algorithm by planning low precision solutions, and then refining their quality by employing a gap reduction technique that exploits group symmetries of the system to avoid costly numerical integrations. This technique also allows PRMs to be extended to problems with differential constraints, even when no high-quality steering method exists.

We present an algorithm that computes the complete set of Pareto-optimal coordination strategies for two translating polygonal robots in the plane. A collision-free acyclic roadmap of piecewise-linear paths is given on which the two robots move. The robots have a maximum speed and are capable of instantly switching between any two arbitrary speeds. Each robot would like to minimize its travel time independently. The Pareto-optimal solutions are the ones for which there exist no solutions that are better for both robots. The algorithm computes exact solutions in time O(mn/sup 2/ log n), in which m is the number of paths in the roadmap, n is the number of coordination space vertices. An implementation is presented.

We discuss theoretical and practical issues related to using Rapidly-Exploring Random Trees (RRTs) to incrementally reduce dispersion in the configuration space. The original RRT planners use randomization to create Voronoi bias, which causes the search trees to rapidly explore the state space. We introduce RRT-like planners based on exact Voronoi diagram computation, as well as sampling-based algorithms which approximate their behavior. We give experimental results illustrating how the new algorithms explore the configuration space and how they compare with existing RRT algorithms. Initial results show that our algorithms are advantageous compared to existing RRTs, especially with respect to the number of collision checks and nodes in the search tree.

This paper addresses the problem of generating uniform deterministic samples over the spheres and the three-dimensional rotation group, SO(3). The target applications include motion planning, optimization, and verification problems in robotics and in related areas, such as graphics, control theory and computational biology. We introduce an infinite sequence of samples that is shown to achieve: 1) low-dispersion, which aids in the development of resolution complete algorithms, 2) lattice structure, which allows easy neighbor identification that is comparable to what is obtained for a grid in /spl Ropf//sup d/, and 3) incremental quality, which is similar to that obtained by random sampling. The sequence is demonstrated in a sampling-based motion planning algorithm.

In this paper we present an online algorithm for pursuit-evasion in a unknown simply connected environment, for one pursuer that has minimal sensing and carries a set of stationary sentries that it can drop off and pick up during the pursuit. In our sensing model, the pursuer is only able to detect discontinuities in depth information (gaps), and it is able to find all of the evaders without any explicit localization or geometric information, by using a gap navigation tree. The strategy is based on growing an evader-free region, by reading "exploration" schedules from the gap navigation tree, that is constructed online. We prove that a pursuer with k + 1 sentries can clear any environment that could be cleared by k pursuers using the algorithm in L.J. Guibas et al. (1999), which required a complete map and perfect sensing.

This paper presents a sampling-based approach to computing and executing feedback-motion strategies by defining a global navigation function over a collection of neighborhoods in configuration space. The collection of neighborhoods and their underlying connectivity structure are captured by a sampling-based neighborhood graph (SNG), on which navigation functions are built. The SNG construction algorithm incrementally places new neighborhoods in the configuration space, using distance information provided by existing collision-detection algorithms. A termination condition indicates the probability that a specified fraction of the space is covered. Our implementation illustrates the approach for rigid and articulated bodies with up to six-dimensional configuration spaces. Even over such spaces, rapid online responses to unpredictable configuration changes can be made in a few microseconds on standard PC hardware. Furthermore, if the goal is changed, an updated navigation function can be quickly computed without performing additional collision checking.

We present deterministic sequences for use in sampling-based approaches to motion planning. They simultaneously combine the qualities found in many other sequences: i) the incremental and self-avoiding tendencies of pseudo-random sequences, ii) the lattice structure provided by multiresolution grids, and iii) low-discrepancy and low-dispersion measures of uniformity provided by quasi-random sequences. The resulting sequences can be considered as multiresolution grids in which points may be added one at a time, while satisfying the sampling qualities at each iteration. An efficient, recursive algorithm for generating the sequences is presented and implemented. Early experiments show promising performance by using the samples in search algorithms to solve motion planning problems.

In this paper we develop a dynamite data structure, useful for robot navigation in an unknown, simply connected planar environment. The guiding philosophy in this work is to avoid traditional problems such as complete map building and localization by constructing a minimal representation based entirely on critical events in online sensor measurements made by the robot. Furthermore, this representation provides a sensor-feedback motion strategy that guides the robot along an optimal trajectory between any two environment locations, and allows the search of static targets, even though there is no geometric map of the environment. We present algorithms for building the data structure in an unknown environment, and for using it to perform optimal navigation. We implemented these algorithms on a real mobile robot. Results are presented in which the robot builds the data structure online, and is able to use it without needing a global reference frame. Simulation results are shown to demonstrate how the robot is able to find interesting objects in the environment.

We address the problem of eliminating gaps in paths that are constructed by some nonholonomic and kinodynamic motion planning algorithms. In many of these algorithms, control inputs at each planning step are chosen from a finite set, obtained from discretization of the available control set. While this approach is attractive for computational reasons, it can generate gaps, or discontinuities, either between path segments or between the final state and the desired goal. For the purpose of reducing gaps, the original control set and continuous time interval can be utilized, and perturbations may be applied to incrementally optimize the gap error while respecting collision constraints. By exploiting Lie group symmetries, which emerge in a broad class of robot systems, we are able to avoid costly numerical integrations that usually occur in each step of gradient-based optimization techniques. It is hoped that the approach can ultimately lead to faster planning algorithms by allowing coarser discretizations of time and the available input set, with the understanding that later refinements can be made efficiently.

In this paper we present an algorithm to build a sensor-based, dynamic data structure useful for robot navigation in an unknown, multiply-connected planar environment. This data structure offers a robust framework for robot navigation, avoiding the need of a complete geometric map or explicit localization, by building a minimal representation based entirely on critical events in online sensor measurements made by the robot. There are two sensing requirements for the robot: it must detect when it is close to the walls, to perform wall-following reliably, and it must be able to detect discontinuities in depth information. It is also assumed that the robot is able to drop, detect and recover a marker. The navigation paths generated are optimal up to the homotopy class to which the paths belong, even though no distance information is measured.

We present and implement an efficient algorithm for performing nearest-neighbor queries in topological spaces that usually arise in the context of motion planning. Our approach extends the Kd tree-based ANN algorithm, which was developed by Arya and Mount (1993) for Euclidean spaces. We argue the correctness of the algorithm and illustrate its efficiency through computed examples. We have applied the algorithm to both probabilistic roadmaps (PRMs) and rapidly-exploring random trees (RRTs). Substantial performance improvements are shown for motion planning examples.

Trajectory design for high-dimensional systems with nonconvex constraints has considerable success recently; however, the resolution completeness analysis for various methods is insufficient. In this paper, based on Lipschitz condition and the accessibility graph, conditions for resolution completeness are derived. By combining the systematic search with randomized technique, a randomized planner is transformed to be a deterministic resolution complete planner, which shows reliable performance in the simulation.

We present an algorithm for a pair of pursuers, each with one rotating beam (flashlight, laser or a camera), searching for an unpredictable, moving target in a 2D environment (simple polygon). Given a polygon with n edges, the algorithm decides in time O(n/sup 4/) whether it can be cleared by the pursuers, and if so, constructs a search schedule. The pursuers are allowed to move on. the boundary and in the interior of the polygon. They are not required to maintain mutual visibility throughout the pursuit.

As a general framework to determine a collision-free feedback motion strategies, the Random Neighborhood Graph (RNG) approach [19] defines a global navigation function over an approximate representation of the free configuration. In this paper, we improve the RNG approach in several aspects. We present an ANN-accelerated RNG construction a1gorithm to achieve near 1ogarithmic running time in each iteration of the RNG expansion. Two probabilistic termination conditions of the RNG constructibn a1gorithm are presented and analyzed. To help overcome the difficulty of narrow corridors, we also introduce a randoniized perturbation algorithm to enhance the sampling quality. Our implementation illustrates a significant performance improvement.

We propose the use of quasi-random sampling techniques for path planning in high-dimensional configuration spaces. Following similar trends from related numerical computation fields, we show several advantages offered by these techniques in comparison to random sampling. Our ideas are evaluated in the context of the probabilistic roadmap (PRM) framework. Two quasi-random variants of PRM- based planners are proposed: 1) a classical PRM with quasi-random sampling; and 2) a quasi-random lazy-PRM. Both have been implemented, and are shown through experiments to offer some performance advantages in comparison to their randomized counterparts.

We consider the problem of searching for an unpredictable moving target, using a robot that lacks a map of the environment, lacks the ability to construct a map, and has imperfect navigation ability. We present a complete algorithm, which yields a motion strategy for the robot that guarantees the elusive target will be detected, if such a strategy exists. It is assumed that the robot has an omnidirectional sensing device that is used to detect moving targets and also discontinuities in depth data in a 2D environment. We also show that the robot has the same problem solving power as a robot that has a complete map and perfect navigation abilities. The algorithm has been implemented in simulation, and some examples are shown.

This paper addresses the trajectory design for generic problems that involve: (1) complicated global constraints that include nonconvex obstacles, (2) nonlinear equations of motion that involve substantial drift due to momentum, and (3) a high-dimensional state space. Our approach to these challenging problems is to develop randomized planning algorithms based on rapidly-exploring random trees (RRTs). RRTs use metric-induced heuristics to conduct a greedy exploration of the state space; however, performance substantially degrades when the chosen metric does not adequately reflect the true cost-to-go. In this paper, we present a version of the RRT that refines its exploration strategy in the presence of a poor metric. Experiments on problems in vehicle dynamics and spacecraft navigation indicate substantial performance improvement over existing techniques.

We consider the problem of visually searching for an unpredictable target that can move arbitrarily fast in a simply-connected two-dimensional curved environment. A complete algorithm is presented and is based on critical visibility events that occur because of inflections and bitangents on the environment boundary. By generalizing the notion of inflections and bitangents to polygonal and piecewise-smooth environments, the approach is considered as a step toward developing pursuit-evasion strategies that have little dependency on the representation of the environment.

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.

We present an algorithm for a single pursuer with one flashlight searching for an unpredictable, moving target in a 213 environment.For a simple polygon with n edges, the algorithm uses O(n 2) time to decide whether the polygon can be cleared by a 1-searcher, and if so, constructs a search schedule.The key ideas in this algorithm include a representation called the visibility obstruction diagram and a decomposition of this diagram based on a skeleton that arises from critical visibility events.An implementation is presented along with a computed example.

A simple and efficient randomized algorithm is presented for solving single-query path planning problems in high-dimensional configuration spaces. The method works by incrementally building two rapidly-exploring random trees (RRTs) rooted at the start and the goal configurations. The trees each explore space around them and also advance towards each other through, the use of a simple greedy heuristic. Although originally designed to plan motions for a human arm (modeled as a 7-DOF kinematic chain) for the automatic graphic animation of collision-free grasping and manipulation tasks, the algorithm has been successfully applied to a variety of path planning problems. Computed examples include generating collision-free motions for rigid objects in 2D and 3D, and collision-free manipulation motions for a 6-DOF PUMA arm in a 3D workspace. Some basic theoretical analysis is also presented.

We present an algorithm for searching a 2D environment for unpredictable moving targets using only beam-based detection. One or more pursuers move along the environment boundary, and carry a rotating beam that detects evaders. The beam could correspond in practice to a laser or a camera. The task is to compute motions for pursuers and their beams that ensure that all evaders will be detected. For a 2D polygonal environment, we solve a long-standing open problem by presenting a complete O(n/sup 3/)-time algorithm that is guaranteed to find a successful motion strategy for a single pursuer and its beam, if a solution exists. This algorithm is extended to the case of coordinating multiple pursuers, but the number of pursuers used in a solution is not necessarily optimal. An implementation is presented, and several computed examples are shown.

This paper presents a randomized framework for computing feedback motion strategies, by defining a global navigation function over a collection of spherical balls in the configuration space. If the goal is changed, an updated navigation function can be quickly computed, offering benefits similar to the fast multiple queries permitted by the probabilistic roadmap approach to path planning. Our choice of balls is motivated in part by recent tools from computational geometry which compute point locations and arrangements efficiently without significant dependence on dimension. We present a construction algorithm that includes a Bayesian termination condition based on the probability that a specified fraction of the free space is covered. A basic implementation illustrates the framework for rigid and articulated bodies with up to five-dimensional configuration spaces.

The paper presents a state-space perspective on the kinodynamic planning problem, and introduces a randomized path planning technique that computes collision-free kinodynamic trajectories for high degree-of-freedom problems. By using a state space formulation, the kinodynamic planning problem is treated as a 2n-dimensional nonholonomic planning problem, derived from an n-dimensional configuration space. The state space serves the same role as the configuration space for basic path planning. The bases for the approach is the construction of a tree that attempts to rapidly and uniformly explore the state space, offering benefits that are similar to those obtained by successful randomized planning methods, but applies to a much broader class of problems. Some preliminary results are discussed for an implementation that determines the kinodynamic trajectories for hovercrafts and satellites in cluttered environments resulting in state spaces of up to twelve dimensions.

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.

We consider the problem of visually searching for an unpredictable target that can move arbitrarily fast in a simply-connected, curved, two-dimensional environment. A complete algorithm is presented that is guaranteed to find the elusive target if it is possible for a single pursuer. The key to the algorithm is a cell decomposition based on critical visibility events that occur because of inflections and bitangents of the environment boundary. We have implemented the cell decomposition algorithm, and show several computed examples. The technique is an extension and simplification of a previous technique for searching a polygonal environment. Our solution can also be considered as a step towards a unified approach to pursuit-evasion strategies that have little dependency on the representation of the environment.

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 work makes two contributions to geometric motion planning for multiple robots: 1) motion plans are computed that simultaneously optimize an independent performance measure for each robot; 2) a general spectrum is defined between decoupled and centralized planning, in which we introduce coordination along independent roadmaps. By considering independent performance measures, we introduce a form of optimality that is consistent with concepts from multiobjective optimization and game theory literature. We present implemented, multiple-robot motion planning algorithms that are derived from the principle of optimality, for three problem classes along the spectrum between centralized and decoupled planning: 1) coordination along fixed, independent paths; 2) coordination along independent roadmaps; and 3) general, unconstrained motion planning. Computed examples are presented for all three problem classes that illustrate the concepts and algorithms.

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.

Numerical computation with Bayesian posterior densities has recently received much attention both in the applied statistics and image processing communities. This paper surveys previous literature and presents efficient methods for computing marginal density values for image models that have been widely considered in computer vision and image processing. The particular models chosen are a Markov random field (MRF) formulation, implicit polynomial surface models, and parametric polynomial surface models. The computations can be used to make a variety of statistically based decisions, such as assessing region homogeneity for segmentation or performing model selection. Detailed descriptions of the methods are provided, along with demonstrative experiments on real imagery.

This work makes two contributions to geometric motion planning for multiple robots: i) motion plans can be determined that simultaneously optimize an independent performance criterion for each robot; ii) a general spectrum is defined between decoupled and centralized planning. By considering independent performance criteria, we introduce a form of optimality that is consistent with concepts from multi-objective optimization and game theory research. Previous multiple-robot motion planning approaches that consider optimality combine individual criteria into a single criterion. As a result, these methods can fail to find many potentially useful motion plans. We present implemented, multi-robot motion planning algorithms that are derived from the principle of optimality, for three problem classes along the spectrum between centralized and decoupled planning: i) coordination along fixed, independent paths; ii) coordination along independent roadmaps; iii) general, unconstrained motion planning. Several computed examples are presented for all three problem classes that illustrate the concepts and algorithms.

Provides a method for characterizing future configurations under the implementation of a motion strategy in the presence of sensing and control uncertainties. We provide general techniques which can apply to either nondeterministic models of uncertainty (as typically considered in preimage planning research) or probabilistic models. Information-space concepts from modern control theory are utilized to define the notion of a strategy in this general context. We have implemented algorithms and show several computed examples that generalize the forward projection concepts from traditional literature in this area.

Gross-motion planning for assembly is commonly considered as a distinct, isolated step between task sequencing/scheduling and fine-motion planning. In this paper the authors formulate a problem of delivering parts for assembly in a manner that integrates it with both the manufacturing process and the fine motions involved in the final assembly stages. One distinct characteristic of gross-motion planning for assembly is the prevalence of uncertainty involving time-in parts arrival, in request arrival, etc. The authors propose a stochastic representation of the assembly process, and design a state-feedback controller that optimizes the expected time that parts wait to be delivered. This leads to increased performance and a greater likelihood of stability in a manufacturing process. Six specific instances of the general framework are modeled and solved to yield optimal motion strategies for different robots operating under different assembly situations. Several extensions are also discussed.

Presents a framework for analyzing and determining motion plans for a robot that operates in an environment that changes over time in an uncertain manner. The authors first classify sources of uncertainty in motion planning into four categories, and argue that the framework addressed in this paper characterizes an important, yet little-explored category. The authors treat the changing environment in a flexible manner by combining traditional configuration space concepts with a Markov process that models the environment. For this context, the authors then propose the use of a motion strategy, which provides a motion command for the robot for each contingency that it could be confronted with. The authors allow the specification of a desired performance criterion, such as time or distance, and the goal is to determine a motion strategy that is optimal with respect to that criterion. A motion planning problem in this framework is formulated as the design of a stochastic optimal controller.

The authors (1995) have previously presented a framework for analyzing motion plans for a robot that operates in an environment that changes over time in an uncertain manner. In this paper, the authors demonstrate the utility of their framework by applying it to a variety of motion planning problems. Examples are computed for problems that involve a changing configuration space, hazardous regions and shelters, and processing of random service requests. To achieve this, the authors have exploited the powerful principle of optimality, which leads to a dynamic programming-based algorithm for determining optimal strategies. Several computed examples are presented and discussed.

Region-based image segmentation methods require some criterion for determining when to merge regions. This paper presents a novel approach by introducing a Bayesian probability of homogeneity in a general statistical context. The authors' approach does not require parameter estimation and is therefore particularly beneficial for cases in which estimation-based methods are most prone to error: when little information is contained in some of the regions and, therefore, parameter estimates are unreliable. The authors apply this formulation to three distinct parametric model families that have been used in past segmentation schemes: implicit polynomial surfaces, parametric polynomial surfaces, and Gaussian Markov random fields. The authors present results on a variety of real range and intensity images.>

We present a method for analyzing and selecting time-optimal coordination strategies for n robots whose configurations are constrained to lie on a C-space roadmap (which could, for instance, represent a Voronoi diagram). We consider independent objective functionals, associated with each robot, together in a game-theoretic context in which maximal Nash equilibria represent the favorable strategies. Within this framework additional criteria, such as priority or the amount of sacrifice one robot makes, can be applied to select a particular equilibrium. An algorithm that determines all of the maximal Nash equilibria for a given problem is presented along with several computed examples for two and three robots.>

We consider the problem of determining robot manipulation plans when sensing and control uncertainties are specified as conditional probability densities. Traditional approaches are usually based on worst-case error analysis in a methodology known as preimage backchaining. We have developed a general framework for determining sensor-based robot plans by blending ideas from stochastic optimal control and dynamic game theory with traditional preimage backchaining concepts. We argue that the consideration of a precise loss (or performance) functional is crucial to determining and evaluating manipulation plans in a probabilistic setting. We consequently introduce a stochastic, performance preimage that generalizes previous preimage notions. We also present some optimal strategies for planar manipulation tasks that were computed by a dynamic programming-based algorithm.>

A novel Bayesian approach to region merging is described. It directly uses statistical image models to determine the probability that the union of two regions is homogeneous, and does not require parameter estimation. This approach is particularly beneficial for cases in which the merging decision is most likely to be incorrect, i.e., when little information is contained in one or both of the regions and when parameter estimates are unreliable. The formulation is applied to the implicit polynomial surface model for range data, and texture models for intensity images.>

Clustering methods, which are frequently employed for region-based segmentation, are inherently metric based. A fundamental problem with an estimation-based criterion is that as the amount of information in a region decreases, the parameter estimates become extremely unreliable and incorrect decisions are likely to be made. It is shown that clustering need not be metric based. A rigorous region merging probability function is used. It makes use of all information available in the probability densities of a statistical image model. By using this probability function as a termination criterion it is possible to produce segmentations in which all region merges are performed above some level of confidence.>