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

Motion Planning II

  • Modelling Search with a Binary Sensor Utilizing Self-Conjugacy of the Exponential Family Authors: Bonnie, Devin; Candido, Salvatore; Bretl, Timothy; Hutchinson, Seth
    In this paper, we consider the problem of an autonomous robot searching for a target object whose position is characterized by a prior probability distribution over the workspace (the object prior). We consider the case of a continuous search domain, and a robot equipped with a single binary sensor whose ability to recognize the target object varies probabilistically as a function of the distance from the robot to the target (the sensor model). We show that when the object prior and sensor model are taken from the exponential family of distributions, the searcher's posterior probability map for the object location belongs to a finitely parameterizable class of functions, admitting an exact representation of the searcher's evolving belief. Unfortunately, the cost of the representation grows exponentially with the number of stages in the search. For this reason, we develop an approximation scheme that exploits regularized particle filtering methods. We present simulation studies for several scenarios to demonstrate the effectiveness of our approach using a simple, greedy search strategy.
  • On the Probabilistic Completeness of the Sampling-Based Feedback Motion Planners in Belief Space Authors: Agha-mohammadi, Ali-akbar; Chakravorty, Suman; Amato, Nancy
    This paper extends the concept of “probabilistic completeness” defined for the motion planners in the state space (or configuration space) to the concept of “probabilistic completeness under uncertainty” for the motion planners in the belief space. Accordingly, an approach is proposed to verify the probabilistic completeness of the sampling-based planners in the belief space. Finally, through the proposed approach, it is shown that under mild conditions the samplingbased method constructed based on the abstract framework of FIRM (Feedback-based Information-state Roadmap Method) are probabilistically complete under uncertainty.
  • Egress: An Online Path Planning Algorithm for Boundary Exploration Authors: Guruprasad, KR; Dasgupta, Raj
    We consider the problem of navigating a mobile robot that is located at any arbitrary point within a bounded environment, to a point on the environment's outer boundary and then, using the robot to explore the perimeter of the boundary. The environment can have obstacles in it and the location and size of these obstacles are not provided a priori to the robot. We present an online path planning algorithm to solve this problem that requires very simple behaviors and computation on the robot. We analytically prove that by using our algorithm, the robot is guaranteed to reach and explore the outer boundary of the environment within a finite time.
  • Shortest Paths for Visibility-Based Pursuit-Evasion Authors: Stiffler, Nicholas; O'Kane, Jason
    We present an algorithm that computes a minimal-cost pursuer trajectory for a single pursuer to solve the visibility-based pursuit-evasion problem in a simply-connected two dimensional environment. This algorithm improves upon the known algorithm of Guibas, Latombe, LaValle, Lin, and Motwani, which is complete but not optimal. Our algorithm uses a Tour of Segments (ToS) subroutine to construct a pursuer path that minimizes the distance traveled by the pursuer while guaranteeing that all evaders in the environment will be captured. We have implemented our algorithm in simulation and provide results.
  • Hierarchical Motion Planning with Kinodynamic Feasibility Guarantees: Local Trajectory Planning Via Model Predictive Control Authors: Cowlagi, Raghvendra; Tsiotras, Panagiotis
    Motion planners for autonomous vehicles often involve a two-level hierarchical structure consisting of a high-level, discrete planner and a low-level trajectory generation scheme. To ensure compatibility between these two levels of planning, we previously introduced a motion planning framework based on multiple-edge transition costs in the graph used by the discrete planner. This framework is enabled by a special local trajectory generation problem, which we address in this paper. In particular, we discuss a trajectory planner based on model predictive control for complex vehicle dynamical models. We demonstrate the efficacy of our overall motion planning approach via examples involving non-trivial vehicle models and complex environments, and we offer comparisons of our motion planner with state-of-the-art randomized sampling-based motion planners.
  • Using State Dominance for Path Planning in Dynamic Environments with Moving Obstacles Authors: Gonzalez, Juan Pablo; Dornbush, Andrew; Likhachev, Maxim
    Path planning in dynamic environments with moving obstacles is computationally complex since it requires modeling time as an additional dimension. While in other domains there are state dominance relationships that can significantly reduce the complexity of the search, in dynamic environments such relationships do not exist. This paper presents a novel state dominance relationship tailored specifically for dynamic environments, and presents a planner that uses that property to plan paths over ten times faster than without using state dominance.

