skip to main content


Title: An Uncertainty-driven Sampling-based Online Coverage Path Planner for Seabed Mapping using Marine Robots
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
Award ID(s):
1945924
NSF-PAR ID:
10387713
Author(s) / Creator(s):
;
Date Published:
Journal Name:
2022 IEEE/OES Autonomous Underwater Vehicles Symposium (AUV)
Page Range / eLocation ID:
1 to 7
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We propose an approach to mapping tissue and vascular systems without the use of contrast agents, based on moving and measuring magnetic particles. To this end, we consider a swarm of particles in a 1D or 2D grid that can be tracked and controlled by an external agent. Control inputs are applied uniformly so that each particle experiences the same applied forces. We present algorithms for three tasks: (1) Mapping, i.e., building a representation of the free and obstacle regions of the workspace; (2) Subset Coverage, i.e., ensuring that at least one particle reaches each of a set of desired locations; and (3) Coverage, i.e., ensuring that every free region on the map is visited by at least one particle. These tasks relate to a large body of previous work from robot navigation, both from theory and practice, which is based on individual control. We provide theoretical insights that have potential relevance for fast MRI scans with magnetically controlled contrast media. In particular, we develop a fundamentally new approach for searching for an object at an unknown distance D, where the search is subject to two different and independent cost parameters for moving and for measuring. We show that regardless of the relative cost of these two operations, there is a simple O(log D/log log D)-competitive strategy, which is the best possible. Also, we provide practically useful and computationally efficient strategies for higher-dimensional settings. These algorithms extend to any number of particles and show that additional particles tend to reduce the mean and the standard deviation of the time required for each task. 
    more » « less
  2. Mapping a desired 2D pattern onto a curved surface has many applications. This includes motion planning for mobile robots to perform coverage path planing, robot end effector trajectory design for tasks such as printing, depositing, wielding on a 3D surface. This problem becomes more difficult if we want the mapped pattern to keep the properties of the original pattern (i.e, least possible mapping distortion), and pass over some desired points and/or remain bounded in a specific region on the surface. In this paper, we apply surface parameterization and mapping distortion analysis, which is rarely used in robot motion planning works, to map a pattern onto 3D surface. To meet additional goals such as passing over certain points, a planar mapping determined by constrained optimization is employed on the original pattern. Our focus is on printing/depositing materials on curved surfaces, and simulations and experiments are provided to confirm the performance of the approach. 
    more » « less
  3. null (Ed.)
    Abstract A novel, exact algorithm is presented to solve the path planning problem that involves finding the shortest collision-free path from a start to a goal point in a two-dimensional environment containing convex and non-convex obstacles. The proposed algorithm, which is called the shortest possible path (SPP) algorithm, constructs a network of lines connecting the vertices of the obstacles and the locations of the start and goal points which is smaller than the network generated by the visibility graph. Then it finds the shortest path from start to goal point within this network. The SPP algorithm generates a safe, smooth and obstacle-free path that has a desired distance from each obstacle. This algorithm is designed for environments that are populated sparsely with convex and nonconvex polygonal obstacles. It has the capability of eliminating some of the polygons that do not play any role in constructing the optimal path. It is proven that the SPP algorithm can find the optimal path in O(nn r2 ) time, where n is the number of vertices of all polygons and n ̓ is the number of vertices that are considered in constructing the path network (n ̓ ≤ n). The performance of the algorithm is evaluated relative to three major classes of algorithms: heuristic, probabilistic, and classic. Different benchmark scenarios are used to evaluate the performance of the algorithm relative to the first two classes of algorithms: GAMOPP (genetic algorithm for multi-objective path planning), a representative heuristic algorithm, as well as RRT (rapidly-exploring random tree) and PRM (probabilistic road map), two well-known probabilistic algorithms. Time complexity is known for classic algorithms, so the presented algorithm is compared analytically. 
    more » « less
  4. We propose a predictive runtime monitoring framework that forecasts the distribution of future positions of mobile robots in order to detect and avoid impending property violations such as collisions with obstacles or other agents. Our approach uses a restricted class of temporal logic formulas to represent the likely intentions of the agents along with a combination of temporal logic-based optimal cost path planning and Bayesian inference to compute the probability of these intents given the current trajectory of the robot. First, we construct a large but finite hypothesis space of possible intents represented as temporal logic formulas whose atomic propositions are derived from a detailed map of the robot’s workspace. Next, our approach uses real-time observations of the robot’s position to update a distribution over temporal logic formulae that represent its likely intent. This is performed by using a combination of optimal cost path planning and a Boltzmann noisy rationality model. In this manner, we construct a Bayesian approach to evaluating the posterior probability of various hypotheses given the observed states and actions of the robot. Finally, we predict the future position of the robot by drawing posterior predictive samples using a Monte-Carlo method. We evaluate our framework using two different trajectory datasets that contain multiple scenarios implementing various tasks. The results show that our method can predict future positions precisely and efficiently, so that the computation time for generating a prediction is a tiny fraction of the overall time horizon. 
    more » « less
  5. Abstract

    In this paper, we address the problem of autonomous multi-robot mapping, exploration and navigation in unknown, GPS-denied indoor or urban environments using a team of robots equipped with directional sensors with limited sensing capabilities and limited computational resources. The robots have no a priori knowledge of the environment and need to rapidly explore and construct a map in a distributed manner using existing landmarks, the presence of which can be detected using onboard senors, although little to no metric information (distance or bearing to the landmarks) is available. In order to correctly and effectively achieve this, the presence of a necessary density/distribution of landmarks is ensured by design of the urban/indoor environment. We thus address this problem in two phases: (1) During the design/construction of the urban/indoor environment we can ensure that sufficient landmarks are placed within the environment. To that end we develop afiltration-based approach for designing strategic placement of landmarks in an environment. (2) We develop a distributed algorithm which a team of robots, with no a priori knowledge of the environment, can use to explore such an environment, construct a topological map requiring no metric/distance information, and use that map to navigate within the environment. This is achieved using a topological representation of the environment (called aLandmark Complex), instead of constructing a complete metric/pixel map. The representation is built by the robot as well as used by them for navigation through a balanced strategy involving exploration and exploitation. We use tools from homology theory for identifying “holes” in the coverage/exploration of the unknown environment and hence guide the robots towards achieving a complete exploration and mapping of the environment. Our simulation results demonstrate the effectiveness of the proposed metric-free topological (simplicial complex) representation in achieving exploration, localization and navigation within the environment.

     
    more » « less