skip to main content

Explore Research Products in the NSF-PAR

Title: Guaranteed Coverage with a Blind Unreliable Robot
We consider the problem of coverage planning for a particular type of very simple mobile robot. The robot must be able to translate in a commanded direction (specified in a global reference frame), with bounded error on the motion direction, until reaching the environment boundary. The objective, for a given environment map, is to generate a sequence of motions that is guaranteed to cover as large a portion of that environment as possible, in spite of the severe limits on the robot's sensing and actuation abilities. We show how to model the knowledge available to this kind of robot about its own position within the environment, show how to compute the region whose coverage can be guaranteed for a given plan, and characterize regions whose coverage cannot be guaranteed by any plan. We also describe a heuristic algorithm that generates coverage plans for this robot, based on a search across a specially-constructed graph. Simulation results demonstrate the effectiveness of the approach.  more » « less
Award ID(s):
1659514
NSF-PAR ID:
10085810
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
Page Range / eLocation ID:
7383 to 7390
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ( , Workshop on Algorithmic Foundations of Robotics)
    null (Ed.)
    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
  2. ; ; ; ; ( , IEEE International Conference on Robotics and Automation)
    null (Ed.)
    In order to solve complex, long-horizon tasks, intelligent robots need to carry out high-level, abstract planning and reasoning in conjunction with motion planning. However, abstract models are typically lossy and plans or policies computed using them can be unexecutable. These problems are exacerbated in stochastic situations where the robot needs to reason about, and plan for multiple contingencies. We present a new approach for integrated task and motion planning in stochastic settings. In contrast to prior work in this direction, we show that our approach can effectively compute integrated task and motion policies whose branching structures encoding agent behaviors handling multiple execution-time contingencies. We prove that our algorithm is probabilistically complete and can compute feasible solution policies in an anytime fashion so that the probability of encountering an unresolved contingency decreases over time. Empirical results on a set of challenging problems show the utility and scope of our methods. 
    more » « less
  3. ; ( , 2022 IEEE/OES Autonomous Underwater Vehicles Symposium (AUV))
    Seabed mapping is a common application for marine robots, and it is often framed as a coverage path planning problem in robotics. During a robot-based survey, the coverage of perceptual sensors (e.g., cameras, LIDARS and sonars) changes, especially in underwater environments. Therefore, online path planning is needed to accommodate the sensing changes in order to achieve the desired coverage ratio. In this paper, we present a sensing confidence model and a uncertainty-driven sampling-based online coverage path planner (SO-CPP) to assist in-situ robot planning for seabed mapping and other survey-type applications. Different from conventional lawnmower pattern, the SO-CPP will pick random points based on a probability map that is updated based on in-situ sonar measurements using a sensing confidence model. The SO-CPP then constructs a graph by connecting adjacent nodes with edge costs determined using a multi-variable cost function. Finally, the SO-CPP will select the best route and generate the desired waypoint list using a multi-variable objective function. The SO-CPP has been evaluated in a simulation environment with an actual bathymetric map, a 6-DOF AUV dynamic model and a ray-tracing sonar model. We have performed Monte Carlo simulations with a variety of environmental settings to validate that the SO-CPP is applicable to a convex workspace, a non-convex workspace, and unknown occupied workspace. So-CPP is found outperform regular lawnmower pattern survey by reducing the resulting traveling distance by upto 20%. Besides that, we observed that the prior knowledge about the obstacles in the environment has minor effects on the overall traveling distance. In the paper, limitation and real-world implementation are also discussed along with our plan in the future. 
    more » « less
  4. ; ( , International Journal of Computational Geometry & Applications)
    null (Ed.)
    We propose an Euler transformation that transforms a given [Formula: see text]-dimensional cell complex [Formula: see text] for [Formula: see text] into a new [Formula: see text]-complex [Formula: see text] in which every vertex is part of the same even number of edges. Hence every vertex in the graph [Formula: see text] that is the [Formula: see text]-skeleton of [Formula: see text] has an even degree, which makes [Formula: see text] Eulerian, i.e., it is guaranteed to contain an Eulerian tour. Meshes whose edges admit Eulerian tours are crucial in coverage problems arising in several applications including 3D printing and robotics. For [Formula: see text]-complexes in [Formula: see text] ([Formula: see text]) under mild assumptions (that no two adjacent edges of a [Formula: see text]-cell in [Formula: see text] are boundary edges), we show that the Euler transformed [Formula: see text]-complex [Formula: see text] has a geometric realization in [Formula: see text], and that each vertex in its [Formula: see text]-skeleton has degree [Formula: see text]. We bound the numbers of vertices, edges, and [Formula: see text]-cells in [Formula: see text] as small scalar multiples of the corresponding numbers in [Formula: see text]. We prove corresponding results for [Formula: see text]-complexes in [Formula: see text] under an additional assumption that the degree of a vertex in each [Formula: see text]-cell containing it is [Formula: see text]. In this setting, every vertex in [Formula: see text] is shown to have a degree of [Formula: see text]. We also present bounds on parameters measuring geometric quality (aspect ratios, minimum edge length, and maximum angle of cells) of [Formula: see text] in terms of the corresponding parameters of [Formula: see text] for [Formula: see text]. Finally, we illustrate a direct application of the proposed Euler transformation in additive manufacturing. 
    more » « less
  5. ; ; ; ; ; ( , Symposium on Combinatorial Search (SoCS))
    The 2D Multi-Agent Path Finding (MAPF) problem aims at finding collision-free paths for a number of agents, from a set of start locations to a set of goal locations in a known 2D environment. MAPF has been studied in theoretical computer science, robotics, and artificial intelligence over several decades, due to its importance for robot navigation. It is currently experiencing significant scientific progress due to its relevance for automated warehouses (such as those operated by Amazon) and other important application areas. In this paper, we demonstrate that some recently developed MAPF algorithms apply more broadly than currently believed in the MAPF research community. In particular, we describe the 3D Pipe Routing (PR) problem, which aims at placing collision-free pipes from given start locations to given goal locations in a known 3D environment. The MAPF and PR problems are similar: a solution to a MAPF instance is a set of blocked cells in x-y-t space, while a solution to the corresponding PR instance is a set of blocked cells in x-y-z space. We show how to use this similarity to apply several recently developed MAPF algorithms to the PR problem, and discuss their performance on real-world PR instances. This opens up a new direction of industrial relevance for the MAPF research community. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email