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.