To the best of our knowledge, an exact solution to the visibility-based pursuit–evasion problem with point agents and polygonal obstacles addressed in this work is not known. Given the above, in this work, we present approximate algorithms, but feasible and with other desirable properties, for such a pursuit–evasion game. Our new method combines asymptotically optimal motion planning based on sampling (more specifically, optimal probabilistic roadmaps) and the value iteration of dynamic programming. In addition, our formulation finds solutions for the evader when there are singular surfaces, which previous work could not find. In this work, we obtain two main theoretical results. We first prove that the proposed discrete formulation is correct (that the method obtains the solution for the discretization of the given configuration space). Subsequently, combining random graph results, Bellman's optimality principle, and limits, it is proved that, as the number of samples tends to infinity, our approximate discrete formulation becomes the continuous formulation corresponding to the Hamilton–Jacobi–Isaacs equation. This results in a feasible method that improves its approximation as the number of samples increases. Simulation experiments in 2-D and 3-D environments with obstacles that are simply and multiplicattively connected exemplify the results of the new method and show the advantages over previous work.

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.

In this article, we study properties of local planners for nonholonomic dynamical systems to achieve asymptotic global optimality in a sampling-based planner, namely, the RRT*. Formal results are presented concerning length optimal trajectories under a nonholonomic metric, more specifically, an analysis about necessary or sufficient conditions for the local planners is provided. The analysis makes use of the case of finding time-optimal trajectories for differential drive robots. Later, relevant concepts for complex robotic systems such as detachability and time dominance are introduced. Detachability is a property over the cost functional such that, if respected, it allows the reusability of previously designed local planners for simpler systems into more complex ones. The introduced concepts are further illustrated through a robotic system comprised of a mobile manipulator robot equipped with a camera in the arm’s end-effector, whose task is to move between states maintaining a desired object within its field of view. Experiments in a physical mobile manipulator robot are shown, which validate the proposed theoretical modeling.

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.

We present the Regression-based Linear Quadratic Regulator (R-LQR), a new approach for determining locally-optimal control feedback policies for robots with non-linear dynamics and non-quadratic cost functions. Our proposal uses a free-derivative algorithm based on local quadratic regressions to obtain the robot motion policy. In addition, our methodology allows to define a notion of scale that translates into the definition of neighborhoods of valid policy and into the exploration of larger areas of the search space to find the optimal policies. The results show that our formulation allows to reach policies with lower costs than existing algorithms and to avoid problems when the behavior of the cost function makes the optimization difficult.

In this paper, we present a complete algorithm for exploration of unknown environments containing disjoint obstacles with multiple robots. We propose a distributed approach considering two main cases. In the first one, the obstacles are distinguishable, i.e., each obstacle is uniquely identifiable, which can be imagined as each obstacle having a different color, and in the second case, the obstacles are not distinguishable. Two possible applications of our algorithms are: 1) Search of a static object in an unknown environment. 2) Damage verification in unknown environments composed by multiple elements (e.g. buildings). The main contributions of this work are the following: 1) The algorithms guarantee exploring the whole environment in finite time even though each robot does not have full information about the part of the environment explored by other robots. 2) The method only requires limited communication between the robots. In both cases distinguishable and indistinguishable obstacles, the robots communicate only at rendezvous. 3) The algorithm scales well to hundreds of robots and obstacles. We tested in several simulations the performance of our algorithms for both cases, in terms of the distance traveled by the robots.

In this paper, we address the pursuit/evasion problem of capturing an omnidirectional evader using a Differential Drive Robot (DDR) in an obstacle-free environment. The goal of the evader is to keep the pursuer farther than the capture distance for as long as possible and for the pursuer the goal is to capture the evader as soon as possible. In [1] an open-loop time-optimal strategy is proposed for this pursuit/evasion problem. In [2] a state feedback-based time-optimal motion policy for the DDR is provided. The time-optimal strategies obtained in [1] are in Nash equilibrium, meaning that any unilateral deviation of a player from the optimal strategies does not provide it a benefit in its payoff. However, Nash equilibrium does not tell if one player deviates from its optimal policy then, does there exist a new strategy for the other player that can take advantage of such deviation? If so, which is the required information to improve the payoff compared with the worst case scenario? In this paper we address those questions, analysing the scenario in which the players deviate from their optimal controls. We show that when the evader deviates from its optimal speed there are cases where there exists a new pursuer motion strategy that reduces the time to capture the evader. The shown cases where the time to capture the evader is reduced require more information about the evader's state. Nevertheless, there are also cases in which despite the availability of new information, the pursuer must stick to the worst case strategy, otherwise it cannot capture the evader.

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

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.

