The Experts below are selected from a list of 6522 Experts worldwide ranked by ideXlab platform
Larry H. Matthies - One of the best experts on this subject based on the ideXlab platform.
-
gamma slam visual slam in unstructured environments using variance Grid Maps
Journal of Field Robotics, 2009Co-Authors: Tim K. Marks, Max Bajracharya, Garrison W. Cottrell, Andrew W Howard, Larry H. MatthiesAbstract:This paper describes an online stereo visual simultaneous localization and mapping (SLAM) algorithm developed for the Learning Applied to Ground Robotics (LAGR) program. The Gamma-SLAM algorithm uses a Rao–Blackwellized particle filter to obtain a joint posterior over poses and Maps: the pose distribution is estimated using a particle filter, and each particle has its own map that is obtained through exact filtering conditioned on the particle's pose. Visual odometry is used to provide good proposal distributions for the particle filter, and Maps are represented using a Cartesian Grid. Unlike previous Grid-based SLAM algorithms, however, the Gamma-SLAM map maintains a posterior distribution over the elevation variance in each cell. This variance Grid map can capture rocks, vegetation, and other objects that are typically found in unstructured environments but are not well modeled by traditional occupancy or elevation Grid Maps. The algorithm runs in real time on conventional processors and has been evaluated for both qualitative and quantitative accuracy in three outdoor environments over trajectories totaling 1,600 m in length. © 2008 Wiley Periodicals, Inc.
-
gamma slam using stereo vision and variance Grid Maps for slam in unstructured environments
International Conference on Robotics and Automation, 2008Co-Authors: Tim K. Marks, Max Bajracharya, Andrew Howard, Garrison W. Cottrell, Larry H. MatthiesAbstract:We introduce a new method for stereo visual SLAM (simultaneous localization and mapping) that works in unstructured, outdoor environments. Unlike other Grid-based SLAM algorithms, which use occupancy Grid Maps, our algorithm uses a new mapping technique that maintains a posterior distribution over the height variance in each cell. This idea was motivated by our experience with outdoor navigation tasks, which has shown height variance to be a useful measure of traversability. To obtain a joint posterior over poses and Maps, we use a Rao-Blackwellized particle filter: the pose distribution is estimated using a particle filter, and each particle has its own map that is obtained through exact filtering conditioned on the particle's pose. Visual odometry provides good proposal distributions for the particle pose. In the analytical (exact) filter for the map, we update the sufficient statistics of a gamma distribution over the precision (inverse variance) of heights in each Grid cell. We verify the algorithm's accuracy on two outdoor courses by comparing with ground truth data obtained using electronic surveying equipment. In addition, we solve for the optimal transformation from the SLAM map to georeferenced coordinates, based on a noisy GPS signal. We derive an online version of this alignment process, which can be used to maintain a running estimate of the robot's global position that is much more accurate than the GPS readings.
-
Gamma-SLAM: Stereo visual SLAM in unstructured environments using variance Grid Maps
IROS visual SLAM workshop, 2007Co-Authors: Tim K. Marks, Max Bajracharya, Andrew Howard, Garrison W. Cottrell, Larry H. MatthiesAbstract:We introduce a new method for stereo visual SLAM (simultaneous localization and mapping) that works in unstructured, outdoor environments. Observations use dense stereo vision to measure the variance of the heights in each cell of a 2D Grid. Unlike other Grid-based SLAM algorithms, which use occupancy Grid Maps, our algorithm uses a new mapping technique that maintains a posterior distribution over the height variance in each cell. To obtain a joint posterior over poses and Maps, we use a Rao-Blackwellized particle filter: the pose distribution is estimated using a particle filter, and each particle has its own map that is obtained through exact filtering conditioned on the particle? pose. For the particle filter over pose, visual odometry (VO) provides good proposal distributions. In the analytical (exact) filter for the map, we update the sufficient statistics of a gamma distribution over the precision (inverse variance) of heights in each Grid cell. We demonstrate performance on two outdoor courses, and verify the accuracy of the algorithm by comparing with ground truth data obtained using electronic surveying equipment.
Adi Botea - One of the best experts on this subject based on the ideXlab platform.
-
Symmetry-Based Search Space Reduction For Grid Maps
arXiv: Artificial Intelligence, 2011Co-Authors: Daniel Harabor, Adi Botea, Philip KilbyAbstract:In this paper we explore a symmetry-based search space reduction technique which can speed up optimal pathfinding on undirected uniform-cost Grid Maps by up to 38 times. Our technique decomposes Grid Maps into a set of empty rectangles, removing from each rectangle all interior nodes and possibly some from along the perimeter. We then add a series of macro-edges between selected pairs of remaining perimeter nodes to facilitate provably optimal traversal through each rectangle. We also develop a novel online pruning technique to further speed up search. Our algorithm is fast, memory efficient and retains the same optimality and completeness guarantees as searching on an unmodified Grid map.
-
breaking path symmetries on 4 connected Grid Maps
National Conference on Artificial Intelligence, 2010Co-Authors: Daniel Harabor, Adi BoteaAbstract:Pathfinding systems that operate on regular Grids are common in the AI literature and often used in real-time video games. Typical speed-up enhancements include reducing the size of the search space using abstraction, and building more informed heuristics. Though effective each of these strategies has shortcomings. For example, pathfinding with abstraction usually involves trading away optimality for speed. Meanwhile, improving on the accuracy of the well known Manhattan heuristic usually requires significant extra memory. We present a different kind of speedup technique based on the idea of identifying and eliminating symmetric path segments in 4-connected Grid Maps (which allow straight but not diagonal movement). Our method identifies rectangular rooms with no obstacles and prunes all interior nodes, leaving only a boundary perimeter. This process eliminates many symmetric path segments and results in Grid Maps which are often much smaller and consequently much faster to search than the original. We evaluate our technique on a range of different Grid Maps including a well known set from the popular video game Baldur's Gate II. On our test data, A* can run up to 3.5 times faster on average. We achieve this without using any significant extra memory or sacrificing solution optimality.
-
AIIDE - Breaking path symmetries on 4-connected Grid Maps
2010Co-Authors: Daniel Harabor, Adi BoteaAbstract:Pathfinding systems that operate on regular Grids are common in the AI literature and often used in real-time video games. Typical speed-up enhancements include reducing the size of the search space using abstraction, and building more informed heuristics. Though effective each of these strategies has shortcomings. For example, pathfinding with abstraction usually involves trading away optimality for speed. Meanwhile, improving on the accuracy of the well known Manhattan heuristic usually requires significant extra memory. We present a different kind of speedup technique based on the idea of identifying and eliminating symmetric path segments in 4-connected Grid Maps (which allow straight but not diagonal movement). Our method identifies rectangular rooms with no obstacles and prunes all interior nodes, leaving only a boundary perimeter. This process eliminates many symmetric path segments and results in Grid Maps which are often much smaller and consequently much faster to search than the original. We evaluate our technique on a range of different Grid Maps including a well known set from the popular video game Baldur's Gate II. On our test data, A* can run up to 3.5 times faster on average. We achieve this without using any significant extra memory or sacrificing solution optimality.
-
scalable multi agent pathfinding on Grid Maps with tractability and completeness guarantees
European Conference on Artificial Intelligence, 2010Co-Authors: Kohsin Cindy Wang, Adi BoteaAbstract:Navigating multiple mobile units on Grid Maps is an NP-complete problem [4, 1] with many real-life applications. Centralized search in the combined state space of all units scales very poorly. Previous approaches that decompose the initial problem into a series of smaller searches, such as FAR [5] and WHCA* [2], can significantly improve scalability and speed. However, such methods are incomplete. They provide no guarantees with respect to the total running time, and are unable to apriori tell whether they would succeed in finding a solution to a given instance. More recent algorithms, such as MAPP [6] and BIBOX [3], are complete on well-specified subclasses of problems. They also provide low-polynomial upper bounds for the running time, the solution length and the memory requirements. However, their empirical speed and scalability, compared to incomplete methods, has been an open question. In this paper we take steps towards bridging the gap between the two categories of algorithms, combining strengths specific to each of them. We extended MAPP to improve its completeness range, solution quality, and total runtime, addressing main bottlenecks of the original algorithm. We performed the first empirical analysis of MAPP, showing that the enhanced MAPP has better success ratio and scalability than state-of-the-art incomplete algorithms, and is competitive in running times, with at most 92% longer solutions, while maintaining the theoretical properties of the original MAPP.
-
tractable multi agent path planning on Grid Maps
International Joint Conference on Artificial Intelligence, 2009Co-Authors: Kohsin Cindy Wang, Adi BoteaAbstract:Multi-agent path planning on Grid Maps is a challenging problem and has numerous real-life applications. Running a centralized, systematic search such as A* is complete and cost-optimal but scales up poorly in practice, since both the search space and the branching factor grow exponentially in the number of mobile units. Decentralized approaches, which decompose a problem into several subproblems, can be faster and can work for larger problems. However, existing decentralized methods offer no guarantees with respect to completeness, running time, and solution quality. To address such limitations, we introduce MAPP, a tractable algorithm for multi-agent path planning on Grid Maps. We show that MAPP has low-polynomial worst-case upper bounds for the running time, the memory requirements, and the length of solutions. As it runs in low-polynomial time, MAPP is incomplete in the general case. We identify a class of problems for which our algorithm is complete. We believe that this is the first study that formalises restrictions to obtain a tractable class of multi-agent path planning problems.
Tim K. Marks - One of the best experts on this subject based on the ideXlab platform.
-
gamma slam visual slam in unstructured environments using variance Grid Maps
Journal of Field Robotics, 2009Co-Authors: Tim K. Marks, Max Bajracharya, Garrison W. Cottrell, Andrew W Howard, Larry H. MatthiesAbstract:This paper describes an online stereo visual simultaneous localization and mapping (SLAM) algorithm developed for the Learning Applied to Ground Robotics (LAGR) program. The Gamma-SLAM algorithm uses a Rao–Blackwellized particle filter to obtain a joint posterior over poses and Maps: the pose distribution is estimated using a particle filter, and each particle has its own map that is obtained through exact filtering conditioned on the particle's pose. Visual odometry is used to provide good proposal distributions for the particle filter, and Maps are represented using a Cartesian Grid. Unlike previous Grid-based SLAM algorithms, however, the Gamma-SLAM map maintains a posterior distribution over the elevation variance in each cell. This variance Grid map can capture rocks, vegetation, and other objects that are typically found in unstructured environments but are not well modeled by traditional occupancy or elevation Grid Maps. The algorithm runs in real time on conventional processors and has been evaluated for both qualitative and quantitative accuracy in three outdoor environments over trajectories totaling 1,600 m in length. © 2008 Wiley Periodicals, Inc.
-
gamma slam using stereo vision and variance Grid Maps for slam in unstructured environments
International Conference on Robotics and Automation, 2008Co-Authors: Tim K. Marks, Max Bajracharya, Andrew Howard, Garrison W. Cottrell, Larry H. MatthiesAbstract:We introduce a new method for stereo visual SLAM (simultaneous localization and mapping) that works in unstructured, outdoor environments. Unlike other Grid-based SLAM algorithms, which use occupancy Grid Maps, our algorithm uses a new mapping technique that maintains a posterior distribution over the height variance in each cell. This idea was motivated by our experience with outdoor navigation tasks, which has shown height variance to be a useful measure of traversability. To obtain a joint posterior over poses and Maps, we use a Rao-Blackwellized particle filter: the pose distribution is estimated using a particle filter, and each particle has its own map that is obtained through exact filtering conditioned on the particle's pose. Visual odometry provides good proposal distributions for the particle pose. In the analytical (exact) filter for the map, we update the sufficient statistics of a gamma distribution over the precision (inverse variance) of heights in each Grid cell. We verify the algorithm's accuracy on two outdoor courses by comparing with ground truth data obtained using electronic surveying equipment. In addition, we solve for the optimal transformation from the SLAM map to georeferenced coordinates, based on a noisy GPS signal. We derive an online version of this alignment process, which can be used to maintain a running estimate of the robot's global position that is much more accurate than the GPS readings.
-
Gamma-SLAM: Stereo visual SLAM in unstructured environments using variance Grid Maps
IROS visual SLAM workshop, 2007Co-Authors: Tim K. Marks, Max Bajracharya, Andrew Howard, Garrison W. Cottrell, Larry H. MatthiesAbstract:We introduce a new method for stereo visual SLAM (simultaneous localization and mapping) that works in unstructured, outdoor environments. Observations use dense stereo vision to measure the variance of the heights in each cell of a 2D Grid. Unlike other Grid-based SLAM algorithms, which use occupancy Grid Maps, our algorithm uses a new mapping technique that maintains a posterior distribution over the height variance in each cell. To obtain a joint posterior over poses and Maps, we use a Rao-Blackwellized particle filter: the pose distribution is estimated using a particle filter, and each particle has its own map that is obtained through exact filtering conditioned on the particle? pose. For the particle filter over pose, visual odometry (VO) provides good proposal distributions. In the analytical (exact) filter for the map, we update the sufficient statistics of a gamma distribution over the precision (inverse variance) of heights in each Grid cell. We demonstrate performance on two outdoor courses, and verify the accuracy of the algorithm by comparing with ground truth data obtained using electronic surveying equipment.
Kohsin Cindy Wang - One of the best experts on this subject based on the ideXlab platform.
-
scalable multi agent pathfinding on Grid Maps with tractability and completeness guarantees
European Conference on Artificial Intelligence, 2010Co-Authors: Kohsin Cindy Wang, Adi BoteaAbstract:Navigating multiple mobile units on Grid Maps is an NP-complete problem [4, 1] with many real-life applications. Centralized search in the combined state space of all units scales very poorly. Previous approaches that decompose the initial problem into a series of smaller searches, such as FAR [5] and WHCA* [2], can significantly improve scalability and speed. However, such methods are incomplete. They provide no guarantees with respect to the total running time, and are unable to apriori tell whether they would succeed in finding a solution to a given instance. More recent algorithms, such as MAPP [6] and BIBOX [3], are complete on well-specified subclasses of problems. They also provide low-polynomial upper bounds for the running time, the solution length and the memory requirements. However, their empirical speed and scalability, compared to incomplete methods, has been an open question. In this paper we take steps towards bridging the gap between the two categories of algorithms, combining strengths specific to each of them. We extended MAPP to improve its completeness range, solution quality, and total runtime, addressing main bottlenecks of the original algorithm. We performed the first empirical analysis of MAPP, showing that the enhanced MAPP has better success ratio and scalability than state-of-the-art incomplete algorithms, and is competitive in running times, with at most 92% longer solutions, while maintaining the theoretical properties of the original MAPP.
-
tractable multi agent path planning on Grid Maps
International Joint Conference on Artificial Intelligence, 2009Co-Authors: Kohsin Cindy Wang, Adi BoteaAbstract:Multi-agent path planning on Grid Maps is a challenging problem and has numerous real-life applications. Running a centralized, systematic search such as A* is complete and cost-optimal but scales up poorly in practice, since both the search space and the branching factor grow exponentially in the number of mobile units. Decentralized approaches, which decompose a problem into several subproblems, can be faster and can work for larger problems. However, existing decentralized methods offer no guarantees with respect to completeness, running time, and solution quality. To address such limitations, we introduce MAPP, a tractable algorithm for multi-agent path planning on Grid Maps. We show that MAPP has low-polynomial worst-case upper bounds for the running time, the memory requirements, and the length of solutions. As it runs in low-polynomial time, MAPP is incomplete in the general case. We identify a class of problems for which our algorithm is complete. We believe that this is the first study that formalises restrictions to obtain a tractable class of multi-agent path planning problems.
-
IJCAI - Tractable multi-agent path planning on Grid Maps
2009Co-Authors: Kohsin Cindy Wang, Adi BoteaAbstract:Multi-agent path planning on Grid Maps is a challenging problem and has numerous real-life applications. Running a centralized, systematic search such as A* is complete and cost-optimal but scales up poorly in practice, since both the search space and the branching factor grow exponentially in the number of mobile units. Decentralized approaches, which decompose a problem into several subproblems, can be faster and can work for larger problems. However, existing decentralized methods offer no guarantees with respect to completeness, running time, and solution quality. To address such limitations, we introduce MAPP, a tractable algorithm for multi-agent path planning on Grid Maps. We show that MAPP has low-polynomial worst-case upper bounds for the running time, the memory requirements, and the length of solutions. As it runs in low-polynomial time, MAPP is incomplete in the general case. We identify a class of problems for which our algorithm is complete. We believe that this is the first study that formalises restrictions to obtain a tractable class of multi-agent path planning problems.
Klaus Dietmayer - One of the best experts on this subject based on the ideXlab platform.
-
Motion Estimation in Occupancy Grid Maps in Stationary Settings Using Recurrent Neural Networks.
arXiv: Robotics, 2019Co-Authors: Marcel Schreiber, Vasileios Belagiannis, Claudius Gläser, Klaus DietmayerAbstract:In this work, we tackle the problem of modeling the vehicle environment as dynamic occupancy Grid map in complex urban scenarios using recurrent neural networks. Dynamic occupancy Grid Maps represent the scene in a bird's eye view, where each Grid cell contains the occupancy probability and the two dimensional velocity. As input data, our approach relies on measurement Grid Maps, which contain occupancy probabilities, generated with lidar measurements. Given this configuration, we propose a recurrent neural network architecture to predict a dynamic occupancy Grid map, i.e. filtered occupancy and velocity of each cell, by using a sequence of measurement Grid Maps. Our network architecture contains convolutional long-short term memories in order to sequentially process the input, makes use of spatial context, and captures motion. In the evaluation, we quantify improvements in estimating the velocity of braking and turning vehicles compared to the state-of-the-art. Additionally, we demonstrate that our approach provides more consistent velocity estimates for dynamic objects, as well as, less erroneous velocity estimates in static area.
-
environment perception framework fusing multi object tracking dynamic occupancy Grid Maps and digital Maps
International Conference on Intelligent Transportation Systems, 2018Co-Authors: Fabian Gies, Andreas Danzer, Klaus DietmayerAbstract:Autonomously driving vehicles require a complete and robust perception of the local environment. A main challenge is to perceive any other road users, where multi-object tracking or occupancy Grid Maps are commonly used. The presented approach combines both methods to compensate false positives and receive a complementary environment perception. Therefore, an environment perception framework is introduced that defines a common representation, extracts objects from a dynamic occupancy Grid map and fuses them with tracks of a Labeled Multi-Bernoulli filter. Finally, a confidence value is developed, that validates object estimates using different constraints regarding physical possibilities, method specific characteristics and contextual information from a digital map. Experimental results with real world data highlight the robustness and significance of the presented fusing approach, utilizing the confidence value in rural and urban scenarios.
-
modeling occluded areas in dynamic Grid Maps
International Conference on Information Fusion, 2017Co-Authors: Nils Rexin, Dominik Nuss, Stephan Reuter, Klaus DietmayerAbstract:The dynamic Grid map illustrates the environment of robots with moving and static obstacles. Nuss et al. describe in [1] an implementation of this Grid map, in which the state of the Grid cells is to be modeled as a random finite set (RFS) based on a stochastic measurement system. For a real-time implementation this approach was approximated with Dempster-Shafer (DS). For this Nuss et al. design the areas without information (unknown areas) so, that no probabilistic calculations are executed. Only in the field of view, hypotheses represent the dynamic behavior of objects. This hypotheses are generated with particles. Therefore, in [1] it was proposed to extend this modeling. In this paper a pure Bayes approach is presented, which calculates all areas of the dynamic Grid map probabilistic. Now, the resulting modeling generates hypotheses, which represent the dynamic behavior of unobservable objects. Thus, objects moving out of unknown areas can be detected more quickly. This leads to a more intuitive understanding as well as representation of the environment.
-
FUSION - Hidden Markov model-based occupancy Grid Maps of dynamic environments
2016Co-Authors: Matthias Rapp, Bharanidhar Duraisamy, Klaus Dietmayer, Markus Hahn, Jürgen DickmannAbstract:For a reliable localization in dynamic environments, a robust representation is of vital importance to obtain an accurate position estimation. This paper introduces a hidden Markov model-based approach to obtain robust representations of dynamic environments. The model uses occupancy Grid Maps created at different times as observations. The approach involves a Grid map registration process for pre-processing to align new observations impacting the robust representation. It uses a combined feature-based registration method and NDT-based refinement. For the robust representation, a hidden Markov model is used to estimate the probabilities of static and dynamic states of cells based on observations. The robust representation is updated with each new observation using an iterative propagation algorithm. Experiments on real world radar data demonstrate that a localization algorithm based on this method provides a more reliable localization performance than a standard approach.
-
a random finite set approach for dynamic occupancy Grid Maps with real time application
arXiv: Robotics, 2016Co-Authors: Dominik Nuss, Stephan Reuter, Markus Thom, Gunther Krehl, Ting Yuan, Michael Maile, Axel Gern, Klaus DietmayerAbstract:Grid mapping is a well established approach for environment perception in robotic and automotive applications. Early work suggests estimating the occupancy state of each Grid cell in a robot's environment using a Bayesian filter to recursively combine new measurements with the current posterior state estimate of each Grid cell. This filter is often referred to as binary Bayes filter (BBF). A basic assumption of classical occupancy Grid Maps is a stationary environment. Recent publications describe bottom-up approaches using particles to represent the dynamic state of a Grid cell and outline prediction-update recursions in a heuristic manner. This paper defines the state of multiple Grid cells as a random finite set, which allows to model the environment as a stochastic, dynamic system with multiple obstacles, observed by a stochastic measurement system. It motivates an original filter called the probability hypothesis density / multi-instance Bernoulli (PHD/MIB) filter in a top-down manner. The paper presents a real-time application serving as a fusion layer for laser and radar sensor data and describes in detail a highly efficient parallel particle filter implementation. A quantitative evaluation shows that parameters of the stochastic process model affect the filter results as theoretically expected and that appropriate process and observation models provide consistent state estimation results.
