Taking Me to Task: Spatially and Temporally Aware Task Management
Advisor: David Liben-Nowell
Background
This week—really! the very week that I wrote this project
description—my To Do list contained a collection of
tasks/meetings with a variety of nontrivial (and, to a computer
scientist like me, interesting) constraints. Some examples of the
kinds of constraints include:
- some precedence constraints on tasks (I must read the
applications for Carleton's Digital Humanities postdoc position
before I can decide on my rankings of the DH postdoc
applicants).
- some release conditions on tasks that rely on others' actions (I
cannot read the paper that Julia emails me until Julia emails me
the paper).
- some release conditions on tasks that rely on timing (I
cannot look over CS 202 ps05 submissions until the due date
(8:30am Friday) for ps05).
- some deadlines for tasks (I must write description of comps
project before I attend the CS department meeting (1:15pm
Thursday) where we will discuss comps project proposals).
Also, many of my tasks have associated data that informs when I can,
or prefer, to do them:
- many tasks have fixed locations (I can only go to the faculty
meeting in Boliou 103, because that's where it is).
- many tasks have fixed times (I can only go to the faculty
meeting at 4:30pm Monday, because that's when it is).
- many tasks have (estimated) durations (I can only write
description of comps project in a ≈2-hour period, because
that's how long I estimate it will take me to write it; I prefer for
this time to be uninterrupted).
And sometimes these constraints intersect in complicated ways. I
recently had, for example, one day in which my To Do List contained
all of the following:
- hold office hours (Weitz 225C, 1:00–2:00p).
- drop off dry cleaning (Dufour's Cleaners, closes at 6:30p).
- return a shirt I ordered online that turned out to be ugly (any of about nine Macy's locations in the Twin Cities, hours vary by location).
- buy curling gloves (any of about eight Sports Authority locations in the Twin Cities, hours vary by location, must be done before Task 7).
- get an oil change (Walser Nissan, estimated duration 30 minutes (I can do other things during those 30 minutes); closes at 8:00pm).
- write a recommendation letter (estimated duration 60 minutes),
write an exam (estimated duration 200 minutes, interruptions
okay), and do some work on my book (arbitrary amount of time).
[Acceptable locations: Weitz 225C, Walser Nissan, any of ≈100 Twin Cities Caribous.] - play in a curling match (Fogerty Arena, 7:45pm–11:00pm).
The Project
In this project, you will build a system for task management that can
support tasks with the above kinds of complications. Your system will
allow users to add new tasks (perhaps with associated data related to
time, space, or precedence); mark tasks as complete; and propose a
planned schedule for task completion for the user. You will tackle a
variety of types of issues in your work:
- Algorithms: even without worrying about all of these types
of complications, some of the simplest problems that your system will
have to handle
include Subset
Sum–like problems (given a set of tasks with durations,
which should be scheduled in a k-minute block of time?) and
Traveling
Salesman–like problems (given a set of locations that must
all be visited, in what order should they be visited to minimize total
travel time?).
- Infrastructure: how will you organize the database that
stores tasks? What kind of third-party data sources will you interact
with: Google Maps? Gmail (so that tasks can be added when someone
emails me)? Android/iPhone (a mobile version of the system)? the Web
(to make best guesses about when stores are open, e.g.)?
While this project will have some user interface components, that
will not be the emphasis of your team. You'll have to make a
serviceable interface, but your top priorities will be algorithmic.
The outline of the project's task will to (1) investigate existing
task-management systems; (2) investigate the literature for existing
approaches to the type of algorithmic challenges that you'll face; (3)
design an interface and a backend to handle these types of requests;
(4) build it; and (5) test it (with actual users).