The task addressed in this paper is to plan iteratively a set views in order to reconstruct an object using a mobile manipulator robot with an “eye-in-hand” sensor. The proposed method plans views directly in the configuration space avoiding the need of inverse kinematics. It is based on a fast evaluation and rejection of a set of candidate configurations. The main contributions are: a utility function to rank the views and an evaluation strategy implemented as a series of filters. Given that the candidate views are configurations, motion planning is solved using a rapidly-exploring random tree. The system is experimentally evaluated in simulation, contrasting it with previous work. We also present experiments with a real mobile manipulator robot, demonstrating the effectiveness of our method.

In this paper, we consider the problem of capturing an omnidirectional evader using a differential drive robot in an obstacle-free environment. At the beginning of this game, the evader is at a distance (the capture distance) from the pursuer. The goal of the evader is to keep the pursuer farther than this capture distance for as long as possible. The goal of the pursuer is to capture the evader as soon as possible. In this paper, we make the following contributions. We present closed-form representations of the motion primitives and time-optimal strategies for each player; these strategies are in Nash equilibrium, meaning that any unilateral deviation of each player from these strategies does not provide to such player benefit toward the goal of winning the game. We propose a partition of the playing space into mutually disjoint regions where the strategies of the players are well established. This partition is represented as a graph, which exhibits properties that guarantee global optimality. We also analyze the decision problem of the game and we present the conditions defining the winner.

In this paper, we consider the problem of capturing an omnidirectional evader using a Differential Drive Robot in an obstacle free environment. At the beginning of the game the evader is at a distance L >; l from the pursuer. The pursuer goal is to get closer from the evader than the capture distance l. The goal of the evader is to keep the pursuer at all time farther from it than this capture distance. In this paper, we found closed-form representations of the motion primitives and time-optimal strategies for each player. These strategies are in Nash Equilibrium, meaning that any unilateral deviation of each player from these strategies does not provide to such player benefit toward the goal of winning the game. We also present the condition defining the winner of the game and we construct a solution over the entire reduced space.

In this paper, we present a multi-robot exploration strategy for map-building. We consider a team of robots with different sensing and motion capabilities. We combine geometric and probabilistic reasoning to propose a solution to our problem. We formalize the proposed solution using dynamic programming in states with imperfect information. We apply the dynamic programming technique in a reduced search space that allows us to incrementally explore the environment. We propose realistic sensor models and provide a method to compute the probability of the next sensor reading given the current state of the team of robots based on a Bayesian approach.

In this paper, we address the problem of repairing previously computed plans for searching for an object. The object is sought with a 7 degrees of freedom mobile manipulator robot with an ¿eye-in-hand¿ sensor. The sensor is limited in both range and field of view. Our method computes a set of sensing configurations, which collectively cover the environment with the 3-D visibility region of the limited sensor. An order for visiting sensing configurations, which diminishes the expected value of the time for finding the object is generated. The search plan corresponds mainly to the set of sensing configurations to be visited and the order for visiting those configurations. In this paper, we show that whenever the environment changes locally our plan can also be repaired locally. We base our approach on a 3-D convex regions decomposition dividing the environment. The plan is repaired by generating a new sub-set of sensing configurations and a new order for visiting those configurations, only considering the convex regions related to the change in the map of the 3-D environment. We have implemented all our algorithms, and we present simulation results in realistic environments.

