Significant work has been dedicated to developing methods for communicating reasons for decision-making within au-
 tomated scheduling systems to human users. However, much less focus has been placed on communicating reasons for why
 scheduling systems are unable to arrive at a feasible solution when over-constrained. We investigate this problem in the
 context of task scheduling. We introduce the agent resource-constrained project scheduling problem (ARCPSP), an ex-
 tension of the resource-constrained project scheduling problem which includes a conception of agents that execute tasks
 in parallel. We outline a generic framework, based on efficiently enumerating minimal unsatisfiable sets (MUS) and
 maximal satisfiable sets (MSS), to produce small descriptions of the source of infeasibility. These descriptions are supple-
 mented with potential relaxations that would fix the infeasibility found within the problem instance. We illustrate how
 this method may be applied to the ARCPSP and demonstrate how to generate different types of explanations for an over-
 constrained instance of the ARCPSP. In many real-world applications, human users in charge of developing plans and making decisions are aided by automated planning and scheduling systems. For example, NASA mission planning makes use of a large team of human planners that use various automated scheduling systems in order to construct day-to-day as well as long-term plans for crew members. A primary function of these automated systems is generating different types of plans and schedules while ensuring that various constraints do not conflict. When plans are ultimately constructed by human planners for a human crew, it is essential for both the planners, and the crew executing the plans, to understand how and why certain scheduling decisions were made by automated tools. In general, when the primary function of such constraint satisfaction and optimization tools is to support human decision-making, it is necessary for the automated systems to be transparent in how they arrive at certain outputs.Significant work has been dedicated to generating humanunderstandable explanations for why certain automated planning decisions were made BID10 ).However , little work has been done in generating reasons for why plans or schedules cannot be generated under certain specifications. Human users interacting with such constraint satisfaction or optimization tools are bound to run into configurations for which no feasible solution exists. Fixing infeasible configurations is a challenging task for the human user if they are unable to understand why the solver arrives at an unsatisfiable conclusion.While various partial constraint satisfaction tools exist for solving such over-constrained problems BID4 , solutions employing these tools have significant limitations that make them less applicable in certain real-life scenarios. Most of these methods employ constraint hierarchies to determine which constraints should be violated in order to satisfy more important ones. However , in complicated planning or scheduling applications involving multiple human agents, constructing such a hierarchy is often impractical. Instead , if reasons for infeasibility can be properly conveyed back to the human user, they can make high-level decisions to solve infeasibility in any way they see fit.In this paper, we provide a framework for iteratively generating human-understandable explanations of infeasibility for a specific class of scheduling problems. These explanations manifest themselves as minimal sets of specifications (or constraints) that are responsible for causing infeasibility, coupled with suggestions for relaxations through which feasibility could be achieved.The method proposed in this paper allows users to enumerate over a series of explanations for infeasible instances of problems at varying levels of abstraction. For example , raw explanations of relevant low-level constraints may be directly output or a causal link may be established back to higher level descriptions of the problem to understand what specifications were responsible for the feasibility issue. This system also allows directed questions about feasibility to be asked, such as "why can task A not be scheduled after task B?"A strategy for iteratively generating minimal unsatisfiable sets (MUS) and maximal satisfiable sets (MSS) forms the basis for interpreting the infeasibility of the problem. Existing methods such as QuickXplain BID5 ) focus on generating a single most preferable explanation of infeasibility. Likewise, BID1 aims to generate a single explanation in the context of optimization without attempting to achieve minimality. However, overconstrained problems may contain several infeasibility issues which cannot be solved by changing only a single part of the problem. So, because a single MUS only provides indication of a single feasibility issue, we aim to enumerate several sets of MUS to highlight multiple feasibility issues found within the problem instance. Therefore, the proposed enumeration strategy is based on MARCO BID8 ), a flexible algorithm for generating MUSes and MSSes in succession.Motivated by the domain of space mission scheduling, we introduce and investigate the agent resource-constrained project scheduling problem (ARCPSP), an extension of the resource-constrained project scheduling problem (RCPSP) that incorporates the delegation of tasks to differing agents. This problem cannot be framed as an instance of the RCPSP because it deals with the case of asymmetric agents in which certain tasks may only be executed by a subset of the agents. This problem is meant to model applications in which efficient scheduling for teams of differing agents is critical. While we only explicitly investigate this problem, the generality of the approach outlined in this paper would allow the methodology to be adapted for different types of constraint satisfaction and optimization tools as well as different types of planning and scheduling problems.The main contributions of this paper are the following: firstly, we provide a formal definition of the agent resourceconstrained project scheduling problem (ARCPSP) in Section 3. Then in Section 4 we outline a difference logic encoding of the ARCPSP which is used to check feasibility of problem instances. The framework for generating humanunderstandable explanations of infeasibility for instances of the ARCPSP is described in Section 5. Finally, we provide an overview of the trade-off between interpretability and expressibility of different types of explanations and conclude by discussing how these ideas can be extended. We introduced the agent resource-constrained project scheduling problem (ARCPSP) along with an associated difference logic encoding. We proposed a general framework for generating minimal conflicts and minimal relaxations based on the MARCO algorithm and demonstrated how it could be used to generate varying types of descriptions for why infeasibility is occurring in instances of the ARCPSP. The framework outlined in this paper is general enough to be applied to constraint satisfaction formulations for various other scheduling and planning problems. These ideas may potentially be further extended to different kinds of formal languages, such as linear temporal logic, that are used to describe planning problems.
We develop a framework for generating human-understandable explanations for why infeasibility is occurring in over-constrained instances of a class of resource-constrained scheduling problems.
{"src": "scitldr-AIC_train", "paper_id": "rkG3QTnQcN"}