An official website of the United States government
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
A coding approach to localization using landmarks
Fully autonomous vehicles need the ability to localize without external help, for instance by using visual sensors together with a pre-loaded map of landmarks. In this paper we connect self-localization using landmarks with coding theory. This connection enables to translate Hamming distance properties to probabilistic localization guarantees given a certain number of errors in landmark identification; it also enables to leverage existing polynomial time decoding algorithms for localization. We present promising numerical evaluation results by simulating vehicle traveling paths along a road network generated from real data of a region in Washington D.C.
more »
« less
- Award ID(s):
- 1740047
- PAR ID:
- 10313180
- Date Published:
- Journal Name:
- GLOBECOM
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Many modern simultaneous localization and mapping (SLAM) techniques rely on sparse landmark-based maps due to their real-time performance. However, these techniques frequently assert that these landmarks are fixed in position over time, known as the static-world assumption. This is rarely, if ever, the case in most real-world environments. Even worse, over long deployments, robots are bound to observe traditionally static landmarks change, for example when an autonomous vehicle encounters a construction zone. This work addresses this challenge, accounting for changes in complex three-dimensional environments with the creation of a probabilistic filter that operates on the features that give rise to landmarks. To accomplish this, landmarks are clustered into cliques and a filter is developed to estimate their persistence jointly among observations of the landmarks in a clique. This filter uses estimated spatial-temporal priors of geometric objects, allowing for dynamic and semi-static objects to be removed from a formally static map. The proposed algorithm is validated in a 3D simulated environment.more » « less
-
Monitoring localization safety will be necessary to certify the performance of robots that operate in life-critical applications, such as autonomous passenger vehicles or delivery drones because many current localization safety methods do not account for the risk of undetected sensor faults. One type of fault, misassociation, occurs when a feature extracted from a mapped landmark is associated to a non-corresponding landmark and is a common source of error in feature-based navigation applications. This paper accounts for the probability of misassociation when quantifying landmark-based mobile robot localization safety for fixed-lag smoothing estimators. We derive a mobile robot localization safety bound and evaluate it using simulations and experimental data in an urban environment. Results show that localization safety suffers when landmark density is relatively low such that there are not enough landmarks to adequately localize and when landmark density is relatively high because of the high risk of feature misassociation.more » « less
-
Spatial navigation involves the use of various cues. This study examined how cue conflict influences navigation by contrasting landmarks and optic flow. Participants estimated spatial distances under different levels of cue conflict: minimal conflict, large conflict, and large conflict with explicit awareness of landmark instability. Whereas increased cue conflict alone had little behavioral impact, adding explicit awareness reduced reliance on landmarks and impaired the precision of spatial localization based on them. To understand the underlying mechanisms, we tested two cognitive models: a Bayesian causal inference (BCI) model and a non-Bayesian sensory disparity model. The BCI model provided a better fit to the data, revealing two independent mechanisms for reduced landmark reliance: increased sensory noise for unstable landmarks and lower weighting of unstable landmarks when landmarks and optic flow were judged to originate from different causes. Surprisingly, increased cue conflict did not decrease the prior belief in a common cause, even when explicit awareness of landmark instability was imposed. Additionally, cue weighting in the same-cause judgment was determined by bottom-up sensory reliability, while in the different-cause judgment, it correlated with participants’ subjective evaluation of cue quality, suggesting a top-down metacognitive influence. The BCI model further identified key factors contributing to suboptimal cue combination in minimal cue conflicts, including the prior belief in a common cause and prior knowledge of the target location. Together, these findings provide critical insights into how navigators resolve conflicting spatial cues and highlight the utility of the BCI model in dissecting cue interaction mechanisms in navigation.more » « less
-
Loop closure detection is a critical component of large-scale simultaneous localization and mapping (SLAM) in loopy environments. This capability is challenging to achieve in long-term SLAM, when the environment appearance exhibits significant long-term variations across various time of the day, months, and even seasons. In this paper, we introduce a novel formulation to learn an integrated long-term representation based upon both holistic and landmark information, which integrates two previous insights under a unified framework: (1) holistic representations outperform keypoint-based representations, and (2) landmarks as an intermediate representation provide informative cues to detect challenging locations. Our new approach learns the representation by projecting input visual data into a low-dimensional space, which preserves both the global consistency (to minimize representation error) and the local consistency (to preserve landmarks’ pairwise relationship) of the input data. To solve the formulated optimization problem, a new algorithm is developed with theoretically guaranteed convergence. Extensive experiments have been conducted using two large-scale public benchmark data sets, in which the promising performances have demonstrated the effectiveness of the proposed approach.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/GLOBECOM42002.2020.9347982