This paper is concerned with determining whether a mobile robot, called the pursuer, is up to maintaining visibility of an antagonist agent, called the evader. This problem, a variant of pursuit-evasion, has been largely studied, following a systematic treatment by increasingly relaxing a number of restrictions. In, we considered a scenario where the pursuer and the evader move at bound speed, traveling around a known, 2D environment, which contains obstacles. Then, considering that, in an attempt to escape, the evader travels the shortest path to reach a potential escape region, we provided a decision procedure that determines whether or not the pursuer is up to maintain visibility of the evader and obtained complexity measures of this surveillance task. In this paper, we prove that there are cases for which an evader may escape only if it does not travel the shortest path to an escapable region. We introduce planning strategies for the movement of the pursuer that keeps track of the evader, even if the evader chooses not to travel the shortest path to an escape region. We also present a sufficient condition for the evader to escape that does not depend on the initial positions of the players. It can be verified only using the environment. All our algorithms have been implemented and we show simulation results.

In this paper we consider the problem of maintaining visibility of a moving evader by a mobile robot, the pursuer, in an environment with obstacles. We simultaneously consider bounded speed for both players and a variable distance separating them. Unlike our previous efforts [R. Murrieta-Cid et al., 2007], we give special attention to the combinatorial problem that arises when searching for a solution through visiting several locations. We approach evader tracking by decomposing the environment into convex regions. We define two graphs: one is called the mutual visibility graph (MVG) and the other the accessibility graph (AG). The MVG provides a sufficient condition to maintain visibility of the evader while the AG defines possible regions to which either the pursuer or the evader may go to. The problem is framed as a non cooperative game. We establish the existence of a solution, based on a k- Min approach, for the following givens: the environment, the initial state of the evader and the pursuer, including their maximal speeds. We show that the problem of finding a solution to this game is NP-complete.

In this paper, we consider the problem of planning optimal paths for a differential-drive robot with limited sensing, that must maintain visibility of a fixed landmark as it navigates in its environment. In particular, we assume that the robot's vision sensor has a limited field of view (FOV), and that the fixed landmark must remain within the FOV throughout the robot's motion. We first investigate the nature of extremal paths that satisfy the FOV constraint. These extremal paths saturate the camera pan angle. We then show that optimal paths are composed of straight-line segments and sections of these these extremal paths. We provide the complete characterization of the shortest paths for the system by partitioning the plane into a set of disjoint regions, such that the structure of the optimal path is invariant over the individual regions

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.

In this paper, we consider the surveillance problem of maintaining visibility at a fixed distance of a mobile evader using a mobile robot equipped with sensors. Optimal motion for the target to escape is found. Symmetrically, an optimal motion strategy for the observer to always maintain visibility of the evader is determined. The optimal motion strategies proposed in this paper are based on critical events. The critical events are defined with respect to the obstacles in the environment.

In this paper we address the problem of generating a motion strategy to find an object in a known 3-D environment as quickly as possible on average. We use a sampling scheme that generates an initial set of sensing locations for the robot and then we propose a convex cover algorithm based on this sampling. Our algorithm tries to reduce the cardinality of the resulting set and has the main advantage of scaling well with the dimensionality of the environment. We then use the resulting convex covering to generate a graph that captures the connectivity of the workspace. Finally, we search this graph to generate trajectories that try to minimize the expected value of the time to find the object.

In this paper we consider the problem of maintaining surveillance of a moving the target by a nonholonomic mobile observer. The observer's goal is to maintain visibility of the target from a predefined, fixed distance, l. The target escapes if (a) it moves behind an obstacle to occlude the observer's view, (b) it causes the observer to collide with an obstacle, or (c) it exploits the nonholonomic constraints on the observer motion to increase its distance from the observer beyond the surveillance distance l. We deal specifically with the situation in which the only constraint on the target's velocity is a bound on speed (i.e., there are no nonholonomic constraints on the target's motion), and the observer is a nonholonomic, differential drive system having bounded speed. We develop the system model, from which we derive a lower bound for the required observer speed. Finally, we consider the effect of obstacles on the observer's ability to successfully track the target.

