Auctions for Time-Dependent Tasks

点击翻译按钮获取中文摘要

The PI will investigate methods for modeling and evaluating the decisions an agent must make when requesting quotes and when bidding for tasks that have complex time constraints and interdependencies. Time plays a major role in most human contracting and planning activities, yet current auction-based systems do not support decisions involving time constraints and inter-item dependencies. The way task schedules are specified in a Request for Quotes affects the number and types of bids received, and therefore the quality of the solutions that can be produced by such a system. Similarly, the way tasks are scheduled affects the ability of an agent to fit a new task into its own pre-existing commitments. The research will focus on two major goals: quantifying the relationships between schedules of tasks, bids, costs, and commitments of agents (to this end, the PI will develop theory, algorithms, and heuristics to maximize the expected utility for an agent scheduling tasks in a Request for Quotes and for an agent submitting bids); and experimentally validating the algorithms and heuristics in two application domains, supply-chain management and collaborative planning among robots and people. The project will provide a fundamental understanding of the tradeoffs between schedules and feasibility of tasks, in particular the dependencies between the way tasks are scheduled in a Request for Quotes, the bids they solicit, and their cost. The ability of agents to bid for tasks depends on their previous commitments, so different settings of time windows will end up soliciting different bids with different costs. The model proposed is based on Expected Utility Theory. Expected utility provides a natural way of accounting for the risk posture of the person or organization on whose behalf the agent is acting, and for modeling the tradeoffs between risks and profit expectations. The outcomes of the project will include a theoretical study of the dependencies between task schedules, bids, and costs, which will provide the foundations for efficient maximization algorithms and heuristics for determining optimal schedules, a collection of methods for generating practical schedules suitable for use in a Request for Quotes, algorithms and heuristics for an agent to generate bids for tasks with time and precedence constraints, and an experimental validation in two application domains, supply-chain management and collaborative planning among robots and people.Broader Impact: This research will produce a new theoretical understanding of the interdependencies between time and costs, which will lay the foundations for designing more capable agents, and thus will increase the effectiveness of systems of agents. The application scenarios address real world problems, and have significant societal impact. Improving the efficiency of supply-chain management has the potential to decrease costs and open new markets. The results of this work will be especially useful in situations involving a large number of intersecting constraints and/or dynamic environments with evolving constraints. Enabling teams of robots and people to plan and interact will make robots more useful for tasks such as monitoring large areas or helping people in their daily life. The software tools developed will be made available to the community at large.