Homework 4: Creating Sabre Problems

Learning Objectives

• Figure out how to write a problem for a planning program.
• Determine how utility functions within Sabre.
• Compare and contrast the planner’s behavior to when the game is played by a human.

Extra Credit:

• Generate a planning problem using a code-based LLM.
• Compare the processes of generating a planning problem by hand vs LLM

Introduction

In this homework, we’re going back to the beginning! Primarily, you will be converting the Action Castle game from HW1 into Sabre’s syntax by hand.

Working with Sabre

In this first part, you will be creating a planning problem following the syntax of Sabre and then running your problem through the Sabre planner.

Sabre tries to find a story based on a set of limits. It has three different types of limits:

• author temporal limit: “maximum number of actions in the author’s plan—that is, the actual actions that will be executed to raise the author’s utility” (-atl flag)
• character temporal limit: “maximum number of actions in a plan a character imagines when justifying an action” (-ctl flag)
• epistemic limit: “how deeply Sabre will search into a character’s theory of mind” (-el flag)

Whether a limit is reached is calculated by looking at the utility of the overall problem (utility()) or the utility of a particular character’s perspective (e.g., utility(Princess)).

The above definitions and more information can be found in the report A Collection of Benchmark Problems for the Sabre Narrative Planner. You can also find a partial example of a problem that I made in the Extra Credit.

Part 1: Make a Planning Problem by Hand

The skeleton of a problem has been provided to you in this notebook. Again, you can open this notebook in Colab, Deepnote, or VSCode. You might notice that there are some variations from Action Castle. I’ve simplified a few things: the rose is just in the garden (no rosebush) and there is no “Death” room or path from the tree.

To write a problem for Sabre, do the following:

1. Download one or a couple of the problems from the list https://github.com/sgware/sabre-benchmarks/tree/main/problems to use as reference.
2. Find your HW1 notebook. If you can’t find your notebook from when you did HW1, here is the empty one again: Homework 1 Notebook.
3. Note the syntax used in the example Sabre problems to make a planning problem for the first Action Castle game. You will implement the Actions from Action Castle in your plan. There are 11 of them in total.
4. Download the notebook for running Sabre and test your file. You can also run one of the example files to see what a successful plan looks like.
5. Iterate until Sabre can solve your problem. Tip: To debug your problem once your syntax bugs are fixed, you can try changing your utility to a smaller problem until you know the paths are available. For example, set your utility to location(Player) == GardenPath if you’re trying to make sure your walk action works. Also, the deeper the goal is, the longer the planner is going to take to run.

Part 2: Experiment with Utility

1. (2 pts) Set your utility() as the following block:

   utility():
    if(royal(Player)) 1 else 0;
   

   run it and collect the plan you get (for context this utility takes my solution about 3 minutes to plan through), and then replace it with

   utility():
    if(inv(Crown) == Player) 1 else 0;
   

   and run that and collect that plan.

   • Copy and paste each plan that you get (printed at the end of the output when you run the Java command) into a word document.
2. (2 pts) Do the above plans differ a lot from the actions someone would take when playing the interactive fiction version of Action Castle? (1-3 sentences)
3. (2 pts) Give the characters their own utility that is consistent with their attributes/personality in the game. 2 free points
   • Copy and paste what your utilities are and what the resulting plan is into your word document.
4. (2 pts) Now that you’ve added character utility, change the walk() action to allow all characters to walk around, not just the Player.
   • Copy and paste the resulting plan & share your impressions on how the story has changed.
5. (2 pts) Does adjusting the characters’ utilities result in a more interesting story? If so, why? If not, why not? (2-3 sentences)
6. (2 pts) Traditional planners require a pre-specified goal that the system tries to find a path toward. How does Sabre compare to more traditional planners? (1-3 sentences)

Extra Credit: Use GitHub Copilot for Problem Creation

Setting up GitHub Copilot

You can find the instructions here: https://code.visualstudio.com/docs/copilot/setup

But it essentially is:

1. Get access to GitHub Copilot, you can sign up for a free student account or do the 1-month free trial. It’s usually $10/month.
2. Make sure to block suggestions matching public code and uncheck allowing GitHub to use your code snippets to train on.
3. Install the extension on VSCode & link it to your GitHub account.

And you should be ready to go!

Generating a Planning Problem from wikiHow

We’ll now use GitHub Copilot to write a Sabre problem for a wikiHow article. The goal for this is to start from something that describes proceedures and actions and is written in natural language, and then have Copilot translate it into the description language used for automated planning.

Here are a few wikiHow articles that I thought might be interesting since they had some elements that could make for interesting interactive fiction. It’s fine to pick your own article. You shouldn’t translate the whole article, just a few steps, so you can pick out the parts that you think are most relevant/easiest to create a schema from.

Survival Stories

• How to Survive in the Woods
• How to Survive in the Jungle
• How to Survive on a Desert Island
• How to Survive on a Deserted Island With Nothing
• How to Get Out of Quicksand
• How to Open a Coconut
• How to Test if a Plant Is Edible
• How to Find True North Without a Compass
• How to Survive a Wolf Attack

