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
Autonomous Urban Localization and Navigation with Limited Information
Urban environments offer a challenging scenario for autonomous driving. Globally localizing information, such as a GPS signal, can be unreliable due to signal shadowing and multipath errors. Detailed a priori maps of the environment with sufficient information for autonomous navigation typically require driving the area multiple times to collect large amounts of data, substantial post-processing on that data to obtain the map, and then maintaining updates on the map as the environment changes. This paper addresses the issue of autonomous driving in an urban environment by investigating algorithms and an architecture to enable fully functional autonomous driving with limited information. An algorithm to autonomously navigate urban roadways with little to no reliance on an a priori map or GPS is developed. Localization is performed with an extended Kalman filter with odometry, compass, and sparse landmark measure ment updates. Navigation is accomplished by a compass-based navigation control law. Key results from Monte Carlo studies show success rates of urban navigation under different environmental conditions. Experiments validate the simulated results and demonstrate that, for given test conditions, an expected range can be found for a given success rate.
more »
« less
- Award ID(s):
- 1724282
- PAR ID:
- 10079289
- Date Published:
- Journal Name:
- 2018 IEEE Intelligent Vehicles Symposium (IV)
- Page Range / eLocation ID:
- 806 to 813
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This research project aims to achieve a future urban environment where people and self-driving cars coexist together while guaranteeing safety. To modify the environment, our first approach is to understand the limitations of GPS/GNSS positioning in an urban area where signal blockages and reflections make positioning difficult. For the evaluation process, we assume reasonable integrity requirements and calculate navigation availability along a sample Chicago urban corridor (State Street). We reject all non-line-of-sight (NLOS) that are blocked and reflected using a 3-D map. The availability of GPS-only positioning is determined to be less than 10% at most locations. Using four full GNSS constellations, availability improves significantly but is still lower than 80 % at certain points. The results establish the need for integration with other navigation sensors, such as inertial navigation systems (INS) and Lidar, to ensure integrity. The analysis methods introduced will form the basis to determine performance requirements for these additional sensors.more » « less
-
Low-cost and easily obtained Global Navigation Satellite System (e.g., GPS) receivers are broadly embedded into various devices for providing location information. In this work, we develop a secret key establishment by utilizing the driving data obtained from GPS. Those data may exhibit randomness as the driver may alternatively step on the accelerator and brake pedals from time to time with varying force in order to adapt to the road traffic during driving. A driving vehicle provides a physically secure boundary as the devices co-located within the vehicle can observe common GPS data, as opposed to devices that do not experience the trip. We implement this key establishment in a real-world environment on top of off-the-shelf GPS-equipped devices as well as widely deployed GPS modules each connected with Raspberry Pi. Extensive experimental results show that when a user drives around 1.36 km for 1.32 minutes on average under moderate traffic conditions, two legitimate GPS-equipped devices in the vehicle can successfully establish a 128-bit secret key. Meanwhile, an attacker following the target vehicle is unable to establish a secret key with the legitimate devices.more » « less
-
Accurate and up-to-date digital road maps are the foundation of many mobile applications, such as navigation and autonomous driving. A manually-created map suffers from the high cost for creation and maintenance due to constant road network updating. Recently, the ubiquity of GPS devices in vehicular systems has led to an unprecedented amount of vehicle sensing data for map inference. Unfortunately, accurate map inference based on vehicle GPS is challenging for two reasons. First, it is challenging to infer complete road structures due to the sensing deviation, sparse coverage, and low sampling rate of GPS of a fleet of vehicles with similar mobility patterns, e.g., taxis. Second, a road map requires various road properties such as road categories, which is challenging to be inferred by just GPS locations of vehicles. In this paper, we design a map inference system called coMap by considering multiple fleets of vehicles with Complementary Mobility Features. coMap has two key components: a graph-based map sketching component, a learning-based map painting component. We implement coMap with the data from four type-aware vehicular sensing systems in one city, which consists of 18 thousand taxis, 10 thousand private vehicles, 6 thousand trucks, and 14 thousand buses. We conduct a comprehensive evaluation of coMap with two state-of-the-art baselines along with ground truth based on OpenStreetMap and a commercial map provider, i.e., Baidu Maps. The results show that (i) for the map sketching, our work improves the performance by 15.9%; (ii) for the map painting, our work achieves 74.58% of average accuracy on road category classification.more » « less
-
In addition to the multiple sensors to measure parameters that can be used to improve both safety and efficiency, modern vehicles also gather information about external data (e.g., traffic conditions, weather) which, if properly used, could further improve the overall trip experience. Specifically, when it comes to navigation, one source that can provide increased context awareness, especially for autonomous driving, are the High Definition (HD) maps, which have recently witnessed a tremendous growth of popularity in vehicular technology and use. As they are limited to a particular geographic area, different portions need to be downloaded (and processed) on multiple occasions throughout a given trip, along with the other data from other internal and external sources. In this paper, we provide an effective deep learning approach for the recently introduced problem of Predicting Map Data Consumption (PMDC) in the future time instants for a given trip. We propose a novel methodology that integrates multiple data sources (road network, traffic, historic trips, HD maps) and, for a given trip, enables prediction of the map data consumption. Our experimental observations demonstrate the benefits of the proposed approach over the candidate baselines.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/IVS.2018.8500693
