Scheduling Algorithms and “Crip Time”

One of Mobi.AI’s travel planning products generates trip itineraries for travelers. Something we do when we design itinerary-generating algorithms is ask “how do we want to model time?” For example, there are certain activities that you think of as having rigid start and end times (like seeing a movie in a theater), and other activities that you probably think of as “taking” a certain amount of time (like, taking 15 minutes to taxi from point A to B). Additionally, some activities must happen concurrently, in a series, overlapped, or contained within other activities! As humans, we can schedule something into our day and naturally take our context and personal approach towards time into account. Computers don’t intuit this information though. This means Mobi’s computer programmers and product designers can’t take our cultural and social ideas about time as a given: we have to think about modelling different aspects of “time” explicitly in code.

What should we consider when we model time? The ways that people experience and engage with time differ across individuals and cultures. Some examples, like the ones mentioned above, are conceptual ways of thinking about time. How do different people experience or organize the same duration of time? Other variations are more socially constructed. How do we estimate how long an activity will take? What activities or events are appropriate at different times of days? Or at different times in your life? What activities require precision, and how does your awareness of time convey respect? The study of how time is socially constructed is called Chronemics. Originally coming out of studies in non-verbal communication, chronemics is a field at the intersection of anthropology, philosophy, and linguistics. Thinking about chronemics (directly, or more often, passively) during a design process helps to make more human-feeling schedules… while not thinking about this can make software fail on edge cases or make the user experience clunky!

The Encyclopedia of Special Education talks about Chronemics as, "including time orientation, understanding and organization <of time>, the use of and reaction to time pressures, the innate and learned awareness of time, by physically wearing or not wearing a watch, arriving, starting, and ending late or on time.”

A particularly vivid example of how chronemics is important is when planning for traveling with a disability. When Mobi works with disabled travelers, Mobi pulls inspiration from “Crip Time”: an academic concept that describes the relationship that disabled people and communities have to timeliness (especially punctuality), schedules, and coordination. The concept of “Crip Time” is recognized academically as a subfield of chronemics, but the term and conceptual development originated in disabled communities. It continues to primarily be used, discussed, and developed by these communities today. In the essay “Six Ways of Looking at Crip Time” by Ellen Samuels, the author describes the cultural significance of “Crip Time” and the way that normative cultures around time can cause friction with the disabled. One facet of this is the need to be hyper-scheduled (in order to be accommodated in the first place: like requesting a special car) and also to need the grace and flexibility of moving plans around when you are inevitably late or exhausted.

Though creatively building slack and flexibility into itineraries or emphasizing hard deadline requirements are by no means a perfect translation of these concepts, this is technical functionality that can be supported by our current travel planner tool and user interface (UI, or the way user interacts with the product). We believe that by talking with disabled travelers about their scheduling needs and by pulling concepts from “Crip Time”, Mobi can generate itineraries that are more useful to everyone. The schedules we generate are more realistic when informed by the habits users already have around time management in trip planning contexts.

Let’s go into more technical depth and show how we apply this design approach. First, we’re going to look at applying foundational chronemics concepts. We’ll follow abstract temporal (relating to time) concepts as we turn them into computational ideas. After that, we apply the computational ideas to travel problems. We’ll then get more specific; doing the same process for ideas pulled from Crip Time.

What are some common temporal ideas that we as humans use when we reason about and produce schedules? Often, we think of activities in a schedule as having a start, end, and duration. Certain activities are exclusive: you can only be doing that activity at that time. Activities also have relationships to each other: sometimes one must happen before another. Certain activities are routines and need to happen regularly (like eating or sleeping) and other activities might be best done at certain times of day (errands can only be done while the stores are open). These fairly universal ways of engaging with time are the blueprints for encoding what could happen in software. This allows us to then use algorithms to determine the feasibility of scheduling activities together to build itineraries.

The scheduling portion of Mobi’s planner is based on something called a Controllable Conditional Temporal Problem (or CCTP, formulated in this paper by one of Mobi’s founders Peng Yu and Mobi’s Chief Scientist and MIT professor Brian Williams). This allows us to relate different activity start and end times to each other by a lower bound and upper bound time duration. Computationally, this creates a specific version of a data structure called a directional graph. In addition to “start” and “end” nodes, CCTPs additionally have “choice nodes” which indicate points in the schedule in which one set of activities must be selected at the exclusion of the others. Together, activity start nodes, activity end nodes, and activity choice nodes represent all the hypothetical schedules that can happen. To generate one schedule, we choose a path for each choice node, and then find at least one feasible schedule for the selected activities using the common algorithm APSP. This type of scheduling allows for the coordination of multiple people or resources and closely follows how a person might organize their time around task completion without the aid of a computer.

