The Operating Room Scheduling (ORS) problem refers to the task of assigning patients to operating rooms. An automated solution able to solve the ORS problem in real world scenarios should also be “explainable” to be fully acceptable. Answer Set Programming (ASP) has been successfully applied to solve the ORS problem. However, when the available resources are not enough to satisfy user's requirements (e.g., insuficient number of free beds) the system cannot compute a schedule, and also cannot provide an explanation for that “negative” result. In this work, we present an extension of the aforementioned ASP-based approach to the ORS problem that is also able to provide explanations (in terms of input facts) that caused the absence of solutions. The explanation computation technique builds on the ideas employed by the ASPIDE debugger for ASP programs. Preliminary experimental results show the viability of the approach.
The increasing use of Artificial Intelligence (AI) methods in applications is afecting all parts
of our lives and the need for explainable methods is becoming even more important. Even
though AI-driven systems have been shown to outperform humans in certain tasks, the lack of
explainability features continues to spark criticisms ([
Answer Set Programming (ASP; [
ASP has been proved to provide efective solutions to practical applications [
In this work we present a framework for the generation of the needed explanations. In
particular, our approach aims at generating explanations in case the instance modeling the
ORS problem is incoherent, hence the system is not able to compute a solution. More in
detail, our aim is to isolate the facts in the input that led to the incoherence: this procedure is
called facts checking. Furthermore, we make this knowledge available in a readable fashion for
inexperienced users such as medical staf. The explanation computation technique builds on the
ideas employed by the ASPIDE debugger for ASP programs ([
In this paper, the elements of the waiting list are called registrations. Each registration links a particular surgical procedure, with a predicted surgery duration and length of stay in the ward and in the ICU, to a patient. The overall goal of the ORS problem is to assign the maximum number of registrations to the operating rooms (ORs), taking into account the availability of beds in the associated wards and in the ICU. Three requirements are respected to solve the ORS problem: (i) the assignments must guarantee that the sum of the predicted duration of surgeries assigned to a particular OR session does not exceed the length of the session itself. To distinguish between registrations referring to patients with diferent medical conditions a priority factor is used. (ii) It must be ensured that a registration can be assigned to an OR only if there is a bed available for the patient for the entire length of stay (LOS). (iii) Also the Intensive Care Unit (ICU) is considered: it is a particular type of ward that is accessible to patients from any specialty. It must be ensured that a registration can be assigned to an OR only if there is a bed available for the patient for the entire length of stay (LOS) in the ICU if necessary.
Since our aim is to be able to identify facts that can lead to the inconsistency of the encoding, our focus will be in the input data given to the ORs scheduler. The input data is specified by means of the following atoms: • Instances of registration(R,P,SU,LOS,SP,ICU,A) represent the registrations, characterized by an id (R), a priority score (P), a surgery duration (SU ) in minutes, the overall length of stay both in the ward and the ICU after the surgery (LOS) in days, the id of the specialty (SP) it belongs to, a length of stay in the ICU (ICU ) in days, and finally a parameter representing the number of days in advance (A) the patient is admitted to the ward before the surgery. • Instances of mss(O,S,SP,D) link each operating room (O) to a session (S) for each specialty(SP) and planning day (D) as established by the hospital Master Surgical Schedule (MSS). • The OR sessions are represented by the instances of the predicate duration(N,O,S), where
N is the session duration. • Instances of beds(SP,AV,D) represent the number of available beds (AV ) for the beds associated to the specialty SP in the day D. The ICU is represented by giving the value 0 to SP.
Details about the encoding can be found in [
In this section, we show the integration of the ASP model for ORS and a debugging tool able to perform facts checking, with the goal of identifying the set of atoms modeling the input leading to the absence of a solution, i.e. to the inconsistency.
The idea of our approach is to implement a tool based on the work presented in [
We tested our framework under the following assumptions: (i) the test were carried out with a single encoding with 5 diferent configuration of the data: 2 representing the data necessary for the schedule of 5 days of operations and 3 representing the data necessary for the schedule of 10 days of operations, (ii) for each configuration, we are measuring the computation time from the beginning to the moment in which the error is found, and (iii) the set of facts included in the search are subject to a shufle , in which the atoms are shufled each time a new search begin, or to a reverse, in which the atoms are reversed once instead. Under these assumptions, we were able to identify two fact typologies that could lead to the inconsistency of the problem: (a) the lack of available beds in a certain specialty, given by facts of the type beds(SP,AV,D), and (b) the duration of a certain operation is higher than the available time of each OR of each day in a certain specialty, given by facts of the type duration(N,O,S).
As a sum up of our results, the reasons that can make a fact causing the incoherence are multiple. By analysing the knowledge represented by each fact, it is possible, for a domain expert, to categorize the source of the inconsistency: if the inconsistency is related to the number of beds available in a certain speciality SP in the day D its causes can be: (i) the lack of beds in the speciality in that specific day; or (ii) the number of patients to be scheduled in the speciality are too many; or (iii) the maximum time for the schedule is too short, or rather it is impossible to schedule all the patients in the amount of given days. If the inconsistency is related to the fact that duration N of a certain session S is higher than the available time of each OR of each day in a certain specialty, its causes can be: (i) the time that a patient must spend in an OR is too high, or (ii) the sum of the times that all patients, of a certain specialty (SP), must spend in an OR is too high.
When all the faulty atoms are isolated, we are able to extract many useful information to retrieve to user in order to let her/him decide which solution fits best, such as: the specialty that is causing the fault; the list of patients with high priority in those specialities and all their data (surgery duration, length of the stay, etc); the day in which the fault occurs; and the number of beds available in that day in the given specialty.
With all these information, the user can choose the best way to solve the problem, e.g., increasing the number of beds, increasing the number of maximum days to schedule, decreasing the number of patients. The initial results gathered after the preliminary test shows that this approach is able to extract information from real-world scenarios data and generate explanations understandable by an inexperienced user.
In Figure 1, it is possible to observe the schema of our framework. The Web Application uses
the encoding presented in [
The faulty encoding is sent to the Fault Detector Module which manages the data flow between the modules during the execution. Then, the Atoms Remover module removes all the low priority patients and all the weak constraints from the encoding since they cannot cause incoherence; therefore, they are not of our interest. After the preprocessing step, the faulty encoding is sent to the Debugging Tool module whose role is to identify the set of input facts leading to the inconsistency, i.e., it performs the facts checking. It is important to underline that we are searching the fault only inside the set of input facts given by the user since we assume that the encoding is properly written as we state in Section 3. The Debugging Tool operates within a given time limit, i.e., if the explanation is not found within such a threshold, then the debugging process is interrupted. In this case, the Faulty Detector Module performs a shufle of the KB atoms and starts a new facts checking process. This allows the tool to analyse always diferent atoms. This process is repeated until an explanation is found. It is important to notice that, during the preliminary test and analysis, we have noticed that shufling the facts atoms before starting the facts checking process tangibly improves the performances. Moreover, we noticed that, under certain circumstances, reversing the KB could lead to great improvements of the performances.
When an explanation is found then faulty atoms are sent to the Error Handler Module, whose goal is to generate a new set of input atoms where faulty atoms are corrected. Since the facts checking process searches for the minimal set of facts leading to inconsistency, fixing one faulty atom is enough to solve the inconsistency. For this reason, the Error Handler Module forces the removal of one of the faulty facts. In this way, two scenarios are possible: (i) there are other sources of inconsistency, therefore the ORS problem admits no solution, or (ii) a solution can be found. In the first case, the new set of faulty atoms is sent back to the Fault Detector Module and the explanation process restarts with such a new set. In the second case, the inconsistency is fixed.
When the inconsistency is fixed, the Explanability Module extracts and processes all the information from the list of faulty atoms in order to make them available in a comprehensible form to the user. In our case, the explanations are text messages aimed at making various information available to the user. In particular, since the user is assumed to be totally inexperienced with ASP, the generated messages are designed to put all the extracted information in the right context so that the meaning of the given information is clear to the user.
Message Example. The surgery time necessary to operate the patients of speciality 2 on day 10 exceeded the maximum time of operation at disposal of 30 hours for the operating room 5. Please increase the maximum operating time on some operating room or reduce the number of patients assigned to the faulty speciality.
The patients that might generate the error are: • Patient id: 2001 Speciality: 2
Total stay: 12 days Days at the ICU 0
Days in ward before surgery: 2 Surgery duration: 10 hours • Patient id: 2011
Total stay: 12 days Days in ward before surgery: 2
Speciality 2 Days at the ICU: 0
Surgery duration: 11 hours • Patient id: 2014
Total stay: 6 days Days in ward before surgery: 2
Speciality: 2 Days at the ICU: 0
Surgery duration: 10 hours
In order to obtain an assessment of the capabilities of the developed solution, we generated three diferent sets of facts. Each set represent the available resources of an hospital for a 10 day scheduling with the list of the patients to which is necessary to assign an OR. Each set is composed by 600 atoms approximately and they are designed to be solvable. In our analysis, 1 to 7 sources of inconsistency were forced in each set and each one is tested on the architecture 10 times. Observe that for any iteration the inconsistencies are forced in diferent input atoms.
For each iteration, a time limit of 60 seconds and a memory limit of 16 GB was applied. All the experiments have been conducted on an Intel i7-4790 CPU and Linux OS. Clingo was used to solve the ASP-encoded instances.
We compared the performance of the considered encodings using coverage, i.e., the percentage
of solved instances, and the Penalised Average Run-time (PAR10) score. The latter is a metric
usually exploited in machine learning and algorithm configuration techniques. It trades of
coverage and run-time for solved problems: if an encoding allows the solver to solve an instance
Π in time ≤ ( = 60 in our case), then 10(, Π) = , otherwise 10(, Π) =
10 × (i.e., 600 in our case). It is important to point out that the errors identified by the
architecture may vary from the errors forced in the input set, i.e., if we remove beds from a
speciality SP in a day D, then the architecture could suggest us to add beds for the speciality SP
but in a day D’. However, as it is possible to observe from the results (shown in table 1), our
system is able to identify the sources of the unsatisfiability under the 60 seconds timeout only if
in the input sets are forced 6 or less errors. It is important to underline that in this paper we are
not going to evaluate the understandability of the generated explanations; for a detailed study
in the field of the social sciences we refer to ([
In this paper, we have presented an approach to explaining the outcome of an ASP-based solution to the problem of operating room scheduling. The objective is to explain why, in # Set 2 0.51 0.9 17.12 26.77 30.67 50.34 600.0
Set 3
a certain situation, no appropriate schedule could be found, in other words, why no answer
set could be computed. The preliminary tests show that the presented approach is able to
identify the facts which led to the inconsistency of the solution. However, the generation of
the explanations is highly dependent on the treated domain: in order to be able to present an
explanation comprehensible to inexperienced users, the knowledge represented by the faulty
facts must be analysed by a domain expert with a deep understanding of the encoding. As we
stated in Section 3, the presented approach is able to find the minimal set of adorned atoms.
Since a single faulty fact is enough to lead to the inconsistency, our strategy will be able to find
one faulty fact at the time. To overcome this problem and being able to find the complete set
of faulty facts, we included in our architecture a module that handles the inconsistency: the
process used in this model is highly dependent by the domain. However, the process of finding
a single faulty fact is applicable to any domain. Moreover, the explanation generated by our
approach takes under consideration only the input facts: to generate exhaustive explications it
is necessary to include this approach into a platform of solutions, which consider also rules,
similarly to, e.g., [
Between cmodels and smodels), in: ICLP, volume 3668 of LNCS, Springer, 2005, pp. 37–51. [24] E. Giunchiglia, N. Leone, M. Maratea, On the relation among answer set solvers, Ann.
Math. Artif. Intell. 53 (2008) 169–204.