Auctions for Time-Dependent Tasks

PI将研究代理在请求报价和投标具有复杂时间限制和相互依赖性的任务时必须做出的决策的建模和评估方法。时间在大多数人类合同和计划活动中起着重要作用，但目前基于拍卖的系统不支持涉及时间限制和项目间依赖关系的决策。在报价请求中指定任务时间表的方式会影响收到的投标的数量和类型，因此也会影响由该系统产生的解决方案的质量。同样，任务调度的方式也会影响代理将新任务融入其已有承诺的能力。研究将集中在两个主要目标上：量化任务、投标、成本和代理承诺之间的关系（为此，PI将开发理论、算法和启发式方法，以最大化代理在报价请求中调度任务和提交投标的代理的预期效用）；并在供应链管理和人机协同规划两个应用领域对算法和启发式进行了实验验证。该项目将提供对时间表和任务可行性之间权衡的基本理解，特别是在报价请求中安排任务的方式、它们所征求的投标和它们的成本之间的依赖关系。代理对任务的投标能力取决于他们之前的承诺，因此不同的时间窗口设置最终会以不同的成本征求不同的投标。该模型基于期望效用理论。期望效用提供了一种自然的方法来计算代理所代表的个人或组织的风险状况，并对风险和利润预期之间的权衡进行建模。该项目的成果将包括对任务时间表、投标和成本之间依赖关系的理论研究，这将为确定最佳时间表的有效最大化算法和启发式方法提供基础，为生成适合于报价请求使用的实际时间表的方法集合，为代理生成具有时间和优先级约束的任务的投标的算法和启发式方法。并在供应链管理和人机协同规划两个应用领域进行了实验验证。更广泛的影响：本研究将对时间和成本之间的相互依赖关系产生新的理论认识，这将为设计更有能力的代理奠定基础，从而提高代理系统的有效性。应用场景处理现实世界的问题，并具有重要的社会影响。提高供应链管理的效率有可能降低成本并打开新市场。这项工作的结果将在涉及大量交叉约束和/或具有不断发展的约束的动态环境的情况下特别有用。让机器人和人组成的团队进行规划和互动，将使机器人在监控大片区域或在日常生活中帮助人们等任务上更有用。开发的软件工具将向广大社区提供。

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.