So how would this work if we were planning a trip? Well, first we construct a “typical” day template that specifies reasonable start and end times for meals, activities, and sleep in this location. This is made by understanding the typical “routine” of travel in this city and the type of trip you’re going on. For example, if you’re going to Barcelona for a bachelorette party, you might expect to be sleeping from 6AM-11AM, and taking a 3-5PM siesta, eating meals later (or not eating breakfast at all) and having an activity after dinner. If you’re going to Boston on a vacation with your kids, your day template would probably look different. You’d be sleeping from 11PM-7AM, eating meals early, and planning an activity for both the morning and afternoon. This differs from making a schedule using, for example, rigid time slots by instead giving a general reference for when certain types of activities should occur so that we can route and plan for a specific location.

If we’re designing a trip, we don’t just organize all of your pre-selected activities; we also want to help you choose activities. Each decision about a restaurant, activity, or accommodation is represented as a “choice” node when we model it using code. Each of these choice nodes lets us choose a different path (leading to the next choice node or to the end of the itinerary). Each path contains a placeholder for routing information and at least one POI (Point of Interest: a term we use to refer to any location in your trip whether it’s a restaurant, activity, event or hotel). The start and end point of each POI are related by the range of time people usually spend at that location based on our data. We also constrain the “start” and “end” time by the hours during which an attraction is open and relate the start and end points to the slots in the trip template (so you might, for example, connect a path containing a restaurant to the start and end of the meal in the template-graph). For example, if you’re in Barcelona, we would have a “restaurant” choice node connected to the “lunch” start time and which then connects to multiple food options. When this graph has been constructed, we can run a “solver” algorithm on it to make choices about what activities and restaurants you want to go to, fill in routing data, check to see if the trip is schedulable, and then generate an itinerary very quickly. So if your morning activity is really short, the flexible lunch range and choice node might let us recommend an early lunch at a more traditional Barcelona restaurant known for its long and large meals (that is close to your hotel so you can take a siesta afterwards!).

How well does this planner generate itineraries that meet the needs of the disability community? This question is complex because differently-abled people are incredibly diverse and have varying needs. When we ask ourselves “what functionality should a trip planner have to be useful to disabled travelers?” we pull, in part, from discourse and theory from “Crip Time.” On hourly or daily timescales, “Crip Time” often talks about tensions around punctuality; often, despite planning extra time for a deadline or appointment, disabled people find themselves arriving late because of their disability. Other times, arriving early or being blocked at a certain task can result in large stretches of waiting. This is, of course, in tension with receiving accommodations which often require punctuality. For example, wheelchair accommodations at the airport may require that a handicapped person ride in a specific vehicle or meet an airport attendant at a specific time. Differently-abled people, not just people with mobility impairments, also have varying transit or movement times. This extends to tasks more broadly: as we mentioned earlier, without realizing it, we have preconceived notions of how long a given task should take (and are more opposed to accommodating when it takes shorter or longer than we realize). Of course, all of this intersects with cultural time constructs as well; for example a mobility impaired person in Spain may have extra difficulty returning to their hotel to take advantage of the siesta hours that we mentioned earlier, especially if they’re not used to it or thinking about it beforehand.

How do we incorporate these ideas into the design specifications of our planner? By minimally modifying the initialization of the previous design, we can more firmly anchor specific activity starts or ends to rigid timestamps. This modification allows for plans to be generated around required, steadfast tasks: if a user must eat at a certain time to control their blood sugar, if a user needs a sign language interpreter for a tour that is only available at a specific time, or they might need to catch a very specific shuttle, this can be selected in a UI and then incorporated into the description of “potential plans.” Imagine a tool that allows you to specify “returning to a hotel from 3-3:30PM” in the middle of the afternoon to take a refrigerated medication, and then having a scheduler that optimizes your day to see the sites without risking your health. When we generate the schedule, the itinerary should mold itself around this constraint without making it the main focus of the trip.

Not everyone wants or needs itineraries with this amount of intention or computational rigor. Some people don’t care to do any kind of planning before they go on a vacation, or they go somewhere with a handful of places in mind and improvise the transportation and daily schedule. Mobi is aware of this, and therefore thinking very intentionally about getting our technology to everyone who would benefit from it. Disabled travelers often receive more benefit from thoughtfully scheduling portions of their trip than the average traveler (especially if activity or hotel recommendations come from a database enriched with data relevant to disabled travelers). This is why we’re looking at how our planner can be used to assist in planning travel for disabled people. This already looks like consulting disabled travelers directly. It could also look like working with travel agencies serving disabled clients (with our Agent product, we can make template trips for different cities, and then re-plan each trip to fit the specific needs and accommodations of each traveler). It could also look like helping groups of disabled travelers coordinate their trips together; for example we could help disabled athletes better plan and coordinate their competition travel for something like the Paralympic Games. At Mobi.AI we’re always looking for new, impactful ways to apply our technology—reach out to us if you have your own idea for how our human-centered planning engine could empower you or your customers.