This paper introduces a new approach for continual planning and model learning in relational, non-stationary stochastic environments. Such capabilities are essential for the deployment of sequential decision-making systems in the uncertain and constantly evolving real world. Working in such practical settings with unknown (and non-stationary) transition systems and changing tasks, the proposed framework models gaps in the agent's current state of knowledge and uses them to conduct focused, investigative explorations. Data collected using these explorations is used for learning generalizable probabilistic models for solving the current task despite continual changes in the environment dynamics. Empirical evaluations on several non-stationary benchmark domains show that this approach significantly outperforms planning and RL baselines in terms of sample complexity. Theoretical results show that the system exhibits desirable convergence properties when stationarity holds.

We present a novel approach for solving pursuit-evasion problems where multiple pursuers with limited sensing capabilities are used to detect all possible mobile evaders in a given environment. We make no assumptions about the number, the speed, or the maneuverability of evaders. Our algorithm takes as input a map of the environment and sensor models for the pursuers. We then obtain a graph representation of an environment using a Čech Complex. Even with such a representation, the configuration space grows exponentially with the number of pursuers. In order to address this challenge, we propose an abstraction framework to partition the configuration space into sets of topologically similar configurations that preserve the space of possible evader locations. We validate our approach on several simulated environments with varying topologies and numbers of pursuers.

Simultaneous localization and mapping (SLAM) algorithms allow a single robot to reduce the effects of drifting sensor biases while exploring unknown, GPS-denied environments. To reduce exploration time, a team of robots can build smaller maps in parallel and perform map fusion. Most map fusion techniques require a known relative transformation between coordinate frames. Other techniques rely on inter-robot detections to estimate an initial transformation. However, large environments with sparse robot coverage may necessitate alternative techniques when robots are in communication, but not, sensor range. In this paper, we address the map fusion problem with unknown relative transformations between robot pairs. We use the probabilistic hypothesis density (PHD) SLAM algorithm to track features within a static, simulated environment and propose two techniques for distributed map matching: a RANSAC based congruent triangle matching algorithm and an earth mover's distance (EMD) based assignment algorithm.

We present a novel path planning algorithm that, starting from a probabilistic roadmap, efficiently constructs a product graph used to search for a near optimal solution of a multiobjective optimization problem. The goal is to find paths that minimize a primary cost, such as the path length from start to goal, subject to a bound on a secondary cost such as the state estimation error covariance. The proposed algorithm is efficient as it relies on a scalar metric, related to the largest eigenvalue of the error covariance, and adaptively quantizes the secondary cost, yielding a product graph whose number of vertices and edges provides a good tradeoff between optimality and computational complexity. We further show how our approach can be extended to handle constraints on the probability of collision avoidance specified at every vertex along the path. Numerical examples show 1) how the computed paths change as a function of the specified bound on the secondary costs, and 2) the tradeoff between accuracy and computational efficiency of the proposed approach compared with methods where the product graph is built by quantizing the secondary cost uniformly.

This paper considers the problem of planning a path for an autonomous vehicle from a start to a goal location in presence of sensor intermittency modeled as a stochastic process, in addition to process and measurement noise. The aim is to plan a path that minimizes the localizational uncertainty for the vehicle upon arriving at the goal location. The main contribution of this paper is two-fold. We first show that it is possible to obtain an analytical bound on the performance of a state estimator under sensor misdetection (intermittency) occurring stochastically over time. We then use this bound in a sample-based path planning algorithm to produce a path that trades off accuracy and robustness. This extends the recent body of work on planning under uncertainty to include the fact that sensors may not provide any measurement owing to misdetection. This is caused either by adverse environmental conditions that prevent the sensors from making measurements or by the fundamental limitations of the sensors. Examples include RF-based ranging devices that intermittently do not receive the signal from beacons because of obstacles or the misdetection of features by a camera system in detrimental lighting conditions. Computational results demonstrate the benefit of the approach and comparisons are made with the state of the art in path planning in belief space.

We propose a hierarchical planning framework for mission planning and execution in uncertain and dynamic environments. We consider missions that involve motion planning in large, cluttered environments, trading off mission objectives while satisfying logical/spatial/temporal constraints. Our framework enables the decomposition of the planning problem across different layers, leveraging the difference in spatial and temporal scales of the mission objectives. We show that this framework facilitates contingency management under unanticipated events. Interaction between the various layers requires consistent model abstractions and common message semantics. To satisfy these requirements, we adopt a generic knowledge-based architecture that is independent from a specific application domain. We show a specific instance of our framework using a Constrained Markov Decision Process (CMDP) planner at the higher level and a Multi-Objective Probabilistic Roadmap (MO-PRM) planner at the lower level. The resulting planning system is tested in a realistic scenario where an agent is tasked with a mission in a large urban threat rich environment under dynamic uncertain conditions. The mission specification includes a Linear Temporal Logic (LTL) formula that defines the desired behaviors, a list of metrics to be optimized and a list of constraints on time, resources and probability of mission success.

