Human-Centered Planning

Given a set of activities/tasks that the user wants to accomplish during the day, the goal of the planner is to generate an agenda that takes into account constraints and avoids conflicts. In practice, tasks come from three categories:

• •

  Pre-scheduled are events already scheduled for the day on one’s calendar (e.g., work meetings and appointments).

• •

  Habits are things that the user performs daily, such as eating meals and getting exercise.

• •

  ToDos are tasks that the user wants to accomplish for the day, such as reading a book, mowing the lawn, etc.

Ideally, the events that are fed to the planner for a given day should be automatically populated from the tools that the person is already using, such as their calendar or a todo list tool. The habits can be inferred from the user’s past activities when those are available.

Formally, an input event to the planner, $e$, is a tuple of the form $(d,L)$ where $d$ is the event description (e.g., “breakfast”) and $L=\{l_{1},\dots,l_{m}\}$ is the list of constraints that the planner needs to satisfy. The output of the planner is an agenda consisting of a sequence of $m$ calendar events $\{c_{1},\dots,c_{m}\}$ where each $c_{i}$ is a triplet $(e,\mathsf{start},\mathsf{end})$ where $e\in E$ and $\mathsf{start}/\mathsf{end}$ are the start/end time of the event $e$.

We consider three types of constraints (see Table 1 for examples):

• •

  Absolute temporal constraints: These constrain the absolute start and end times of events and take the following form: $\{\mathsf{``starts\ at"},\mathsf{``ends\ at"},\mathsf{``before"},\mathsf{``after"}\}$ + time (e.g., “9am”).

• •

  Duration constraints: These constrain only the duration of an event and are of the form: $\{``<",``>"\}$ + duration (e.g., “1 hr”).

• •

  Relative temporal constraints: These constrain the relative ordering of pairs of events and take the form: $\{\mathsf{``before"},\mathsf{``after"}\}$ + event.

Next, we describe each of the planners we built and their hybrid variants.

The key idea underlying $\mathsf{LLMPlan}$ is to leverage LLM’s commonsense reasoning capabilities and its ability to create structured results (in our case, plans). In $\mathsf{LLMPlan}$, we leverage LLMs for day planning via in-context learning IV et al. (2022). Specifically, we construct a prompt designed to enable the LLM to generate correct plans. The prompt consists of 3 components: (1) a task description describing the high-level goal of the task, (2) the list of input events and constraints formatted in text, and (3) a 1-shot example of a plan. The details of the prompt are shown in Figure 5 in the Appendix. Note that additional processing steps are necessary to correctly extract the event name and start/end time from the LLM’s output.

There are two points worth noting here. First, a traditional symbolic planner requires all the constraints as input. One of the benefits of using LLMs for planning is that the user does not need to specify all the constraints and some can be inferred from the commonsense knowledge in the LLM (e.g., appropriate times and lengths for meals or other activities). Second, we expect that the interaction with the planner may involve several iterations, where the user refines their needs as they go along. Here too, the $\mathsf{LLMPlan}$ will offer the benefit that it can understand user needs that are stated more vaguely in natural language, such as “I want frequent breaks in the afternoon”.

We contrast the LLM-based approach to planning with a symbolic planner, $\mathsf{SymPlan}$. Given the set of events $E$ and constraints $L_{e}$ for each $e\in E$, $\mathsf{SymPlan}$ computes the start and end times ($\mathsf{start}_{e}$ and $\mathsf{end}_{e}$) of the events. Since there can be multiple plans that satisfy all the constraints, $\mathsf{SymPlan}$ chooses between them by solving an optimization problem that minimizes the total length of the schedule. Specifically, $\mathsf{SymPlan}$ finds $\min\{\max_{e\in E}\mathsf{end}_{e}\}$ s.t., $l_{e,i}$ holds $\forall l_{e,i}\in L_{e},\forall e\in E$.

Users don’t always provide a consistent set of constraints. Hence, $\mathsf{SymPlan}$ begins by employing a constraint checking and relaxation step. It begins by encoding the events as nodes and temporal constraints as edges into the distance graph representation of a simple temporal network (STN) Dechter et al. (1991) (see Figure 2). The STN allows us to obtain upper and lower bound times for scheduling each node by running shortest path algorithms on it. If we do not get valid bounds for an event, we use a procedure similar to Oei (2009) to detect conflicting edges and either relax them or drop them completely if they cannot be relaxed.

Having obtained valid time bounds for scheduling each node and having asserted feasibility, we plan using a backtracking search which implicitly enforces a non-overlap between events in time. The search algorithm uses: (a) our distance graph representation for constraint propagation, and (b) slack-based heuristics to choose events which have a tighter remaining scheduling window earlier during the search. Upon completion of the search, we return the best full (or partial) solution found till then. For more details, see Appendix C.

Specifically, after receiving an output plan from the LLM, we run a set of constraint checkers that identify a few kinds of violations: (1) unsatisfied input constraints, (2) missing events, and (3) overlapping events. We then verbalize the list of violations into textual feedback such as “the duration of A is too long/short”, “A should not overlap with B”, etc., and feed them as input to the LLM to re-generate the plan. We repeat this process for a fixed number of iterations or until there is no violation detected. Among all the iterations, we select the plan with the minimal number of violations as the final output. Details of the self-reflection prompt are in Figure 6 of the appendix.

