skip to main content


Title: Inferring Obstacles and Path Validity from Visibility-Constrained Demonstrations
Many methods in learning from demonstration assume that the demonstrator has knowledge of the full environment. However, in many scenarios, a demonstrator only sees part of the environment and they continuously replan as they gather information. To plan new paths or to reconstruct the environment, we must consider the visibility constraints and replanning process of the demonstrator, which, to our knowledge, has not been done in previous work. We consider the problem of inferring obstacle configurations in a 2D environment from demonstrated paths for a point robot that is capable of seeing in any direction but not through obstacles. Given a set of survey points, which describe where the demonstrator obtains new information, and a candidate path, we con-struct a Constraint Satisfaction Problem (CSP) on a cell decomposition of the environment. We parameterize a set of obstacles corresponding to an assignment from the CSP and sample from the set to find valid environments. We show that there is a probabilistically-complete, yet not entirely tractable, algorithm that can guarantee novel paths in the space are unsafe or possibly safe. We also present an incomplete, but empirically-successful, heuristic-guided algorithm that we apply in our experiments to 1) planning novel paths and 2) recovering a probabilistic representation of the environment.  more » « less
Award ID(s):
1553873
NSF-PAR ID:
10211346
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
Workshop on Algorithmic Foundations of Robotics
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. In this paper, we adopt a new perspective on the Multi-Agent Path Finding (MAPF) problem and view it as a Constraint Satisfaction Problem (CSP). A variable corresponds to an agent, its domain is the set of all paths from the start vertex to the goal vertex of the agent, and the constraints allow only conflict-free paths for each pair of agents. Although the domains and constraints are only implicitly defined, this new CSP perspective allows us to use successful techniques from CSP search. With the concomitant idea of using matrix computations for calculating the size of the reduced domain of an uninstantiated variable, we apply Dynamic Variable Ordering and Rapid Random Restarts to the MAPF problem. In our experiments, the resulting simple polynomial-time MAPF solver, called Matrix MAPF solver, either outperforms or matches the performance of many state-of-the-art solvers for the MAPF problem and its variants. 
    more » « less
  2. We design a parallel algorithm for the Constrained Shortest Path (CSP) problem. The CSP problem is known to be NP-hard and there exists a pseudo-polynomial time sequential algorithm that solves it. To design the parallel algorithm, we extend the techniques used in the design of the Δ-stepping algorithm for the single-source shortest paths problem. 
    more » « less
  3. In this paper, we investigate the design of high throughput relay-assisted millimeter-wave (mmWave) backhaul networks in urban areas. Different from most related works, we consider the deployment of dedicated simple mmWave relay devices to help enhance the line-of-sight (LoS) connectivity of the backhaul network in urban areas with abundant obstacles. Given a set of (logical) backhaul links between base stations in the network, we propose an algorithm to find high-throughput LoS paths with relays for all logical links by minimizing interference within and between paths. We also propose methods to modify the backhaul topology to increase the probability of finding high-throughput paths using our algorithm. Extensive simulations, based on a 3-D model of a section of downtown Atlanta, demonstrate that high-throughput topologies, with minimal inter-path and intra-path interference, are feasible in most cases. The analyses also yield some insights on the mmWave backhaul network design problem. 
    more » « less
  4. "Monkey see monkey do" is an age-old adage, referring to naive imitation without a deep understanding of a system's underlying mechanics. Indeed, if a demonstrator has access to information unavailable to the imitator (monkey), such as a different set of sensors, then no matter how perfectly the imitator models its perceived environment (See), attempting to directly reproduce the demonstrator's behavior (Do) can lead to poor outcomes. Imitation learning in the presence of a mismatch between demonstrator and imitator has been studied in the literature under the rubric of causal imitation learning (Zhang et. al. 2020), but existing solutions are limited to single-stage decision-making. This paper investigates the problem of causal imitation learning in sequential settings, where the imitator must make multiple decisions per episode. We develop a graphical criterion that is both necessary and sufficient for determining the feasibility of causal imitation, providing conditions when an imitator can match a demonstrator's performance despite differing capabilities. Finally, we provide an efficient algorithm for determining imitability, and corroborate our theory with simulations. 
    more » « less
  5. In this paper, we propose a leader-follower hierarchical strategy for two robots collaboratively transporting an object in a partially known environment with obstacles. Both robots sense the local surrounding environment and react to obstacles in their proximity. We consider no explicit communication, so the local environment information and the control actions are not shared between the robots. At any given time step, the leader solves a model predictive control (MPC) problem with its known set of obstacles and plans a feasible trajectory to complete the task. The follower estimates the inputs of the leader and uses a policy to assist the leader while reacting to obstacles in its proximity. The leader infers obstacles in the follower’s vicinity by using the difference between the predicted and the real-time estimated follower control action. A method to switch the leader-follower roles is used to improve the control performance in tight environments. The efficacy of our approach is demonstrated with detailed comparisons to two alternative strategies, where it achieves the highest success rate, while completing the task fastest. 
    more » « less