This work addresses the problem of computing the motions of a robot observer in order to maintain visibility of a moving target at a fixed surveillance distance. In this paper, we deal specifically with the situation in which the observer has bounded velocity. We give necessary conditions for the existence of a surveillance strategy and give an algorithm that generates surveillance strategies.

This work presents the minimal length paths, for a robot that maintains visibility of a landmark. The robot is a differential drive system and has limited sensing capabilities (range and angle of view). The optimal paths are composed of straight lines and curves that saturate the camera pan angle.

In this paper we address the problem of finding time optimal search paths in known environments. In particular, the task is to search a known environment for an object whose unknown location is characterized by a known probability density function (pdf). With this formulation, the time required to find the object is a random variable induced by the choice of search path together with the pdf for the object's location. The optimization problem is to find the path that yields the minimum expected value of the time required to find the object. We propose a two layered approach. Our algorithm first determines an efficient ordering of visiting regions in a decomposition that is defined by critical curves that are related to the aspect graph of the space to be searched. It then generates locally optimal trajectories within each of these regions to construct a complete continuous path. We have implemented this algorithm and present results.

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.

This paper deals with the problem of computing the motions of a robot observer in order to maintain visibility of a moving target. The target moves unpredictably, and the distribution of obstacles in the workspace is known in advance. Our algorithm computes a motion strategy based on partitioning the configuration space and the workspace in non-critical regions separated by critical curves. In this work, the existence of a solution for a given polygon and delay are determined.

In this paper, we propose an approach to solve the problem of finding an object in a polygon which may contain holes. We define an optimal solution as the route that minimizes the expected time it takes to find said object. The object search problem is shown to be NP-hard by reduction, therefore, we propose the heuristic of an utility function, defined as the ratio of a gain over a cost and a greedy algorithm in a reduced search space that is able to explore several steps ahead without incurring in too high computational cost. This approach was implemented and simulation results are shown.

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.

This paper deals with the problem of computing the motions of one or more robot observers in order to maintain visibility of one or several moving targets. The targets are assumed to move unpredictably, and the distribution of obstacles in the workspace is assumed to be known in advance. Our algorithm computes a motion strategy by maximizing the shortest distance to escape $the shortest distance the target needs to move in order to escape the observer's visibility region. Three main points are discussed: 1) the design and implementation of a reactive planner; 2) the integration and testing of such a planner in a robot system which includes perceptual and control capabilities; and 3) the design and simulation of a motion planner for the task of maintaining visibility of two targets using two mobile observers.

In this paper a complete strategy for scene modelling from sensory data acquired in a natural environment is defined. This strategy is applied to outdoor mobile robotics, from environment recognition to landmark extraction. In this work, an environment is understood as a specific kind of landscape, for instance prairie, forest, desert, etc. A landmark is defined as a conspicuous object in the environment. In the context of outdoor mobile robotics a landmark has to be useful to perform localization and navigation tasks.

The goal of this work is to develop techniques that allow one or more robotic observers to operate with full autonomy while accomplishing the task of model building. The planning algorithm operates using certain simple but flexible models of the observer sensor and actuator abilities. We provide techniques that allow us to implement these sensor models on top of the capabilities of the actual (and off-the-shelf) sensors we have. It is worth keeping the following points in mind regarding our goals: 1) even with completely idealized sensing and mobility capabilities, the algorithmic task of model building is quite challenging; 2) computational techniques can be used to approximate and implement these idealized sensors on top of actual sensors; and 3) the quality and success of the generated plans depend significantly on the observer capabilities. The study of this dependency terms of high-level parameters describing the sensors is part of this work.

This paper deals with the development of the use of visual function in order to add useful information for tasks of a mobile robot roving in natural environments. We have proposed and implemented the nominative region model which indicates every region's nature in an image. A color segmentation algorithm provides a synthetic description of the scene. Regions obtained from the segmentation stage are then characterized by their color and texture and afterwards identified in order to obtain their nature (grass, rocks, ...). Probabilistic methods are used to determine the nature of current elements in the environment. Then, one specific landmark is chosen according to its nature and shape and this representation is tracked through an image sequence.