Estimation and Control for UAVs

  • Autonomous Indoor 3D Exploration with a Micro-Aerial Vehicle Authors: Shen, Shaojie; Michael, Nathan; Kumar, Vijay
    In this paper, we propose a stochastic differential equation-based exploration algorithm to enable exploration in three-dimensional indoor environments with a payload constrained micro-aerial vehicle (MAV). We are able to address computation, memory, and sensor limitations by considering only the known occupied space in the current map. We determine regions for further exploration based on the evolution of a stochastic differential equation that simulates the expansion of a particle system with Langevin dynamics. The regions of most significant particle expansion correlate to unexplored space. After identifying and processing these regions, the autonomous MAV navigates to these locations to enable fully autonomous exploration. The performance of the approach is demonstrated through numerical simulations and experimental results in single- and multi-floor indoor experiments.
  • Wind Field Estimation for Autonomous Dynamic Soaring Authors: Langelaan, Jack W.; Spletzer, John; Montella, Corey; Grenestedt, Joachim
    A method for distributed parameter estimation of a previously unknown wind field is described. The application is dynamic soaring for small unmanned air vehicles, which severely constrains available computing while simultaneously requiring updates that are fast compared with a typical dynamic soaring cycle. A polynomial parameterization of the wind field is used, allowing implementation of a linear Kalman filter for parameter estimation. Results of Monte Carlo simulations show the effectiveness of the approach. In addition, in-flight measurements of wind speeds are compared with data obtained from video tracking of balloon launches to assess the accuracy of wind field estimates obtained using commercial autopilot modules.
  • Decentralized Formation Control with Variable Shapes for Aerial Robots Authors: Turpin, Matthew; Michael, Nathan; Kumar, Vijay
    We address formation control for a team of quadrotors in which the robots follow a specified group trajectory while safely changing the shape of the formation according to specifications. The formation is prescribed by shape vectors which dictate the relative separations and bearings between the robots, while the group trajectory is specified as the desired trajectory of a leader or a virtual robot in the group. Each robot plans its trajectory independently based on its local information of neighboring robots which includes both the neighbor's planned trajectory and an estimate of its state. We show that the decentralized trajectory planners (a) result in consensus on the planned trajectory for predefined shapes and (b) achieve safe reconfiguration when changing shapes.
  • Versatile Distributed Pose Estimation and Sensor Self-Calibration for an Autonomous MAV Authors: Weiss, Stephan; Achtelik, Markus W.; Chli, Margarita; Siegwart, Roland
    In this paper, we present a versatile framework to enable autonomous flights of a Micro Aerial Vehicle (MAV) which has only slow, noisy, delayed and possibly arbitrar- ily scaled measurements available. Using such measurements directly for position control would be practically impossible as MAVs exhibit great agility in motion. In addition, these measurements often come from a selection of different onboard sensors, hence accurate calibration is crucial to the robustness of the estimation processes. Here, we address these problems using an EKF formulation which fuses these measurements with inertial sensors. Compared to existing approaches we do not only estimate pose and velocity of the MAV, but also states such as sensor biases, scale of the position estimate and self (inter- sensor) calibration in real-time. Furthermore, we show that it is possible to obtain a yaw estimate from position measurements only. We demonstrate that the proposed framework is capable of running entirely onboard a MAV boosting its autonomy, performing state prediction at the rate of 1 kHz. Our results illustrate that this approach is able to handle measurement delays (up to 500ms), noise (std. deviation up to 20 cm) and slow update rates (as low as 1 Hz) while dynamic maneuvers are still possible. We present a detailed quantitative performance evaluation of the real system under the influence of different disturbance parameters and different sensor setups to highlight the versatility of our approach
  • Probabilistic Velocity Estimation for Autonomous Miniature Airships Using Thermal Air Flow Sensors Authors: Mueller, Joerg; Paul, Oliver; Burgard, Wolfram
    Recently, autonomous miniature airships have become a growing research field. Whereas airships are attractive as they can move freely in the three-dimensional space, their high-dimensional state space and the restriction to small and lightweight sensors are demanding constraints with respect to self-localization. Furthermore, their complex second-order kinematics makes the estimation of their pose and velocity through dead reckoning odometry difficult and imprecise. In this paper, we consider the problem of estimating the velocity of a miniature blimp with lightweight air flow sensors. We present a probabilistic sensor model that accurately models the uncertainty of the flow sensors and thus allows for robust state estimation using a particle filter. In experiments carried out with a real airship we demonstrate that our method precisely estimates the velocity of the blimp and outperforms the standard velocity estimates of the motion model as applied in many existent autonomous blimp navigation systems.
  • Efficient Human-Like Walking for the COmpliant Humanoid COMAN Based on Kinematic Motion Primitives (kMPs) Authors: Moro, Federico Lorenzo; Tsagarakis, Nikolaos; Caldwell, Darwin G.
    Research in humanoid robotics in recent years has led to significant advances in terms of the ability to walk and even run. Yet, despite the general achievements in locomotion and control, energy efficiency is still one important area that requires further attention, especially as it is one of the major steeping stones leading to increased autonomy. This paper examines, and quantifies, the energetic benefits of introducing passive compliance into bipedal locomotion using COMAN, an intrinsically COmpliant huMANoid robot. The novelty of the method proposed consists of: i) the use of a method of gait synthesis based on kinematic Motion Primitives (kMPs) extracted from human, ii) the frequency tuning of the resultant trajectories, to excite the physical elasticity of the system, and the subsequent analysis of the energetic performance of the robot. The motivation is to assess the possible effects of using dynamic human-like, and human derived, trajectories, with significant Center of Mass (CoM) vertical displacement, regulated in frequency around the frequency band of the system resonances, on the excitation of the compliant actuators, and subsequently to measure and verify any energetic benefit. Experimental results show that if the gait frequency is close to one of the main resonant frequencies of the robot, then the total work contribution of the elastic compliant element to the overall motion of the robot is positive (15% of the work required is generated by the springs).
  • State Estimation for Aggressive Flight in GPS-Denied Environments Using Onboard Sensing Authors: Bry, Adam (Massachusetts Institute of Technology), Bachrach, Abraham (Massachusetts Institute of Technology,), Roy, Nicholas (Massachusetts Institute of Technology)
    In this paper we present a state estimation method based on an inertial measurement unit (IMU) and a planar laser range finder suitable for use in real-time on a fixed-wing micro air vehicle (MAV). The algorithm is capable of maintaing accurate state estimates during aggressive flight in unstructured 3D environments without the use of an external positioning system. Our localization algorithm is based on an extension of the Gaussian Particle Filter. We partition the state according to measurement independence relationships and then calculate a pseudo-linear update which allows us to use 20x fewer particles than a naive implementation to achieve similar accuracy in the state estimate. We also propose a multi-step forward fitting method to identify the noise parameters of the IMU and compare results with and without accurate position measurements. Our process and measurement models integrate naturally with an exponential coordinates representation of the attitude uncertainty. We demonstrate our algorithms experimentally on a fixed-wing vehicle flying in a challenging indoor environment.

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.