Browsing by Subject "Auctions"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Decentralized Allocation of Tasks with Temporal and Precedence Constraints to a Team of Robots
    (2017-01) Nunes, Ernesto
    The use of multiple robots is beneficial, and sometimes required, to complete sets of tasks. Designing functional multi-robot systems is particularly relevant in application domains such as search and rescue, surveillance, and warehouse management. Allocation of tasks to a team of robots is a well studied topic in the multi-robot systems field. In contrast, task allocation problems where tasks have constraints on where, when and in which order they should be performed have received limited attention, especially in decentralized settings where multiple decision makers are allowed. Here, we investigate multi-robot task allocation problems with temporal and precedence constraints. To address this class of problems, we employ decentralized algorithms to find approximate solutions that minimize the maximum time needed to complete all tasks. To achieve decentralization, we use auction-based insertion heuristics that allow robots to divide work among themselves. To do so, robots take active part in computing schedules that help the team achieve its objectives. This leads to solutions that are robust to the failure of any single robot or task. In this thesis, the use of decentralized algorithms in multi-robot task allocation is explored in four chapters. First, we propose a taxonomy for task allocation problems with temporal and ordering constraints. The taxonomy is the first in the multi-robot task allocation literature to focus specifically on these constraints. It also distinguishes between studies in which task allocation is done deterministically vs. stochastically, and between works that assume hard vs. soft constraints. The taxonomy provides a broad classification of the existing literature, and places our technical work within its different subclasses. Second, we explore the task allocation problem with temporal constraints and propose the temporal sequential single-item auction (TeSSI). TeSSI's key innovation is its combination of sequential single-item auctions and simple temporal networks. The auctions allows robots to distribute work among themselves. Each robot also controls its own simple temporal network, which is used to ensure that new allocations respect tasks' temporal constraints. One of the attractive aspects of the approach is that can be readily used in offline allocations, where tasks are known upfront, or in online scenarios, where tasks arrive over time. We validate the method experimentally, and show its competitiveness when compared to an optimal method, and its advantage over another state of the art auction, and a baseline greedy algorithm. Third, we study task allocation problems with general precedence constraints and propose the simple and prioritized iterated auctions (sIA and pIA). These auctions' novelty is the decomposition of precedence constraints, such that an auctioneer agent handles the precedence constraints, while individual robots bid on pairwise unconstrained tasks. The auctioneer abstracts the precedence graph into layers, and in each iteration a set of pairwise unconstrained tasks is formed and sent to the robots for bidding. We show via thorough experimental evaluations that the method is competitive, and in some instances achieves solutions that are 10% from an optimal solution. Fourth, we address the allocation and execution of tasks with temporal and precedence constraints. A re-purposed pIA auction that relies on a modified TeSSI auction is used for task allocation. A simple executor is also proposed. The executor is made robust by fast adjustments to robots' schedules when robots are delayed, and by a single-shot auction which is used when robots can no longer perform a task in their schedule. We validate the framework in simulation and also run experiments in a robotic testbed with three Turtlebot 2 robots. Additionally, we leverage the power of simulation as a schedule evaluation tool. We present risk and probabilistic analysis that enable users to assess when to readjust tasks' constraints to improve task completion. Taken together, this thesis proposes methods that divide tasks and constraints among the robots, such that each robot controls a subset of the constraints. This decomposition leads to low computational costs, flexibility to handle local failures, and greater individual robot autonomy. These features are important in designing responsive systems for groups of robots that operate in environments where exogenous events are common and may affect robot performance.
  • Thumbnail Image
    Item
    Essays on subcontracting, competitive bidding, and dynamic housing demand.
    (2009-10) Miller, Daniel Patrick
    The first essay quantifies and compares the impact of contractual incompleteness on subcontracting and in-house contracting costs. I examine 2,200 individual construction work items (i.e. drilling, concrete, traffic striping) on 32 bridge projects procured by the California Department of Transportation through competitive bidding. I use ex-post revisions to work item contracts to construct a measure of contractual incompleteness. I model strategic bidding behavior and derive a new structural approach to estimate costs from bids. The results show that contractual incompleteness raises procurement costs, up to 12% for subcontracted work. The effect for in-house work is much smaller. The results provide one of the first pieces of quantitative evidence supporting the incomplete contracting theories of the firm. In the U.S., macroeconomic policy makers are concerned about how consumers will respond to falling incomes, nominal home prices, falling income, rising mortgage interest rates and tightening credit standards. In the second essay, we estimate and simulate a dynamic structural model of housing demand. The model allows for realistic features of the housing market including non-convex adjustment costs from buying and selling a home and credit constraints from minimum downpayment requirements. We use the forward simulation procedure of Bajari, Benkard and Levin (2007) to estimate the structural parameters using data from the Panel Study of Income Dynamics. Given the estimated parameters, we simulate the partial equilibrium consumption and housing and financial asset accumulation response by consumers to negative income and home price shocks and a tightening of credit constraints. The simulation results demonstrate that many households do not adjust their stock of housing, but rather absorb the negative shocks by depleting home equity and reducing consumption. The intuition behind this result is simple---households only move two to three times before retirement. Because they are locked in, changes in housing market conditions do not influence their level of housing stock.
  • Thumbnail Image
    Item
    Repeated auctions for robust task execution by a robot team.
    (2010-12) Nanjanath, Maitreyi
    We study the use of auction based methods for allocation of tasks in a team of cooperative robots. The thesis makes contributions to this topic in three main directions: 1. We propose a novel auction algorithm for task allocation to robots that is specially suited for dynamic environments where unexpected obstacles, loss of communication, and other delays may prevent a robot from completing its allocated tasks. We present theoretical properties of the algorithm and experimental results, obtained both in simulation and using real robots in a variety of environments. 2. We extend combinatorial auctions for tasks that have precedence constraints and that require robots to visit task locations within assigned time windows. We present experimental results obtained in simulation and compare the allocation generated by the combinatorial auction algorithm with allocations generated by other auction algorithms. 3. We apply auctions to the RoboCup search and rescue scenario, a city-level simulation of a disaster situation where heterogeneous agents have to clear debris, extinguish fires, and rescue civilians. We propose an auction mechanism to coordinate the agents, and show its effectiveness.