Detectives

• How to Make a Detective Kit
• How to Disguise Yourself
• How to Make a Hidden Camera
• How to Hide Money
• How to Spy on People
• How to Hack
• How to Make a Grappling Hook
• How to Open a Locked Door
• How to Create a Secret Society

Dystopian Futures

• How to Survive a Comet Hitting Earth
• How to Survive an EMP
• How to Survive a Nuclear Attack
• How to Build a Fallout Shelter
• How to Survive a Riot
• How to Survive Under Martial Law
• How to Avoid Danger During Civil Unrest
• How to Thwart an Abduction Attempt
• How to Make Papyrus

Example

As an example, I’ll pick the How to Survive in the Woods article, and show you how part of the schema might look. Here is step 1 from that article:

Finding Drinking Water

Search for a source of fresh water.[1] The first thing that you’ll need in order to survive in the woods is water that you can drink. Look for signs of fresh water nearby like areas of green foliage that indicate water is nearby, low-lying areas where water could be collected, and signs of wildlife like animal tracks. It could mean that a creek, stream, or pond is nearby. While finding water is important for survival, be aware some water sources will not be safe - if possible treat all drinking water before using it. [2] If there are mountains nearby, look for water collected at the foot of the cliffs.

• The presence of insects like mosquitoes and flies means that water is nearby.
• Water from heavily oxygenated water (such as from a big waterfall or rapids) typically is safer than that from a slow or still water source.
• Freshwater springs are typically safer water sources, although these can be contaminated by mineral or bacteria as well.
• Remember that all untreated water must be considered risky unless treated. Even crystal clear water can harbor diseases and be dangerous if consumed.

My Sabre problem for this might look like this:

I would declare some types that would be relevant. These are like listing variable.

  type location;
  type type : attribute;
  type player : location;
  type attribute : entity;
  type water: entity;
  type status;

And some entities – specific instances of the types above. These are like the characters and things in your story.

  entity Bugs : player;
  entity Treated : attribute;
  entity Fresh : type;
  entity Moving : type;
  entity Salt : type;
  entity Chesapeake : location;
  entity Lake : location;
  entity Water : water;
  entity Player : player;

And properties – what types of what attributes entities might have and the relations they have with each other.

  property is(location : location, attribute : attribute) : boolean;
  property has_water(location : location) : boolean;
  property is(location : location) : type;
  property at(player : player) : location;
  property from(water : water) : location;
  property safe(water : water) : boolean;
  property has(player : player, water : water) : boolean;
  ...

Then we need some starting facts – what state things are in at the beginning of the story.

  at(Foot) = Lake;
  at(Bugs)= Lake;
  !has(Player, Water);
  at(Player) = Chesapeake;
  has_water(Chesapeake);
  ...

And actions – things that move the story along.

  action get_water(player : player, water : water, location : location) {
     precondition:
		has_water(location) &
		at(player) == location;
     effect:
		!safe(water) &
		has(player, water);
  };
  ...

Any potential triggers – things that should occur but don’t neccessarily have an event that starts it.

  trigger know_water_source(player : player, other : player, water : water, location : location) {
	precondition:
		at(player) != location &
		from(water) == location &
		has(other, water);
	effect:
		believes(player, safe(water));
  };
  ...

Finally, some utility. This is how you want the planner to weight effects.

  utility(Water):
	if(safe(Water))
		2
	elseif(is(Water,Fresh) & is(Water,Moving))
		1
	else
		0;
   ...

Using GitHub Copilot

1. Download an example problem from https://github.com/sgware/sabre-benchmarks/tree/main/problems (or use the same one you’ve used in Part 1).
2. Import the problem file in VSCode.
3. Create a new .txt file for the problem you plan to generate.
4. Open the file and press CTRL + I to open Copilot.
5. Add an example problem file as an attachment in the prompt (as shown in image).
6. Write your prompt.
7. Save the file and run it through Sabre.
8. If it is close, count the number of edits you need to make to get it to run. If it’s pretty far off from what you wanted, generate it again.

In order to get the full 5 points, you need:

• Sabre to be able to find a solution in the generated problem.
• To provide the list of changes you made to the generated code to get it to work.

What to submit

You should submit the following:

• A Jupiter notebook with your completed planning problem.
• A PDF file containing your answers to Parts 2 & 3.
• If you did the extra credit:
  • A PDF called “extra-credit.pdf” containing 1) the original text of your prompt and 2) what problem file you used as input.
  • A txt file called “generated.txt” of the generated problem.

Submissions should be done on Blackboard.

Grading

Recommended readings

• Stephen G. Ware and Cory Siler, Sabre: A Narrative Planner Supporting Intention and Deep Theory of Mind.

• Stephen G. Ware, Lasantha Senanayake, and Rachelyn Farrell, Causal Necessity as a Narrative Planning Step Cost Function.

• Stephen G. Ware and Rachelyn Farrell, A Collection of Benchmark Problems for the Sabre Narrative Planner.