TechTalks from event: Technical session talks from ICRA 2012

Conference registration code to access these videos can be accessed by visiting this link: PaperPlaza. Step-by-step to access these videos are here: step-by-step process .
Why some of the videos are missing? If you had provided your consent form for your video to be published and still it is missing, please contact support@techtalks.tv

Multi Robots: Task Allocation

  • Competitive Analysis of Repeated Greedy Auction Algorithm for Online Multi-Robot Task Assignment Authors: Luo, Lingzhi; Chakraborty, Nilanjan; Sycara, Katia
    We study an online task assignment problem for multi-robot systems where robots can do multiple tasks during their mission and the tasks arrive dynamically in groups. Each robot can do at most one task from a group and the total number of tasks a robot can do is bounded by its limited battery life. There is a payoff for assigning each robot to a task and the objective is to maximize the total payoff. A special case, where each group has one task and each robot can do one task is the online maximum weighted bipartite matching problem (MWBMP). For online MWBMP, it is known that, under some assumptions on the payoffs, a greedy algorithm has a {em competitive ratio} of $frac{1}{3}$. Our key result is to prove that for the general problem, under the same assumptions on the payoff as in MWBMP and an assumption on the number of tasks arising in each group, a repeated auction algorithm, where each group of tasks is (near) optimally allocated to the available group of robots has a guaranteed competitive ratio. We also prove that (a) without the assumptions on the payoffs, it is impossible to design an algorithm with any performance guarantee and (b) without the assumption on the task profile, the algorithms that can guarantee a feasible allocation (if one exists) have arbitrarily bad performance in the worst case. Additionally, we present simulation results depicting the average case performance of the repeated greedy auction algorithm.
  • Tunable Routing Solutions for Multi-Robot Navigation Via the Assignment Problem: A 3D Representation of the Matching Graph Authors: Liu, Lantao; Shell, Dylan
    In several scenarios in which new robots and tasks are added to a network of already deployed, interchangeable robots, a trade-off arises in seeking to minimize cost to execute the tasks and the level of disruption to the system, This paper considers a navigation-oriented variant of this problem and proposes a parameterizable method to adjust the optimization criterion: from minimizing global travel time (or energy, or distance), to minimizing interruption (i.e., obtaining the fewest number of robot reassignments), and mixtures in-between. Paths are computed by task-allocation formulation in which destination locations of newly deployed robots are added as tasks to an existing allocation. We adapt the graph matching variant of the Hungarian algorithm—originally designed to solve the optimal assignment problem in complete graphs—to construct routing paths by showing that there is a three-dimensional spatial interpretation of the Hungarian bipartite graph. When new agent-task pairs are inserted, the assignment is globally reallocated in an incremental fashion so it requires only linear time when the robots’ traversal options have bounded degree. The algorithm is studied systematically in simulation and also validated with physical robots.
  • An Efficient Stochastic Clustering Auction for Heterogeneous Robot Teams Authors: Zhang, Kai; Collins, Emmanuel; Barbu, Adrian
    Stochastic Clustering Auctions (SCAs) constitute a class of cooperative auction methods that enable improvement of the global cost of the task allocations obtained with fast greedy algorithms. Prior research had developed Contracts Sequencing Algorithms (CSAs) that are deterministic and enable transfers, swaps, and other types of contracts between team members. In contrast to CSAs, SCAs use stochastic transfers or swaps between the task clusters assigned to each team member and have algorithm parameters that can enable tradeoffs between optimality and computational and communication requirements. The first SCA was based on a "Gibbs Sampler" and constrained the stochastic cluster reallocations to simple single transfers or swaps; it is applicable to heterogeneous teams. Subsequently, a more efficient SCA was developed, based on the generalized Swendsen-Wang method; it achieves the increased efficiency by connecting tasks that appear to be synergistic and then stochastically reassigning these connected tasks, hence enabling more complex and efficient movements between clusters than the first SCA. However, its application was limited to homogeneous teams. The contribution of this work is to present an efficient SCA for heterogeneous teams; it is based on a modified Swendsen-Wang method.
  • Stochastic Motion Planning with Path Constraints and Application to Optimal Agent, Resource and Route Planning Authors: Lim, Sejoon
    We present algorithms for a motion planning for multiple agents whose goals are to visit multiple locations with probabilistic guarantees for achieving the goal. Though much research has been done in stochastic shortest path algorithms, the existing algorithms focus on the single-origin single-destination problem for one agent. This paper formulates a general framework for the stochastic shortest path problem with visit node constraints designed to achieve a specific goal with multiple agents, multiple resources, and multiple destinations. The constraints are defined by a set of sequences of nodes to be visited. Given predetermined constraints, our motion planning problem consists of finding the best agents, resources, and destinations, and the path through a sequence of nodes representing them. The technique in this paper solves the problem at the same level of complexity as solving the single-origin single-destination problem by parallelization. We demonstrate the algorithm by a Web-based traffic navigation guide system and evaluate the algorithm’s performance.
  • Accounting for Uncertainty in Simultaneous Task and Motion Planning Using Task Motion Multigraphs Authors: Sucan, Ioan Alexandru; Kavraki, Lydia
    This paper describes an algorithm that considers uncertainty while solving the simultaneous task and motion planning (STAMP) problem. Information about uncertainty is transferred to the task planning level from the motion planning level using the concept of a task motion multigraph (TMM). TMMs were introduced in previous work to improve the efficiency of solving the STAMP problem for mobile manipulators. In this work, Markov Decision Processes are used in conjunction with TMMs to select sequences of actions that solve the STAMP problem such that the resulting solutions have higher probability of feasibility. Experimental evaluation indicates significantly improved probability of feasibility for solutions to the STAMP problem, compared to algorithms that ignore uncertainty information when selecting possible sequences of actions. At the same time, the efficiency due to TMMs is largely maintained.