Table 2 shows statistics of the 2 datasets and Table 3 shows example events and constraints. To the best of our knowledge, these are the first available benchmarks for day planning.

Due to the complex and subjective nature of the task, there is no single metric for evaluating the quality of a plan. Instead, we consider a set of metrics that provide a more comprehensive view of the behavior of the planner.

• •

  Event Coverage (CO): percentage of input events included in the plan,

• •

  Non-Overlap (NO): percentage of planned events that don’t overlap with others, and

• •

  Percentage of Duration constraints (DC), Order Constraints (OC), Start/End constraints (SEC) that are correctly satisfied.

Note that these constraints are not hard constraints that the planners must satisfy. For example, the planner may decide to schedule a language class in the evening which is uncommon but may still be acceptable. Achieving a low commonsense violation score indicates that the planner is capable of capturing human behavioral patterns, even when they are not explicitly specified in the input. For this set of metrics, we expect the LLM-based or the hybrid approach to outperform the symbolic planners that do not take event semantics into account.

We implemented $\mathsf{LLMPlan}$ using Langchain¹¹1https://langchain.readthedocs.io/en/latest/ and OpenAI’s LLM APIs²²2https://openai.com/api/. For the LLM-based planner, we evaluate various LLMs to understand what techniques enable the planning capabilities:

• •

  GPT-3: Transformer-based LLM pre-trained on web and general text data Brown et al. (2020). We evaluate the base model curie of 6.7B parameters and davinci model of 175B parameters.

• •

  InstructGPT / GPT-3.5 Ouyang et al. (2022): These models are instruction-tuned to enable better following of human instructions. We test the text-davinci-002 model based on supervised fine-tuning and text-davinci-003 based on reinforcement learning, both with 175B parameters.

• •

  ChatGPT OpenAI (2022): The well-known chat version of GPT-3.5 optimized for dialog. We use the gpt-3.5-turbo checkpoint in our experiment.

• •

  GPT-4 OpenAI (2023): The most recent OpenAI LLM known for its significantly improved capabilities on problem solving and handling complex instructions versus GPT-3.5 (but whose size is unknown).

For LLM-based planning, model size and instruction tuning are critical for planning. As seen in Tables 4 and 5, the GPT-3.5 models outperform GPT-3 on both correctness and commonsense understanding by large margins, e.g., by over 40% average correctness score or 5% to 10% commonsense scores on both benchmarks. Overall, the recent large and instruction-tuned LLMs outperform their counterparts.

We manually inspected the plans for errors made by the planners. For $\mathsf{LLMPlan}$, the most common errors were (1) to hallucinate events that were not in the input (e.g., add “free time” at various points in the day) and (2) to slightly rename events (e.g., rename “take marketing class” to “Take a marketing class”) or combine multiple events into one. The renaming of events is not a strict error, and even the combination of events often made sense and satisfied the timing constraints. $\mathsf{SymPlan}$, on the other hand, sometimes returned plans that were not very natural, such as putting a meal at a completely wrong time (when appropriate constraints were not given). We show in Figure 4 and Figure 3 examples of typical behaviors of the planners.

Our experiments so far focus on evaluating plans objectively, without any user feedback. To better understand the utility of $\mathsf{LLMPlan}$ and $\mathsf{SymPlan}$, we conduct a user study where users can refine their plan by iteratively providing feedback to the planner. In doing so, we also obtain insights into the kinds of constraints and events that users specify to a day planner. For example, after observing an initial plan, the user may want to re-plan with requests in natural language such as “can you move event X to the afternoon?”. Sometimes the requests can be more complicated, such as “I want frequent breaks in the afternoon”.

To support this experiment, we enhanced both planners with additional features for incorporating user feedback. For $\mathsf{LLMPlan}$ this merely involved putting it behind a chatbot interface. The chatbot receives messages from the user and appends them as additional input to the LLM to update the plan (see Figure 5 for the prompting detail).

For $\mathsf{SymPlan+}$, we developed an extractor, that given a user statement such as “lunch should start at noon and be at least 30 minutes”, would try to identify constraints that can be added to the planner’s input, for example,

‘‘lunch: starts at 12:00, >30 minutes’’

to update the original input to $\mathsf{SymPlan+}$. Note that the interactive capability of this approach is limited by the expressive power of the current constraint language and the extractor.

An interesting discovery from the user study is the types of requirements that users provide to the planner. We collected 113 user requirements in total. We organize them into 3 heuristically derived categories (see Table 6 for some examples and stats):

• •

  Well-defined: (52.2%) these are human instructions with clearly defined semantics of action, such as add/change/remove events or constraints.

• •

  Complex: (12.4%) these are messages with clear semantics but requiring the planner to execute complex steps, which are beyond the capabilities of current natural language understanding (NLU) approaches.

• •

  Open-ended: (35.4%) these are messages that are ambiguous requiring additional human context to execute correctly. NLU alone will not be sufficient.

In Table 8, we measure how well the planners can correctly handle each category of messages. We found that $\mathsf{LLMPlan}$ significantly outperforms $\mathsf{SymPlan}$ on handling the open-ended messages (72.5% vs. 45% positive rate), while the complex messages remain the most difficult type with no more than 50% positive rate for both planners.