In this paper, we consider a multi-phased, minimalistic approach to mobile robot localization that constrains the robot's ability to sense its environment to a binary detection of uniquely identifiable landmarks having unknown position (e.g., a WiFi transceiver detecting network SSIDs). Central to the proposed solution are dual landmark and observation complexes (instances of simplicial nerve complexes), which can be iteratively built through local observations without any metric or time-sequenced information. We have shown that these complexes approximate the topology of the underlying physical environment. Specifically, the notion of a “hole” (i.e., a topological invariant) within these complexes naturally represents a physical structure (e.g., a building) that limits landmark visibility/communication with respect to the robot's location. Taking advantage of this property, we formulate a homological sensing model that operates on these constructs enabling the robot to “count” the number of structures in its vicinity using local homology computations as a pseudo-metric surrogate sensor. Our homological sensor is highlighted in the context of a Monte-Carlo localization algorithm that resolves robot location by correlating the measured number of topological invariants with an unlabeled, metric map location.

A distributed estimation algorithm for sensor networks is proposed. A noisy time-varying signal is jointly tracked by a network of sensor nodes, in which each node computes its estimate as a weighted sum of its own and its neighbors' measurements and estimates. The weights are adaptively updated to minimize the variance of the estimation error. Both estimation and the parameter optimization is distributed; no central coordination of the nodes is required. An upper bound of the error variance in each node is derived. This bound decreases with the number of neighboring nodes. The estimation properties of the algorithm are illustrated via computer simulations, which are intended to compare our estimator performance with distributed schemes that were proposed previously in the literature. The results of the paper allow to trading-off communication constraints, computing efforts and estimation quality for a class of distributed filtering problems.

A new distributed estimation algorithm for tracking using a wireless sensor network is presented. We investigate how to track a time varying signal, noisily sensed by the nodes of the network. The algorithm is distributed, meaning that it does not require a central coordination among the nodes. Moreover, the proposed approach is scalable with respect to the network size, which means that its complexity does not grow with respect to the total number of nodes. The algorithm designed turns out to be composed by a cascade structure. Local constraints are determined to guarantee the global asymptotic stability of the estimation error. The algorithm can be applied e.g., for the position estimation, temporal synchronization, as well as tracking of signals. Performance is illustrated by simulations, where our filter is shown to behave better than other distributed schemes proposed in the literature.

The problem of estimating and tracking the motion of a moving target by a team of mobile robots is studied in this paper. Each robot is assumed to have a directional sensor with limited range, thus more than one robot (sensor) is needed for solving the problem. A sensor fusion scheme based on inter-robot communication is proposed in order to obtain accurate real-time information of the target's position and motion. Accordingly a hierarchical control scheme is applied, in which a consecutive set of desired formations is planned through a discrete model and low-level continuous-time controls are executed to track the resulting references. The algorithm is illustrated through simulations and on an experimental platform.

A control scheme is proposed for the backward line tracking problem of a truck with trailer. It combines two different regulators, one for backward motion and the other for forward, in a switching scheme that assures convergence to the desired line. The scheme has been implemented and successfully used to reverse a radio-controlled vehicle.

A control scheme is proposed for stabilization of backward driving along simple paths for a miniaturized vehicle composed of a truck and a two-axle trailer. The paths chosen are straight lines and arcs of circles. When reversing, the truck and trailer under examination can be modeled as an unstable nonlinear system with state and input saturations. The simplified goal of stabilizing along a trajectory (instead of a point) allows us to consider a system with controllable linearization. Still, the combination of instability and saturations makes the task impossible with a single controller. In fact, the system cannot be driven backward from all initial states because of the jack-knife effects between the parts of the multibody vehicle; it is sometimes necessary to drive forward to enter into a specific region of attraction. This leads to the use of hybrid controllers. The scheme has been implemented and successfully used to reverse the radio-controlled vehicle.

We discuss how to induce a set of collective emergent behaviors into a team of real robots used for soccer robotics. The activation of robot behaviors is organized according to a multi-level control architecture. The emergent cooperative abilities, like exchanging a ball, are achieved through the use of efficient collision avoidance algorithms implemented by a small set of robots able to frequently swap their roles. Our algorithms have been tested on a couple of real robots, Bart and Homer, which played the final game with the middle size league, at RoboCup'99, in Stockholm. This approach can be generalized to allow multi-robot systems to perform various kind of collective tasks in the entertainment field.