Localization

  • 3-D Mutual Localization with Anonymous Bearing Measurements Authors: Cognetti, Marco; Stegagno, Paolo; Franchi, Antonio; Oriolo, Giuseppe; Buelthoff, Heinrich H.
    We present a decentralized algorithm for estimating mutual 3-D poses in a group of mobile robots, such as a team of UAVs. Our algorithm uses bearing measurements reconstructed, e.g., by a visual sensor, and inertial measurements coming from the robot IMU. Since identification of a specific robot in a group would require visual tagging and may be cumbersome in practice, we simply assume that the bearing measurements are anonymous. The proposed localization method is a non-trivial extension of our previous algorithm for the 2-D case, and exhibits similar performance and robustness. An experimental validation of the algorithm has been performed using quadrotor UAVs.
  • Online Model Estimation of Ultra-Wideband TDOA Measurements for Mobile Robot Localization Authors: Prorok, Amanda; Gonon, Lukas; Martinoli, Alcherio
    Ultra-wideband (UWB) localization is a recent technology that promises to outperform many indoor localization methods currently available. Yet, non-line-of-sight (NLOS) positioning scenarios can create large biases in the time-difference-of-arrival (TDOA) measurements, and must be addressed with accurate measurement models in order to avoid significant localization errors. In this work, we first develop an efficient, closed-form TDOA error model and analyze its estimation characteristics by calculating the Cramer-Rao lower bound (CRLB). We subsequently detail how an online Expectation Maximization (EM) algorithm is adopted to find an elegant formalism for the maximum likelihood estimate of the model parameters. We perform real experiments on a mobile robot equipped with an UWB emitter, and show that the online estimation algorithm leads to excellent localization performance due to its ability to adapt to the varying NLOS path conditions over time.
  • Orientation Only Loop-Closing with Closed-Form Trajectory Bending Authors: Dubbelman, Gijs; Browning, Brett; Hansen, Peter; Dias, M. Bernardine
    In earlier work closed-form trajectory bending was shown to provide an efficient and accurate out-of-core solution for loop-closing exactly sparse trajectories. Here we extend it to fuse exactly sparse trajectories, obtained from relative pose estimates, with absolute orientation data. This allows us to close-the-loop using absolute orientation data only. The benefit is that our approach does not rely on the observations from which the trajectory was estimated nor on the probabilistic links between poses in the trajectory. It therefore is highly efficient. The proposed method is compared against regular fusion and an iterative trajectory bending solution using a 5 km long urban trajectory. Proofs concerning optimality of our method are provided.
  • Capping Computation Time and Storage Requirements for Appearance-Based Localization with CAT− SLAM Authors: Maddern, William; Milford, Michael J; Wyeth, Gordon
    Appearance-based localization is increasingly used for loop closure detection in metric SLAM systems. Since it relies only upon the appearance-based similarity between images from two locations, it can perform loop closure regardless of accumulated metric error. However, the computation time and memory requirements of current appearance-based methods scale linearly not only with the size of the environment but also with the operation time of the platform. These properties impose severe restrictions on long-term autonomy for mobile robots, as loop closure performance will inevitably degrade with increased operation time. We present a set of improvements to the appearance-based SLAM algorithm CAT-SLAM to constrain computation scaling and memory usage with minimal degradation in performance over time. The appearance-based comparison stage is accelerated by exploiting properties of the particle observation update, and nodes in the continuous trajectory map are removed according to minimal information loss criteria. We demonstrate constant time and space loop closure detection in a large urban environment with recall performance exceeding FAB-MAP by a factor of 3 at 100% precision, and investigate the minimum computational and memory requirements for maintaining mapping performance.
  • Improving the Accuracy of EKF-Based Visual-Inertial Odometry Authors: Li, Mingyang; Mourikis, Anastasios
    In this paper, we perform a rigorous analysis of EKF-based visual-inertial odometry (VIO) and present a method for improving its performance. Specifically, we examine the properties of EKF-based VIO, and show that the standard way of computing Jacobians in the filter inevitably causes inconsistency and loss of accuracy. This result is derived based on an observability analysis of the EKF's linearized system model, which proves that the yaw erroneously appears to be observable. In order to address this problem, we propose modifications to the multi-state constraint Kalman filter (MSCKF) algorithm, which ensure the correct observability properties without incurring additional computational cost. Extensive simulation tests and real-world experiments demonstrate that the modified MSCKF algorithm outperforms competing methods, both in terms of consistency and accuracy.

