1Computer Science and Engineering, U. Michigan, Ann Arbor, MI USA Find articles by Edmund H. Durfee 1Computer Science and Engineering, U. Michigan, Ann Arbor, MI USA Find articles by Lynn H. Garrett 2Physical Medicine and Rehabilitation, U. Michigan, Ann Arbor, MI USA Find articles by Abigail Johnson We motivate and overview a system for schedule management assistance that we are developing specifically to help adolescents with disabilities who are transitioning to independent adulthood. We summarize how we have overcome a number of engineering challenges in creating a prototype system. The expert feedback on our prototype suggests how and why the tool is expected to be useful, and has directed our focus toward handling schedule disruptions. In the latter part of this paper, we provide deeper technical material on new metrics and strategies for giving scheduling advice that is resilient to disruptions while also giving the user more freedom. Keywords: Schedule management, Assistive technology, Temporal reasoning A person living independently needs to carry out, at appropriate times, activities associated with daily living, school/work, social relationships, health maintenance, etc. Some people need schedule management assistance, especially when facing a transition (e.g., shouldering more responsibility when transitioning to adulthood, managing more complex demands when confronted with an infirmity, or coping with cognitive decline due to age or illness) [43, 44, 48]. While the assistive technology we present here is being developed to support adolescents with physical and cognitive disabilities in transitioning to independent adulthood, it is applicable in these other contexts as well. Young people with disabilities who are transitioning to managing their own lives can be especially overwhelmed when trying to navigate school/work, family, and social opportunities while also dealing with time-consuming health maintenance routines and unpredictable bouts of impairment [35]. In response, they can choose to simplify by withdrawing from what they might see as “optional” experiences like social engagement, or take risks and hope no catastrophic health consequences ensue [23]. On-line educational resources, the advice of family and of care providers, and tips from others who have faced similar problems can all help guide decisions about how to solve such complicated scheduling problems. However, such guidance from others inevitably reflects the priorities and preferences of the people who provide it, which may not always align well with those of a particular adolescent. We are thus designing, prototyping, and evaluating decision-support technologies to augment the cognition of inexperienced and vulnerable adolescents in order to improve their understanding of how immediate decisions have consequences on the scheduling of work, social, and healthcare activities over the course of a day. The conceptual model underpinning our approach is to empower the adolescent to explore spaces of solutions to find what works best for him or her, right now. We assert that artificial intelligence techniques for agent-based scheduling and schedule coordination can be the core of a computational tool that adolescents can use to rapidly investigate the implications of alternative decisions about activities to perform on other parts of their day, and on the days of family members and caregivers. Specifically, our tool focuses on scheduling and prioritizing activities associated with health (e.g., nutrition, exercise), daily living (e.g., hygiene, organization), and societal participation (e.g., attending school, socializing with friends). Some of these activities can require participation of others, such as when parents provide transportation to the adolescent, help the adolescent with homework, or share a meal with the adolescent. The outline of this paper, and its contributions, are as follows. First, in Section 2, we give an example of the type of scheduling problem, involving an adolescent and parent, for which our system has been designed. This example will be used for illustration throughout the rest of the paper, beginning in Section 3 where we summarize limitations of available technologies for solving this type of problem. Section 4 presents the first contribution of this paper, which is showing how existing ideas for robust automated scheduling can be repurposed for the needs of this domain, as well as where they fall short. The second contribution, therefore, is to introduce new computational and representational strategies, in Sections 5, 6, and 7, to overcome these shortcomings. The result is a prototype system that offers a user considerable freedom in deciding how the day will play out, but that helps the user, and others with whom the user must coordinate schedules, understand how possible choices they are free to make impact future freedom over choices. A third contribution, in Section 9, is to summarize, quantitatively and qualitatively, the reactions of members of the target community to the usefulness and likelihood of adoption of this type of scheduling assistant based on our prototype. Finally, the last sections of this paper (Sections 10, 11, and 12) dive deeper into how our system prevents schedule disruption due to sporadically occurring health maintenance activities. Our technical contributions on this front are a novel formal specification of this type of problem, and an evaluation of algorithms to solve it that can balance user freedom and schedule robustness. The fairly simple running example of a scheduling problem that we use for the rest of this paper is as follows. Prior to school, the adolescent needs to get out of bed, eat breakfast, shower (unless they will instead shower before bed), get dressed, organize homework/lunch for school, and get to school (by either taking a bus or getting a ride from a parent). Each of these activities is required to happen sometime between 5 am and when school starts, but the specific starting and ending times for each over this interval are purposely not prespecified—the adolescent should get choices over the ordering and timing of these activities so long as they are all done before school. Each activity also has a minimum and maximum duration (e.g., eating breakfast could take from 5 to 15 min) corresponding to how much time to set aside to complete it.1 There are constraints over clock times that these activities occur, since the adolescent cannot get up before 5:00 am and cannot be late for school. There are also constraints between these activities, such as getting out of bed always comes first; getting to school always comes last in the morning; if the adolescent showers before school then it must be before getting dressed; and taking a medication with food at least an hour before school starts means starting breakfast at least an hour before school. Finally, there are constraints between some of these activities and activities of others, such as whether a parent’s work schedule this day leaves the parent with time to drive the adolescent to school. The adolescent similarly has after-school activities that include getting from school to a martial arts class; participating in the class; getting home; spending 2 h on homework (though not necessarily all in one block of time) where at least 30 min of that time should be spent with a parent helping the adolescent; eating dinner with family; showering if a shower was not taken in the morning; socializing with friends on the internet; organizing for the next day; and going to bed. As in the morning, there are durations associated with these activities, constraints on the clock times when some of them can occur (when school lets out, latest bedtime), constraints on the timings between the activities (going to bed is always last, evening showers happen after dinner), and constraints on timings of different people’s activities (doing homework with a parent, the family sitting down to dinner together). While a parent could formulate a fixed schedule for such a day and then ask the adolescent to follow it, as stated before our goal is instead to support the adolescent in making their own decisions as they transition to independent adulthood. Furthermore, our aim is to allow the adolescent’s preferences on a given day to lead to a schedule that works best that day, rather than being locked into following a repetitive schedule every day. This is in fact a central requirement for our system: its goal is to avoid telling the adolescent what to do, and instead the system should give the adolescent as many choices as possible so long as the choices can be incorporated into some schedule that keeps the adolescent safely on track (completing all activities without violating constraints). To do this, the technology we provide should help solve complex scheduling problems in ways that allow a user to flexibly satisfy preferences. Various technologies to aid in adhering to schedules already exist, but none provides the combination of choice flexibility, assurance of timing and completion, and coordination across individuals’ activities, that our system supports. We can characterize available systems in terms of whether they are geared toward business versus personal needs, and whether they focus on managing time versus tasks. A growing variety of systems have been developed to manage schedules and projects in business settings; rather than enumerate them all here, we refer to the Capterra buyers-guide website [9]. While such systems run the gamut from scheduling employees, to allowing clients to schedule appointments, to scheduling project phases, the important point about such systems from our application’s perspective is that they emphasize nailing down what exactly will happen when, which is exactly right for business settings. But for personal schedule management, flexibility and the freedom to be spontaneous are also quite important. While fewer, various systems for personal schedule management exist; widely used tools like Google Calendar [17] and Microsoft Outlook [24] can keep track of, and provide reminders for, personal appointments as well as business activities, but these systems do not inherently support flexibility: rearranging activities can involve substantial cognitive skills that our target community disproportionately lacks. A simpler tool that some members of our community report using is TickTick [36], but this focuses more on managing tasks (maintaining a prioritized checklist, with deadlines) than on our problem’s need for managing activities (accounting for how long things take and ensuring time for necessary activities to get done). Such a more sophisticated system is Evernote [14], where the user can associate instructions and tips with to-do tasks. AbleLink Technology’s Endeavor system [1] similarly supports reminders about how to carry out an activity, but embeds these in a more inflexible calendering system rather than in a (timing-unaware) “to-do” list. The most similar existing application we have found to our prototype system is SmartDay [33]. SmartDay supports both obligatory tasks that take place at specific times (like a calendar system) and also tasks (specified with durations) that can be fit in around the scheduled tasks. SmartDay automatically fits floating tasks into spaces in the calendar. However, these are fit in as early as possible, which differs from the philosophy of our system where a user is given flexibility to reorder or even postpone such activities, if they choose, unless, and until any further delays would violate other constraints (e.g., being late for school or dinner, not leaving enough time for homework). Unfortunately, it appears that SmartDay is no longer actively being developed and supported. A final tool to mention is Cozi [11] which, while not as advanced in terms of flexible time management as our approach and some of the examples above, emphasizes coordination among family members, as our system does. In Cozi, a family can share a calendar, to-do list, and even a shopping list. Our system does not emphasize such sharing of information, and in fact attempts to restrict what one person knows of another’s schedule to only where their activities interact (e.g., I know you need family dinner to be later, but not why), but more proactively propagates the effects of one person’s decisions on another person’s calendar, as will be shown in Section 6. Our tool draws heavily from the literature on automated scheduling. Scheduling has been an active topic of research in various fields such as operations research and AI for many years [12, 15, 21]. We particularly build on prior work in temporal constraint reasoning [20, 22, 25, 41]. The field has defined classes of problems such as the Simple Temporal Problem (STP) and Disjunctive Temporal Problem (DTP), where the former defines exactly which timing constraints must always be met and can be solved in polynomial time [3, 7, 19, 29, 30, 47], while the latter allows for (often exponentially) many possible combinations of timing constraints to satisfy the problem and thus requires exponential time to solve [3, 4, 10, 26, 27, 32, 38]. An emphasis of algorithms for solving STPs and DTPs is that the algorithms should not simply find a single satisfying schedule, as such schedules are brittle to environmental contingencies, but rather should identify a space of feasible schedules, and work to keep this space as large as possible despite the introduction of new constraints over time [2, 3, 13, 20, 31, 34]. The past work in the field thus provides a strong foundation for developing a tool for our application domain. However, doing so requires recasting the strengths of past work into a form we can exploit. Specifically, as mentioned above, past work has placed an emphasis on the need for schedules that are flexible because unexpected events could arise that should be fit into the schedule. Such occurrences can certainly arise in our application domain as well, and later in this paper we will return to this concern. But to begin with, a more pressing need in our application is in flexibility for choice. An adolescent, even more so than someone of a different age, will likely rebel against being told what to do, so providing choices is paramount. Furthermore, an adolescent, again possibly more frequently than non-adolescents, will crave variety, and so even if the adolescent prefers a particular ordering to the activities of the day one day, it is far from certain their preferences would remain stationary for future days. Thus, a key insight of our work on applying prior flexible scheduling techniques to our application domain is to recognize that we can repurpose strategies that improved flexibility for autonomous systems to absorb unexpected events, to instead improve flexibility for human users with unpredictable and changing preferences. The first step in using our scheduling tool is to specify a scheduling problem. The kinds of scheduling problems our user community faces are inherently disjunctive: in our running example problem, for instance, the ordering between eating breakfast and getting dressed is flexible, as are decisions about the timing of homework and dinner, or even whether showering will occur in the morning or evening. Thus, our system formulates a schedule as a Disjunctive Temporal Problem (DTP). A DTP D = {V, C} is specified as a set V of timepoints and a set C of disjunctive temporal constraints. The set V contains a timepoint for the start time and the end time of each activity, as well as a zero reference timepoint Z that corresponds to midnight on a given day. Temporal constraints in C are expressed between timepoints, such as saying the S chool start time is no later than 7:40 am, which is 460 min past midnight (SS − Z ≤ 460), saying that B reakfast has a 30-min duration between start and end times (BS − BE ≤− 30 and BE − BS ≤ 30), saying that breakfast starts at least 60 min before school starts (BS − SS ≤− 60), and so on. These constraints can also include those between timepoints of different people (such as that the start times of the parent’s the adolescent’s dinner activities must be the same). Disjunctive temporal constraints (DTCs) correspond to disjunctions between such temporal difference constraints, specifying for example that either the end time of breakfast comes before the start time of dressing, or the end time of dressing comes before the start time of breakfast. That is, dressing and breakfast can happen in either order, but cannot occur at the same time. A solution to a DTP is an assignment of times to the timepoints such that every activity is scheduled (every timepoint is assigned) and all constraints (including DTCs) are satisfied. The combinatorial computation needed to fully solve a DTP is because the solution process involves finding solutions (if they exist) to each of the component STPs—the STPs corresponding to each combination of disjuncts from each of the DTCs. Since our system needs to solve a multiagent DTP (a DTP involving multiple interacting users), its underlying engine uses an implementation of Boerkoel’s multiagent STP (MaSTP) solver [3], invoking this solver for each of the component MaSTPs of the MaDTP [6], and summarizing the space of possible solutions [7]. As suggested in the previous paragraph, the number of (disjunctive) temporal constraints that need to be expressed for a realistic problem can be very large; even our simple running example of only the adolescent’s schedule has 147 temporal constraints (34 of which are disjunctive). Not only does specifying a problem thus take a long time, but it must be done by an expert who understands all of the different constraints that need to be explicitly expressed. Even for experts, it is easy to overlook some constraints, and/or to make mistakes in specifying other constraints, as the process can be tedious and nearly-but-not-exactly repetitive. Hence, to simplify and streamline this process, we have developed a higher level specification language where a scheduling problem is encoded in terms of activities and constraints between those activities. For the temporal constraints described above, for example, our specification language allows us to state that there are breakfast, school, and dressing activities; that the duration of breakfast is 30 min; that school starts at 7:40; that breakfast starts at least 60 min before school starts; that dressing and breakfast cannot occur at the same time, etc. More generally, the interactivity constraints our language currently supports are as follows: ordering constraints that force an activity to occur before another (by some interval); non-concurrency constraints that force two activities to not overlap (by some interval) but does not restrict relative ordering; synchronization constraints that force two activities to occur simultaneously; and exclusivity constraints that force a user to perform only one activity from a pair of activities (e.g., shower in the morning or in the evening but not both). We have implemented an algorithm that translates our higher level specification language into the formal DTP specification. For illustration, selected lines of the specification of our running example are in Fig. 1. Since it is an XML file, a variety of editors are available for manipulating such specifications. (A current list can be found on Wikipedia [45].) These lines illustrate how the system knows that the problem involves two agents, and that the adolescent’s scheduling problem can be nearly decoupled into two pieces (before-school and after-school); the advantages of this near-decoupling are covered in Section 7. The specification of the activity of showering in the morning is then shown, and includes a disjunctive constraint saying that it either lasts 20 min or takes no time (for when the shower happens in the night). The shower-at-night activity (not shown) is similarly specified, but with different availability. Examples of two constraints that generate disjunctive temporal constraints then appear. The first expresses that the morning shower and breakfast can happen in either order, without any minimum time between them, but cannot overlap. The second says that exactly one of showering in the morning or in the evening will have non-zero duration.  Partial example problem specification Since translating such a specification into the DTP representation is mechanical, the higher level specification relieves the person defining the problem from the tedium of entering the DTP details and ensures that the set of constraints corresponding to particular activities and relationships are consistently and correctly specified. The advantages of our high-level language become especially evident when the schedule contains disjunctive choices, e.g., traveling to school can take either 10 or 30 min depending on if you ride the bus or get a ride from a parent. Our language represents this by simply stating that the toSchool activity has a duration of 10 or 30. The formal DTP specification, on the other hand, requires four, 2-ary disjunctive temporal difference constraints to express this. Anecdotally, our problem specification language and translator have saved us many hours, and considerable frustration, in specifying the problems for developing, testing, and demonstrating our system. That said, of course, specifying the more abstract XML formulation might be difficult for a typical user of the system. The graphical user interface of the system can step the user through adding, deleting, and modifying activities (Section 6), and an advantage of the underlying XML format is that a variety of tools for populating, saving, and parsing such files exist, such that the user interface (and the ability to reuse past interactions) can evolve as available tools grow and change. Before delving into the processes by which underlying technologies can solve a specified DTP, it is instructive to examine how our system interacts with the user. Figure 2 is a screenshot of our Apple iPad system interface for getting choice decisions from the user. At the start of the day, or after the user has completed an activity, the system tells the user which activities can be chosen from to perform next. In this screenshot, for example, at the top of the left column the user is given a choice of 2 activities that could be performed at the start of the day: the user could wake up (with a duration of 10 min), or the user could choose to do an “other” activity (e.g., push the snooze bar) for anywhere from 5 min to an hour. The “other” option is presented whenever the current activities and constraints do not immediately force the user to perform an activity. If “other” is selected, the system asks for the desired duration, and the user thus is inserting a new “discretionary” activity (what the user does is at their own discretion), but where its allowable duration is limited (in this case to 60 min) to ensure it will not cause later constraint violations. We return to the question of how much time for an “other” activity should be offered, and whether less time should be offered to be able to handle possible future disruptions, in Section 10. Adolescent’s interface at start of day The activity selection process involves two steps: picking a (tentative) activity, and then confirming it (clicking in the lower left corner of the interface). To decide whether to confirm it, the interface provides visual feedback to the user about the consequences of the tentative choice. Our current visualization is to the right of that left-most column, and attempts to provide the user with helpful knowledge without being overwhelming.2 It is comprised of a vertical list of the user’s activities on the left, and to the right of each is a horizontal bar indicating the time range when the activity could occur. (The clock times are given at the bottom, and the current time is marked as a red, dashed vertical line.) For example, if we look at the morning shower (showerM) activity, it can happen anytime between 5:10 am and the beginning of school; note that this interval starts at 5:10 am rather than 5:00 am as specified in the input problem (Fig. 1) because the DTP solver has reasoned that showering cannot happen before the wakeup activity which takes at least 10 min and cannot start before 5:00 am. Similarly, note that the breakfast activity’s end time is substantially before the start of school: though the input problem just required it to finish before school starts, the DTP solver used additional constraints (e.g., that medication must be taken with food at least an hour before school starts) to discover the tighter interval. Within each interval, a darker gray region indicates the maximum duration the activity could take; conceptually, this can “slide” to anywhere within the wider interval, and represents flexibility for the user in how the day could progress. Figure 3 shows what the interface looks like when the user has tentatively chosen “other” for 60 min (say, to sleep in as long as possible). The system offered up to 60 min because it computed that with this delay (but no more) it is still possible for the user to successfully complete all the daily activities within their constraints. Visualizing consequences of sleeping in Though all the remaining activities can be scheduled, the visualization highlights with yellow the activities with reduced flexibility (possible times they could be done). Unsurprisingly, all the morning activities are highlighted (Fig. 3 (left)), since they all will need to be crammed together, and in fact the morning shower (showerM) had to be eliminated. (An activity’s interval before the tentative choice is shown in outline, and the reduced interval (if any) is in gray and yellow.) Because that means the night shower (showerN) must occur, some of the after-school activities (the ones highlighted in yellow) are also more constrained, and the user can swipe the timeline leftward (Fig. 3 (right)) to see these consequences. (Note swiping leftward also scrolls the list of activities upward to see them all.) When confronted with such significant consequences, the adolescent might (unless really tired) choose not to confirm, and instead change the choice to waking up, confirm, and perform the activity.3 At this point, the flexibility of our system is on display: compared with a fixed schedule that dictates what comes next, the adolescent can spontaneously choose between eating, showering, dressing, organizing, or even something other (like catching up on social media). Figure 4 illustrates a few tentative choices, where if today he woke hungry he could start with breakfast (Fig. 4a, left) which has few downstream consequences, while getting dressed (Fig. 4b) has more (because dressing immediately implies a mandatory shower before bed). Examples of possible choices The user interaction with the system also permits the user to add, delete, and modify activities. As a user gains deeper appreciation for downstream consequences of an activity choice, the choice of modifying a later activity can empower the user to express priorities. For example, if the user wants to perform an evening activity at a specific time (for example, to be on the computer at the same time as friends are), then instead of taking stabs at tentative earlier choices until one is found that allows a desirable timing later, the user can instead modify the computerTime activity’s start time to exactly when it is wanted, and the system will propagate the “consequences” of that choice upstream to narrow the choices earlier in the day accordingly. Currently, our modification functionality only supports such narrowing of an activity’s start- or end-time interval and/or shrinking of its duration, since such changes will never “break” (overconstrain) the problem. Similarly, deleting a future activity and all its constraints will always be possible since doing so only makes scheduling easier. Activity addition, however, makes the problem harder. If the new activity will “fit” without triggering any constraint violations, then it can simply be added, but if not the system must reject it, at least until enough deletions/modifications of existing activities allow it to “fit.” Further, specifying the myriad variations of constraints that could hold between each existing activity and the new one could be overwhelming, so our current interface simplifies the process by hardwiring some assumptions, such as that a new activity is assumed to be nonconcurrent (cannot overlap) with the performance of any existing activities, and that if ordered with another activity there need be no delay between them. We now illustrate the activity modification capability along with the multiagent aspects of our scheduling tool. The parent’s and adolescent’s schedules are linked in a few places: potential ride to school, helping with homework, and sharing dinner. If, the night beforehand, the parent discovers she needs to work late the next day, she can Modify her “work” activity to specify that the earliest time work will end is 6:00 pm (Fig. 5). The system as a result propagates those constraints within the parent’s schedule (dinner and helping with homework will be late) and those propagate into the adolescent’s schedule. Since now the adolescent will not have time to shower in the evening, he is given less discretionary time first thing in the morning (50 instead of 60 min), and Fig. 6 shows the consequences of “sleeping in” for those 50 min: like in Fig. 3, breakfast has to come shortly after wakeup (so as to take the medication an hour before school), but showerM must happen. Note that, the adolescent’s interface gives no details about the parent’s schedule to explain the reason for less snoozing and a mandatory morning shower today, just that dinner and homework together are happening later, precluding an evening shower, and thus requiring getting an earlier start to the day. We have collected information from survey and focus group participants about how useful and intuitive it will be for adolescents with disabilities, and their families, to have available a system for schedule management as prototyped above, and also including capabilities for anticipating certain kinds of schedule disruptions. We summarize the feedback later in Section 9. If used as designed, our system ensures that all activities are completed within constraints, barring unplanned disruptions. In fact, in cases where potential disruptions can be predicted, our system can still ensure success by holding enough discretionary time in reserve for them, as will be described in Section 10. When unpredicted disruptions occur (e.g., need to leave school early, homework takes longer than expected, etc.), then our system counts on a user (possibly a caregiver) to modify (e.g., shorten the duration of school, lengthen the duration of homework), add (e.g., add a return to school in the afternoon), and delete (e.g., remove evening computer time to accommodate longer homework) activities as needed. All that said, our schedule management tool of course cannot force the adolescent to use it as designed; overcoming non-compliance requires a more encompassing system including technologies to monitor behavior (e.g., detect medication adherance at breakfast) and to trigger rewards or punishments (e.g., text a parent about progress). To interact with user(s) in the manner just shown, the system needs to rapidly reason over the scheduling problem in response to (tentative) choices of users. Unfortunately, the number of possible solutions to consider for a DTP grows exponentially with the number of disjunctive constraints in the general case. This can greatly delay reflecting back to the user the “what if” consequences of a choice, especially as the number of activities and/or users grows. It is therefore important to exploit structure in the specified problems for computational advantage, whenever possible. Previous work [3, 5] developed techniques to efficiently decompose and solve multiagent scheduling problems. To summarize that work, each agent performs a variable-elimination process on its private timepoint variables, until all it has left are variables involved in constraints with other agents. The resulting structure summarizes how the local scheduling problem constrains the timing of activities across the agents, and we refer to those impacts on timing as the influences that an agent’s local scheduling problem has on the scheduling of another agent. For example, since the parent and adolescent in our running example want to have dinner together, each of their agents would reason over its local scheduling problem to determine the set of possible times that person has available for dinner. These times summarize the ways its local schedule influences the joint schedule through this constraint. Note that it is not necessary for an agent to completely solve its local problem to compute these influences, nor is it necessary for one agent to share private information about the reasons behind its influences with another agent. After computing these summaries of how their local problems influence each other, the next step is for the agents to reason about the part(s) of their scheduling problems that are connected, which is referred to as the agents’ shared scheduling problem. Continuing the example, suppose the adolescent and parent are available for dinner from 17:00–19:00 and from 18:15–19:30, respectively. They thus know that the 30-min dinner must start between 18:15 and 18:30. Each can propagate this tighter constraint about the start time of dinner into their schedule so as to make decisions that account for each others’ limitations about the timing of dinner without needing to know anything more about the sources of these limitations. This was illustrated in Fig. 6, where the parent’s anticipated late hours at work triggered an earlier start to the day for the adolescent, but where the adolescent would only know that dinner and homework need to happen later, and not why. However, leaving in an interval over which dinner will start can have negative consequences. Namely, every time either person makes (even just tentative) choices that tighten this interval (i.e., alters the influences), their respective agents will incur the cost of propagating that information, through the influences, to each other in order to ensure that a consistent solution remains. This in turn means that the timing of their scheduling decisions needs to be synchronized to avoid race conditions (and thus schedule inconsistencies) that could arise if they make choices concurrently. An example race condition would be if one modifies an after-dinner activity that would require dinner start at 18:15, while at the same time the other chooses an “other” activity that forces the dinner start to be delayed to 18:30. To avoid this, they would have to coordinate who gets to make choices when, so that one of these would happen first, leaving the other person with no choice to make the other happen. But such coordination impinges on the independence that is so desirable to each person. To avoid the disadvantages associated with synchronization and to streamline how each schedules the rest of the day, they can earlier in the day agree to start dinner at, say, 18:20, and add a new constraint to each of their local scheduling problems that restricts the start time of dinner to 18:20. If this were the only connection between their schedules, then they would be able to do their scheduling for the rest of the day independently and asynchronously of each other, conditioned on respecting this commitment to dine at 18:20. Then, with this constraint in place to decouple their problems, the final step is for the agents to each propagate such decoupling constraints to the rest of their local schedules. For example, given that dinner will start at 18:20 the adolescent might now be forced to start on homework after school but before dinner. The above summarizes prior work in scaling scheduling problems up to more agents by finding influences and using these to assert decoupling constraints that allow the agents’ problems to be solved independently. However, in that work, the individual agents’ problems tended to be relatively small. We discovered in developing our system that even a problem like our running example can involve combinatorics over disjunctive constraints within a single agent that can slow down the interaction with the user to unacceptable levels. Thus, we needed to develop an intra-agent strategy for streamlining computation. The novel advance that we present here is to utilize the notion of influence abstractions within a single agent’s reasoning processes. To do so, consider an agent’s schedule as a graph where activities are vertices and constraints are edges. If this graph has weakly connected sub-components, then those components can be viewed as different “agents” in a multiagent scheduling problem. For example, the adolescent’s schedule can be broken into morning and evening components that are weakly connected via the school activity, and the activities of one day are separated from those of another by a predictable “sleep” activity. In the specification in Fig. 1, this is expressed by telling the system that the first agent is represented as a multiDTP (as opposed to just a single DTP), comprised of two sub-DTPs. Each activity is indexed as being in sub-DTP 0 (for example, showerM) or 1 (for example, showerN). Only a few constraints apply across the sub-DTPs, such as the last constraint in Fig. 1 between showerM and showerN. A significant difference between a multiDTP and the prior work on multiagent scheduling is that the sub-DTPs are not actually different agents, but rather the same agent at different times (e.g., “before-school-me” and “after-school-me”). This distinction removes the concern that arises in true multiagent cases about concurrent choices being made that could lead to unsolvable situations, because we can assume that a single agent is only making one choice at a time: it could be deciding what to do next, or imposing a constraint on a later activity that impacts what it can do next, but will not being doing both of those things at once. Thus, decoupling constraints are not needed to ensure consistency across a single agent’s sub-DTPs. Therefore, rather than prematurely imposing a decoupling constraint that removes viable solutions (e.g., deciding before the day begins whether the shower will be taken in the morning or evening), we have revised the algorithm working within an agent to retain the inter-DTP constraints and simply propagate any inter-DTP influences across the shared scheduling component. This leaves the sub-DTPs connected rather than decoupling them. The trade-off here is that since the sub-DTPs are still interdependent, if a new constraint is added to the schedule (e.g., by selecting a specific time for an activity), then that information needs to be propagated to the other sub-DTP(s). However, because the sub-DTPs are related only through their influences, often a new constraint does not affect its sub-DTP’s outgoing influences, and thus propagation need not cross into other sub-DTPs, which can decrease computation substantially. For example, only when the morning activities have either included the shower or made it impossible to shower in the morning will the exclusivity constraint trigger any update to the after-school schedule. To give a sense of the computational advantages of this approach, we consider just the adolescent’s daily schedule (since this approach focuses on improving scheduling efficiency within an agent). While holding constant the total number of activities to be done, we introduce various degrees of connectedness: unconnected (no relationships between morning and evening showers), singly connected (only one shower needs to be done in a day), and doubly connected (only one shower and one organizational time need be done in a day). For each case, we propagate constraints to find the space of possible schedules from the start of the day using the standard DTP-solving technique (enumerating component STPs) both without and with our influence abstractions, and the average runtimes are shown in Table 1. Without influence abstraction, the time complexity is exponential in the total number of disjunctive constraints across the entire day, while our approach has time complexity that is the sum of the smaller exponentials associated with the number of disjuncts in each sub-DTP (half day) and the shared DTP. Thus, when the sub-DTPs are unconnected, a large (tenfold in our experiments) speedup is possible, while even as more connections are introduced the speedup can remain considerable. Average runtimes, in seconds
While in principle our algorithmic techniques can apply to large scheduling problems involving many agents, in practice, as our experiments show, their real-time scalability depends on the complexity of connections between the schedules of different agents, and between sub-DTPs of individual agents. Our prototype implementation assumes two agents (one for each of our research iPads), but could be straightforwardly extended to more. To avoid users perceiving a substantial slowdown with more agents, though, one or more of several strategies could be taken: (1) we could put the server on a more powerful computer; (2) we could speculatively precompute for possible choices of next activities while users are engaged in current activities; (3) we could restrict users to only specifying few connections between sub-DTPs; and/or (4) we could settle for less flexible solutions, where the computations time out and offer the user just the choices found so far. As summarized in Section 5, our automated algorithm to translate our higher level specification language into the formal DTP specification is straightforward for the usual constructs. However, the exploitation of sub-DTP structure within an agent’s local problem has required us to adapt our translation algorithm to make a more creative, unorthodox use of the DTP formalism. Most prominently, we have developed a technique for reducing the effective connectedness of the scheduling problem’s graph representation to exploit the computational strategies described in the previous section. The treatment of the shower activities in Fig. 1 and the previous section is an illustration of our technique. In principle, we could have (and in earlier implementations did) defined a single shower activity lasting 20 min that through disjunctive constraints would occur either before school (and if then before dressing) or after school (and if then after dinner). With this activity, the multiDTP concepts previously described cannot apply, because the same activity cannot appear in both sub-DTPs. As has previously been illustrated, our technique for overcoming this is to create duplicates of a tightly connected activity, partition the existing constraints among the duplicates, and then add a new exclusivity constraint between the activities. That is why the shower activity in the example problem was represented as showerM and showerN, where the morning constraints (shower before dressing) applied to showerM and the evening constraints (shower after dinner) applied to showerN. Both activities were given durations of either 0 or 20 min, and their inter-DTP exclusivity constraint ensures that exactly one of them takes non-zero time. (The other one, taking zero time, is guaranteed to be schedulable, since it can be fit in anywhere—it takes no time!) This encoding results in the weakly connected graph that led to the computational improvements described in Section 7 and Table 1. Over the course of our system development, we have periodically sought feedback from potential users and their caregivers. Our 2015 and 2016 focus groups consulted adolescents with disabilities, and their families, about pressing needs for such a tool. It was during those focus groups that we developed priorities to give users freedom. Adolescents with disabilities were found to value developmentally appropriate priorities for all adolescents (e.g., free time, social activity) over other priorities (e.g., health care routines, homework) and were likely to disengage (turn off) a system that was felt to be out of line with these priorities. Focus group results highlighted themes that many youth, particularly those who are younger or have more complex cognitive impairments, may lack the ability to predict consequences of ignoring health care routines or other scheduling constraints. Thus, adolescents and families would value a tool that helps them understand the possibly undesirable downstream consequences (e.g., being unable to chat on the internet when friends are online) of decisions that might feel good in the near term (e.g., pushing the snooze bar). Those focus groups also drew our attention to the challenges that adolescents with disabilities particularly face in that they are much more likely than other youth to have unpredictable health/medical issues suddenly arise, leading us to the thread of research on anticipating disruptions reported in Section 10 and beyond. In 2017, we sent a 26-item, Likert rating scale survey, based on the validated “perceived use” scale, about our prototype system to professional educators and clinicians who each work with adolescents and young adults in our target population in schools and therapeutic contexts. The majority of respondents had more than 10 year’s expertise working with adolescents with healthcare needs and disabilities. Special educators and therapist were selected for their expertise in teaching planning, scheduling, and task management skills to a wide range of adolescents with healthcare and learning needs, and for their related insights into the specific uses and applications of the technology. The data from the 157 returned surveys were quantitatively analyzed and descriptives indicated that a vast majority (more than 90%) of experts agreed that youth priorities align with emphases of our tool. Youth were perceived as most highly valuing having control over their schedules, protecting time for their own top priorities, planning to ensure free time during the day, and having confidence that they can complete all needed tasks in a day (Fig. 7). Results also found that experts saw a high level of value (more than 90% agreement) in our prototype’s ability to help youth prioritize tasks independently (Fig. 8 (left)), see how their choices affect their schedule (Fig. 8 (right)), and have more independent control over their day (Fig. 9 (left)). Comments were positive but less supportive regarding this tool’s ability to help adolescents independently manage healthcare emergencies or be healthier (Fig. 9 (right)). We afterward invited a small subset to focus groups in order to understand survey responses in greater depth. We verified these results by qualitative deductive analyses of 2 focus group discussions with a total of 9 clinicians. Primary themes from these focus groups included that youth would need direct instruction and practice to use this type of tool well, and good graphics (better than our current prototype interface) would streamline tool training and use. The reasons why opinions about this tool improving general health were more mixed were related to the level of the youth, and the healthcare activities involved. Specifically, younger or more impaired adolescents may not be ready to take on healthcare responsibility. With regard to healthcare responsibilities, the tool was felt to have likely indirect health benefits by helping youth managing chronic conditions; however, providers felt it would be of limited utility in acutely planning a response to a true health crisis as it currently stands. Our improvements to the speed and versatility of our techniques, through a novel approach to problem decoupling within an agent (Section 7) and by finding representational workarounds for modeling more complicated activity relationships (Section 8), move our prototype system closer to a deployable implementation. However, managing sudden disruptions to activities, like the example of falling ill and leaving school early in Section 6, can take time: the user might iteratively modify, add, and delete activities to restructure the day, invoking the scheduler at each iteration to visualize the revisions. Our tool can guide and streamline such restructuring if users can afford the upfront effort to specify priorities of and allowable adjustments to (e.g., shortening) activities beforehand. More generally, though, most human and automated schedulers try to hold some amount of slack time in reserve as a buffer for unexpected delays and emergent events. Holding slack time in reserve, however, means offering the user less discretionary time “just in case.” While a schedule disruption cannot be absorbed by the system if too little is held in reserve, holding too much in reserve risks alienating an adolescent user who perceives the system as too focused on parental priorities over giving the adolescent discretion over his time. The remainder of this paper investigates this tension between being robust to disruptions without unnecessarily restricting user freedom. We first formulate more precise, quantitative metrics for the notion of freedom (Section 10.1), and characterize a particular type of disruption that we call a sporadic activity (Section 10.2). Section 11 delves into our novel Disjunctively-Uncertain Temporal Problem (DUTP) formulation of this problem, and details of our new algorithms for the scheduler to ensure correct handling of a sporadic event whenever it occurs. While those details convey technical advances for developers of scheduling systems, other readers might choose to skim Section 11. In Section 12, we present and discuss empirical results comparing different strategies for balancing robustness and freedom. In our earliest focus groups (Section 9), adolescents said that a tool that always tells them to do something they do not want to do right now is likely to be ignored or shut off. That said, they also realized that even important activities they do not like (like homework and health maintenance routines) need to get done. What they want is as much “freedom” over their day as possible while still getting everything done. To implement a computer-based scheduling assistant, though, the notion of “freedom” must be made more precise, so our system can attempt to maximize it across the day’s decision points (the points in the day that the user decides to begin an activity). Previous work in the STP/DTP literature has measured freedom when maintaining a space of schedules in terms of flexibility and robustness metrics. Canonically, flexibility is quantified as temporal flexibility measured at the timepoint variable level and based on the sizes of availability intervals [18]. Refinements to this flexibility metric have been made such that it is a better representation of the ability of a schedule to absorb constraints that arise dynamically [46]. When these arising constraints can be modeled probabilistically, further work introduces a robustness metric with the intent of capturing the distribution of temporal flexibility to evaluate the likelihood of execution success [8]. In consulting with users and experts, we recognized that these prior metrics emphasized robustness to disruptions, but that is different from the kind of freedom that users want as they navigate through a day. In response, we identified two additional notions of freedom, beyond robustness, that capture interdependent wishes of users. We call these discretionary time freedom and activity choice freedom. Discretionary time in the social sciences [16] refers to time not otherwise allocated to a scheduled activity, like “downtime,” or time spent on an “other” activity (e.g., catching up on social media). At a decision point, a user performs either a defined or a discretionary time activity, where the maximum amount of discretionary time available is the longest they could wait before a defined activity must start without violating a constraint.4 We measure discretionary time freedom (DTF) during schedule execution by summing the discretionary time offered at each decision point with the discretionary time that the user has already taken up until that point. (Accounting for discretionary time that the user has already taken avoids overly penalizing the tool for the user’s decisions about when to use discretionary time and how much of the time offered is used.) Our empirical results in Section 12 average this measure over multiple simulated runs where the user’s behavior over which offered activity is chosen and how much discretionary time is taken if “other” is chosen, is randomized. We normalize this measure with respect to the maximum DTF that could have been offered. We define a maximum-DTF (mDTF) strategy for the scheduling tool as a strategy that always offers the maximum available DTF, but note that such a strategy can sacrifice other desiderata, such as activity choice freedom (discussed next) or robustness to disruptions (by leaving too little slack to absorb them). Our second metric measures freedom based on the number of activity choices offered when a defined activity must be done. We measure activity choice freedom (ACF) as the number of activities offered to the user at a decision point divided by the maximum number of activities that could have been offered. These numbers can differ when activities have timing restrictions. For example, if the adolescent must wait 30 min after taking an evening medication before starting homework, taking 10 min of discretionary time might limit their next activity to only computer time, but taking 30 min also allows homework. The ACF of a single schedule execution is the average number of activity choices offered over the decision points. As with DTF, we define a maximum-ACF (mACF) strategy that only offers an amount of discretionary time that will maximize the subsequent number of activity choices. We define a sporadic activity as one that is known about ahead of time (e.g., resolving a bladder accident), but whose timing, if it happens at all, is not known. To support and satisfy users, the schedule management assistant needs to balance the kind of freedom just discussed with constraining the user enough to ensure handling a sporadic activity. To strike a compromise, we adopt the following assumptions about a sporadic activity: (A1) It has a known and finite duration, d; (A2) it has a limited frequency (e.g., it occurs at most once during the scheduling period); (A3) it can start at any minute during the scheduling period early enough to finish by the scheduling period’s end; and (A4) if it arises during an ongoing (possibly discretionary) activity it must be addressed immediately after the activity ends. Under these assumptions, the scheduling assistant knows enough about the sporadic disruption (how long it could take, how frequently it could arise, etc.) to reserve enough slack time at the right times of day to ensure handling it successfully if it happens, and thus can with confidence devote all the remaining slack time toward the user’s freedom. In the next section, we give technical details about the new representations and algorithms we have developed for this purpose, as a contribution to the scheduling community. Readers not in that community can skim these details. We model a sporadic activity in a new formulation we call a Disjunctively Uncertain Temporal Problem (DUTP), which is like a DTP except some disjunctive choices (when the sporadic activity happens, if ever) are not controlled by the user. Formally, a Disjunctively Uncertain Temporal Constraint (DUTC) is a form of Disjunctive Temporal Constraint (DTC) that was described in Section 5: where each Ei is a conjunction, possibly singleton, of temporal difference constraints. The DUTC of a sporadic activity has a disjunct for each possible time it could arise, and a disjunct for it not occurring at all. Importantly, which disjunct Ei is true is determined exogenously (the “world” gets to choose when if at all the sporadic event occurs), which is what makes the constraint uncertain. Our new DUTP is a scheduling problem that includes a DUTC. Formally, a DUTP D=〈V,C,E,VE〉 is defined by:
The temporal problem D can be an STP or DTP. When D is an STP, we refer to the problem as a DU-STP to make clear the only disjunctive constraint is the DUTC. Just like a DTP is comprised of a set of component STPs, a DUTP is comprised of one or more DU-STPs, each composed of a component STP of the underlying temporal problem D along with the DUTC. Thus a solution to a DUTP is a solution to at least one of its component DU-STPs, which in turn is an assignment of values to timepoint variables V∪VE such that the constraints are satisfied, but where the timepoints in VE are exogenously assigned and not known until execution. The scheduling challenge, addressed in the rest of this section, is to assign the DUTP’s controllable timepoints V so as to anticipate and respond to any possible assignments of the uncontrollable timepoints VE of the DUTC. For example, the start time of breakfast is controllable and should be early enough that, if an uncontrollable activity to address a bladder accident must be squeezed in after eating, later constraints like getting to school on time will assuredly not be violated. Before describing our solution to this scheduling challenge, we briefly explain why we have defined the DUTP as opposed to mapping our problem into an existing temporal problem with uncertainty (TPU) formulation, the most prevalent of which is the Temporal Network with Uncertainty (TNU). In a Simple Temporal Network with Uncertainty (STNU) [42], every activity’s start time is controlled by the user, but some end times are not. For example, the time that commuting to school begins is under the user’s control, but the arrival time at school might not be, due to variable traffic congestion. Thus, each uncontrollable timepoint is associated with a controllable activation timepoint, and the uncertainty is in the bound (duration) between them. A Disjunctive Temporal Network with Uncertainty (DTNU) [28, 40] is defined similarly, but allows disjunctive temporal constraints. The kind of uncertainty (about when a started activity will end) that TNUs capture well differs from uncertainty about when a sporadic activity will begin. While in principle we could model uncertainty over a start time as durational uncertainty between some fixed reference point (e.g., midnight) and the sporadic activity’s start time, the resulting broad bounds (e.g., anywhere from 5 to 22 h!), and the inability to control when the duration starts, mean that the structural levers that DTPU algorithms exploit do not exist. Furthermore, recall that on any given day a sporadic activity might not happen at all; durational uncertainty does not capture the possibility that the uncontrollable timepoint might never need to be assigned. A more general temporal problem formulation supporting uncertainty is the Conditional Temporal Problem (CTP) [39], which introduces observation nodes and propositional labels to encode conditional branching in an STP or DTP. Our problem can be represented in this general CTP framework, but encoding the DUTP as a CTP generates a very large DTP problem, and standard DTP solvers are exponential in the input size. While CTPs with particular structural properties can be more efficiently solved [37], an encoded DUTP lacks such properties. Reusing terminology from the TNU literature, we say that a DUTP is dynamically controllable if, at any decision point during execution, the assignments to (controllable and uncontrollable) timepoints made so far can be extended to a complete assignment for any disjunct in the DUTC that could still be true. (Note that a disjunct becomes false when the time the sporadic activity would start in that disjunct has now passed without it occurring.) Dynamic controllability means that, at any decision point, one or more activities can be chosen that are compatible with all of the remaining possible timings of the sporadic activity. Since dynamic controllability involves considering every (viable) disjunct in a DUTC, the computational effort grows linearly in the number of disjuncts. The naïve encoding of a sporadic activity, with a disjunct for each possible start time (plus a disjunct for when it doesn’t occur at all), leads to computation that grows as the scheduling period lengthens and/or the discretization of time becomes more fine-grained. However, intuitively, we would expect that controlling for the sporadic activity arising at two different times during the same activity would be the same: in either case, the sporadic activity is performed immediately after the activity ends. Based on this intuition, we can prove straightforwardly that, for a DU-STP (where, recall, the scheduled activities are totally ordered) the naïvely enumerated DUTC disjuncts can be collapsed into a number of disjuncts linear in the number of activities, rather than clock ticks. Our algorithms exploit this insight to reduce computation. Because finding a dynamically controllable solution to a DUTP equates to finding at least one dynamically controllable (DC) component DU-STP, our DC-Checking algorithm is framed in terms of the DU-STP. We can refer to the set of instantiated STPs (iSTPs) of a DU-STP, where each iSTP is generated by taking the underlying STP S of the DU-STP and including a single component of the DUTC: iSTPs = {S ∪ Ei}, where Ei was defined in Eq. 1. Then, checking and maintaining dynamic controllability in a DU-STP means properly maintaining the set of valid iSTPs during execution. Specifically, at a particular decision point, say iSTPk includes the disjunct corresponding to the sporadic activity occurring during the just-finished activity. If the sporadic activity in fact occurred, then the set of valid iSTPs collapses to the singleton set containing iSTPk. If it did not occur, then iSTPk is removed from the set of valid iSTPs. Our DC-Checking algorithm builds a Decision Point Tree (DPTree) whose depth is the initial number of iSTPs, and whose nodes are the decision points. Each node is labeled with the set of iSTPs valid at this point. A node’s right child represents the sporadic activity occurring during the immediately preceding activity and contains a singleton set, and its left child removes the invalidated iSTP from the set. Each DPTree leaf contains a singleton set whose iSTP is when (if at all) the sporadic activity occurred. Our algorithm checks dynamic controllability by confirming at least one activity choice is valid for all iSTPs at each node of the DPTree, meaning that at every point during execution the user has an action choice that is compatible with all possible future occurrences of the sporadic activity, precisely as dynamic controllability requires. To find such valid decisions, the algorithm finds intersections over the availability intervals for the activity at each decision point. (Since this is an STP, only one activity is available at any decision point.) To ensure that this intersection exists at each node, and that earlier decisions cannot lead to detrimental downstream effects, our algorithm performs a forward and backward traversal of the DPTree at the beginning of execution. The forward pass restricts the availability intervals for the activity offered at each decision point such that the lower bound of this interval falls within the intersection of the intervals of availability in valid iSTPs. It propagates the effect of this constraint tightening, and continues moving down the DPTree, fixing the lower bounds of these intervals. The backward pass restricts the availability intervals so that the upper bound of an interval falls within the intersection at each decision point. After these traversals, if each activity has a valid interval of availability (lower bound does not exceed upper bound), then the DU-STP is dynamically controllable. The DPTree is returned along with the DU-STP so that these restricted intervals of availability can be used during execution to maintain dynamic controllability. While this DC-Checking algorithm can be slow (as our empirical results will show), with it the scheduling assistant achieves flexibility and dynamic controllability, only offering choices at a decision point that are compatible with any future sporadic activity occurrence. To evaluate the new strategy, based on our DC-Checking algorithm, for offering choices to the user, and to compare it with alternative strategies, we generated artificial scheduling problems (DUTPs) for 600-min days divided into 60 10-min slots. Each problem has 10 regular (controllable) activities, with random temporal ordering constraints between them, and a single 20-min (2-slot) sporadic activity. Given that slack in a schedule matters, we experimented with cases where the 10 activities’ durations filled (summed to) 58, 56, 54, 50, and 48 slots. We randomized the simulated behavior of the user, and the timing of the sporadic activity (where 20% of the time it never happened). We experimented with 5 strategies. They are:
Figure 10 shows the measured probability that all the activities complete within constraints, where DC is perfect as expected. DC-A would be expected to perform well at high fill levels, where activities’ executions must abut each other, and indeed it does, but we were pleasantly surprised that it also empirically performs well even as slack increases. mDTF and mACF perform the worst because they fail to account at all for the sporadic activity, but as fill level decreases they are more likely to get lucky: with more inherent slack, the chances of absorbing the sporadic activity inherently rise. Packing does well because it retains as much slack as possible, but can sometimes be too aggressive: sometimes, it is better to hold off on starting an activity that is available now but has a wide window for performance, and wait a little while to get started promptly on an activity that has less margin for error. That is, if you start the immediately-available activity, and the sporadic activity happens during it, there might not be enough time left after the sporadic activity to then finish the more constrained activity by its deadline. DC’s robustness comes at a computational cost, measured in terms of the number of calls to the underlying constraint solver, orders of magnitude higher than the other strategies (Fig. 11, note the logarithmic scale). By only selectively placing the sporadic activity, DC-A’s computation is not much higher than mDTF and mACF, and Packing is lowest because it unthinkingly just offers whatever activities are immediately available. The normalized DTF generally increases as fill decreases (Fig. 12). For fill = 58, the only discretionary time freedom with the DC, DC-A, and Packing strategies is at the end of the day if the sporadic activity does not occur. As slack increases, DC and DC-A offer as much discretionary time as possible while still withholding enough slack to absorb the sporadic activity at any future time, while Packing offers as little as possible. While the mDTF dispatcher as expected rides along the upper bound on this metric, mACF comes close to this upper bound as well, because it is only rarely the case that choices disappear if the user waits too long. In essence, choices disappearing requires that there be multiple windows to do the activity: that the current window for starting it closes but (since it must be scheduled) another will open later. Most of the modeled activities in our generated problems, though, have a single contiguous window for execution. Regarding activity choice freedom (Fig. 13), again as expected the (in this case mACF) strategy that purposely maximizes this metric does the best. However, in our experiments, all of the strategies did very well (note the scale of the zoomed-in y-axis). Most of the user’s freedom in activity choice is invariant to the strategy because it is due to the structure of the scheduling problem (e.g., the degree to which activities are strictly ordered). Around the margins, the strategies can make a small difference by offering the user either too much discretionary time (to a point beyond the starting window of some activities that could have been done) or too little (to a point before the starting window of some activities that could be offered). Unsurprisingly, no strategy dominates across all the metrics. To be as safe as possible, the DC strategy is the only option that formally guarantees being able to handle sporadic activities under all circumstances. But our empirical results suggest the DC-A(pproximation) strategy can in practice be a better choice, being comparable to DC in performance while being much faster. Unsurprisingly, though, we have been able to contrive problem situations where DC-A fails to succeed when DC can, so DC-A presents some risk. Hence, we ultimately believe a variation of the DC approach that builds on insights from DC-A would be a promising direction to explore. Unlike DC-A which restricts the placement of the sporadic activity to gain computational efficiency, the variation of DC we foresee would instead restrict the orderings of activities, and explore the space of DU-STPs incrementally. At any given time (if a full exploration is too time consuming), it could return whatever choices it has uncovered. It is possible that, had it been given more time, an uninvestigated DU-STP might have revealed an additional activity choice, or more discretionary time, that could have been offered. This variation would thus be sound (only return choices that ensure handling a sporadic activity) but incomplete (not necessarily return all such choices). For a faster system, a user might be willing to sacrifice some amount of freedom without risking failure. In the first half of this paper, we gave an accounting of the motivations, technological foundations, and novel engineering ideas in the development and prototyping of a schedule management assistant especially geared to help adolescents with disabilities (and their families) navigate the transition to independent adulthood. We summarized the guidance we received from the community in our efforts, and the reactions of the community to our prototype to date. We then concluded this paper with a deeper technical exposition on a facet of the system that demanded that we contribute a new formalization of a temporal problem where when, if ever, an activity happens is uncontrollable by the user, and we contribute new algorithmic techniques for solving such problems. We empirically showed that our algorithm works (100% success rate) and that it allows as much freedom as is safely possible. We also identified (incremental) approximation techniques that might represent a good practical balance between performance and speed. As was mentioned in Section 6, while our prototype’s user interface has continued to undergo improvements, it arguably still tries to convey too much information (in a form of Gantt chart) for our anticipated user community. In our future work, we are considering simpler (though less precise) graphics to provide feedback about consequences of tentative choices, and to gather specifications of added/modified activities, with options for “power” users to delve into the richer set of features. Our future work also includes developing speculative and approximate computational strategies for scaling up our system to more agents and harder problems, as summarized at the end of Sections 7 and 12. We are also planning a final round of evaluations on our prototype, with the objective of attracting commercial developers of deployed schedule management products (like those described in Section 3) to adopt components of our system (which will be open source) into improving their products, in the hopes that those products will serve our target community better. Thanks to our collaborators (Dr. Ned Kirsch, Dr. Jason Sleight, Donna Omichinski, Drew Davis, Jordan McKay, and Drew Canada). This work has been supported, in part, by the by the US HHS under NIDILRR grant 90RE5012. The opinions and views expressed in this document do not necessarily reflect those of NIDILRR. Conflict of interests On behalf of all authors, the corresponding author states that there is no conflict of interest. 1If on a particular day the activity’s time needs fall outside this range, or it needs to start sooner or end later than usual, then as will be explained shortly the user can “Modify” the activity in the midst of the day. 2Improving this part of the interface to strike the right balance between informing and not overwhelming the user is an area of future research (Section 13). 3In our prototype, we “fast forward” to the end of the chosen activity in simulation by tapping the UI area labeled “Advance system time to next decision point.” 4In our user interface (Section 6), this is the upper bound on the “other” activity’s time. Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 1. AbleLink: Endeavor 3. https://www.ablelinktech.com/index.php?id=29 2. Barbulescu L, Rubinstein ZB, Smith SF, Zimmerman T (2010) Distributed coordination of mobile agent teams: the advantage of planning ahead. In: Proceedings of the 9th international conference on autonomous agents and multiagent systems, pp 1331–1338 3. Boerkoel JJr, Durfee EH. Distributed reasoning for multiagent simple temporal problems. J Artif Intell Resh (JAIR) 2013;47:95–156. doi: 10.1613/jair.3840. [CrossRef] [Google Scholar] 4. Boerkoel JCJr. Distributed approaches for solving constraint-based multiagent scheduling problems. Ph.D. thesis: University of Michigan; 2012. [Google Scholar] 5. Boerkoel JC Jr, Durfee EH (2012) A distributed approach to summarizing spaces of multiagent schedules. In: Association for the advancement of artificial intelligence, pp 1742–1748 6. Boerkoel J Jr, Durfee EH (2013) Decoupling the multiagent disjunctive temporal problem. In: Proceedings of the 2013 international conference on autonomous agents and multi-agent systems, pp 1145–1146 7. Boerkoel J Jr, Planken L, Wilcox R, Shah JA (2013) Distributed algorithms for incrementally maintaining multiagent simple temporal networks. In: International conference on automated planning and scheduling, pp 11–19 8. Brooks J, Reed E, Gruver A, Boerkoel JC (2015) Robustness in probabilistic temporal planning. In: AAAI, pp 3239–3246 9. Capterra: scheduling software buyers guide. https://www.capterra.com/scheduling-software/ 10. Conrad PR, Williams BC (2011) Drake: an efficient executive for temporal plans with choice. J Artif Intell Res, 607–659 11. Cozi: https://www.cozi.com/ 12. Dechter R, Meiri I, Pearl J. Temporal constraint networks. Artif Intell. 1991;49(1):61–95. doi: 10.1016/0004-3702(91)90006-6. [CrossRef] [Google Scholar] 13. Durfee EH, Boerkoel JC, Sleight J. Using hybrid scheduling for the semi-autonomous formation of expert teams. Futur Gener Comput Syst. 2014;31:200–212. doi: 10.1016/j.future.2013.04.008. [CrossRef] [Google Scholar] 14. Evernote: https://evernote.com 15. Gomes CP. On the intersection of AI and OR. Knowl Eng Rev. 2001;16(01):1–4. doi: 10.1017/S0269888901000066. [CrossRef] [Google Scholar] 16. Goodin RE, Rice JM, Parpo A, Eriksson L (2008) Discretionary time: a new measure of freedom. Cambridge University Press 17. Google: Calendar. https://www.google.com/calendar 18. Hunsberger L. Algorithms for a temporal decoupling problem in multi-agent planning. AAAI/IAAI. 2002;2002:468–475. [Google Scholar] 19. Hunsberger L (2003) Distributing the control of a temporal network among multiple agents. In: Proceedings of the second international joint conference on autonomous agents and multiagent systems, pp 899–906 20. Hunsberger L (2009) Fixing the semantics for dynamic controllability and providing a more practical characterization of dynamic execution strategies. In: 16th International symposium on temporal representation and reasoning (TIME 2009). IEEE, pp 155–162 21. Laborie P. Algorithms for propagating resource constraints in AI planning and scheduling: existing approaches and new results. Artif Intell. 2003;143(2):151–188. doi: 10.1016/S0004-3702(02)00362-4. [CrossRef] [Google Scholar] 22. Lau HC, Li J, Yap RH (2006) Robust controllability of temporal constraint networks under uncertainty. In: 18th IEEE International conference on tools with artificial intelligence (ICTAI’06). IEEE, pp 288–296 23. Lennon J, Klages K, Amaro C, Murray C, Holmbeck G. Longitudinal study of neuropsychological functioning and internalizing symptoms in youth with spina bifida: social competence as a mediator. Pediatric Psychol. 2015;40(3):336–348. doi: 10.1093/jpepsy/jsu075. [PMC free article] [PubMed] [CrossRef] [Google Scholar] 24. Microsoft: Outlook. https://outlook.live.com/owa/ 25. Morris PH, Muscettola N (2005) Temporal dynamic controllability revisited. In: AAAI, pp 1193– 1198 26. Nelson B, Kumar TS (2008) Circuittsat: a solver for large instances of the disjunctive temporal problem. In: ICAPS, pp 232–239 27. Oddi A, Rasconi R, Cesta A (2010) Casting project scheduling with time windows as a DTP. In: Proceedings of the ICAPS workshop on constraint satisfaction techniques for planning and scheduling problems (COPLAS 2010), pp 42–49 28. Peintner B, Venable KB, Yorke-Smith N (2007) Strong controllability of disjunctive temporal problems with uncertainty. In: Principles and practice of constraint programming–CP 2007. Springer, pp 856–863 29. Planken L, De Weerdt M, Van der Krogt R (2008) P3C: a new algorithm for the simple temporal problem. In: Proceedings of the eighteenth international conference on automated planning and scheduling (ICAPS 2008), pp 256–263 30. Planken L, de Weerdt M, Yorke-Smith N (2010) Incrementally solving STNs by enforcing partial path consistency. In: ICAPS, pp 129–136 31. Shah JA, Stedl J, Williams BC, Robertson P (2007) A fast incremental algorithm for maintaining dispatchability of partially controllable plans. In: ICAPS, pp 296–303 32. Shah JA, Williams BC (2008) Fast dynamic scheduling of disjunctive temporal constraint networks through incremental compilation. In: ICAPS, pp 322–329 33. SmartDay: http://mysmartday.com/ 34. Smith SF, Gallagher A, Zimmerman T (2007) Distributed management of flexible time schedules. In: Proceedings of the 6th international joint conference on autonomous agents and multiagent systems (AAMAS07), pp 472–479 35. Tarazi R, Zabel T, Mahone E. Age-related differences in executive function among children with spina bifida/hydrocephalus based on parent behavior ratings. Clin Neuropsychol. 2008;22(4):585–602. doi: 10.1080/13854040701425940. [PMC free article] [PubMed] [CrossRef] [Google Scholar] 36. TickTick: https://ticktick.com 37. Tsamardinos I. Constraint-based temporal reasoning algorithms with applications to planning. Ph.D. thesis: University of Pittsburgh; 2001. [Google Scholar] 38. Tsamardinos I, Pollack ME. Efficient solution techniques for disjunctive temporal reasoning problems. Artif Intell. 2003;151(1):43–89. doi: 10.1016/S0004-3702(03)00113-9. [CrossRef] [Google Scholar] 39. Tsamardinos I, Vidal T, Pollack ME. CTP: a new constraint-based formalism for conditional, temporal planning. Constraints. 2003;8(4):365–388. doi: 10.1023/A:1025894003623. [CrossRef] [Google Scholar] 40. Venable KB, Yorke-Smith N (2005) Disjunctive temporal planning with uncertainty. In: International joint conference on artificial intelligence, pp 1721–1722 41. Vidal T. Handling contingency in temporal constraint networks: from consistency to controllabilities. J Exper Theor Artif Intell. 1999;11(1):23–45. doi: 10.1080/095281399146607. [CrossRef] [Google Scholar] 42. Vidal T, Fargier H. Handling contingency in temporal constraint networks: from consistency to controllabilities. J Exper Theor Artif Intell. 1999;11:23–45. doi: 10.1080/095281399146607. [CrossRef] [Google Scholar] 43. Warschausky S, Kaufman JN, Evitts M, Schutt W, Hurvitz EA. Mastery motivation and executive functions as predictors of adaptive behavior in adolescents and young adults with cerebral palsy or myelomeningocele. Rehabil Psychol. 2017;62(3):258–267. doi: 10.1037/rep0000151. [PubMed] [CrossRef] [Google Scholar] 44. Warschausky S, Kaufman JN, Schutt W, Evitts M, Hurvitz EA. Health self-management, transition readiness and adaptive behavior in persons with cerebral palsy or myelomeningocele. Rehabil Psychol. 2017;62(3):268–275. doi: 10.1037/rep0000157. [PubMed] [CrossRef] [Google Scholar] 45. Wikipedia: Comparison of xml editors. https://en.wikipedia.org/wiki/Comparison_of_XML_editors 46. Wilson M, Klos T, Witteveen C, Huisman B (2013) Flexibility and decoupling in the simple temporal problem. In: BNAIC 2013: proceedings of the 25th benelux conference on artificial intelligence, Delft 47. Xu L, Choueiry BY (2003) A new efficient algorithm for solving the simple temporal problem. In: Proceedings of the tenth international symposium on temporal representation and reasoning, and fourth international conference on temporal logic (TIME-ICTL 03), pp 212–222 48. Zabel T, Jacobson LA, Zachik C, Levey E, Kinsman S, Mahone E. Parent- and self-ratings of executive functions in adolescents and young adults with spina bifida. Clin Neuropsychol. 2011;25(6):926–941. doi: 10.1080/13854046.2011.586002. [PubMed] [CrossRef] [Google Scholar] |
The project schedule is originally designed without concern for resource. how do resource constraints affect this schedule? they can only extend it. all the above resource constraints increase float (slack) times resource constraints do not affect the sche
Postagens relacionadas
direito autoral © 2024 cemle Inc.