Perception for Autonomous Vehicles

  • Active Perception for Autonomous Vehicles Authors: Unterholzner, Alois; Himmelsbach, Michael; Wuensche, Hans J
    Precise perception of a vehicle's surrounding is crucial for safe autonomous driving. It requires a high sensor resolution and a large field of view. Active perception, i.e. the redirection of a sensor's focus of attention, is an approach to provide both. With active perception, however, the selection of an appropriate sensor orientation becomes necessary. This paper presents a method for determining the sensor orientation in urban traffic scenarios based on three criteria: the importance of traffic participants w.r.t. the current situation, the available information about traffic participants while considering alternative sensor orientations as well as sensor coverage of the vehicle's relevant surrounding area.
  • A Probabilistic Framework for Car Detection in Images using Context and Scale Authors: Held, David; Levinson, Jesse; Thrun, Sebastian
    Detecting cars in real-world images is an important task for autonomous driving, yet it remains unsolved. The system described in this paper takes advantage of context and scale to build a monocular single-frame image-based car detector that significantly outperforms the baseline. The system uses a probabilistic model to combine multiple forms of evidence for both context and scale to locate cars in a real-world image. We also use scale filtering to speed up our algorithm by a factor of 3.3 compared to the baseline. By using a calibrated camera and localization on a road map, we are able to obtain context and scale information from a single image without the use of a 3D laser. The system outperforms the baseline by an absolute 9.4% in overall average precision and 11.7% in average precision for cars smaller than 50 pixels in height, for which context and scale cues are especially important.
  • Real-Time Topometric Localization Authors: Badino, Hernan; Huber, Daniel; Kanade, Takeo
    Autonomous vehicles must be capable of localizing even in GPS denied situations. In this paper, we propose a real-time method to localize a vehicle along a route using visual imagery or range information. Our approach is an implementation of topometric localization, which combines the robustness of topological localization with the geometric accuracy of metric methods. We construct a map by navigating the route using a GPS-equipped vehicle and building a compact database of simple visual and 3D features. We then localize using a Bayesian filter to match sequences of visual or range measurements to the database. The algorithm is reliable across wide environmental changes, including lighting differences, seasonal variations, and occlusions, achieving an average localization accuracy of 1 m over an 8 km route. The method converges correctly even with wrong initial position estimates solving the kidnapped robot problem.
  • SeqSLAM: Visual Route-Based Navigation for Sunny Summer Days and Stormy Winter Nights Authors: Milford, Michael J; Wyeth, Gordon
    Learning and then recognizing a route, whether travelled during the day or at night, in clear or inclement weather, and in summer or winter is a challenging task for state of the art algorithms in computer vision and robotics. In this paper, we present a new approach to visual navigation under changing conditions dubbed SeqSLAM. Instead of calculating the single location most likely given a current image, our approach calculates the best candidate matching location within every local navigation sequence. Localization is then achieved by recognizing coherent sequences of these “local best matches”. This approach removes the need for global matching performance by the vision front-end – instead it must only pick the best match within any short sequence of images. The approach is applicable over environment changes that render traditional feature-based techniques ineffective. Using two car-mounted camera datasets we demonstrate the effectiveness of the algorithm and compare it to one of the most successful feature-based SLAM algorithms, FAB-MAP. The perceptual change in the datasets is extreme; repeated traverses through environments during the day and then in the middle of the night, at times separated by months or years and in opposite seasons, and in clear weather and extremely heavy rain. While the feature-based method fails, the sequence-based algorithm is able to match trajectory segments at 100% precision with recall rates of up to 60%.
  • Image Sequence Partitioning for Outdoor Mapping Authors: Korrapati, Hemanth; Mezouar, Youcef; Martinet, Philippe
    Most of the existing appearance based topological mapping algorithms produce dense topological maps in which each image stands as a node in the topological graph. Sparser maps can be built by representing groups of visually similar images as nodes of a topological graph. In this paper, we present a sparse topological mapping framework which uses Image Sequence Partitioning (ISP) techniques to group visually similar images as topological graph nodes. We present four different ISP techniques and evaluate their performance. In order to take advantage of the afore mentioned maps, we make use of Hierarchical Inverted Files (HIF) which enable efficient hierarchical loop closure. Outdoor experimental results demonstrating the sparsity, efficiency and accuracy achieved by the combination of ISP and HIF in performing loop closure are presented.
  • Anytime Merging of Appearance Based Maps Authors: Erinc, Gorkem; Carpin, Stefano
    Appearance based maps are emerging as an important class of spatial representations for mobile robots. In this paper we tackle the problem of merging together two or more appearance based maps independently built by robots operating in the same environment. Noticing the lack of well accepted metrics to measure the performance of map merging algorithms, we propose to use algebraic connectivity as a metric to assess the advantage gained by merging multiple maps. Next, based on this criterion, we propose an anytime algorithm aiming to quickly identify the more advantageous parts to merge. The system we proposed has been fully implemented and tested in indoor scenarios and shows that our algorithm achieves a convenient tradeoff between accuracy and speed.