Home

A02: Git planner

This assignment helps you practice with the PDDL language and automated planning systems in general. Your task is to write PDDL code to generate a series of git commands that update the files or repository from a given initial repository state to a given goal state.

Background about git

As you know, git is a tool that keeps track of the contents of files over time, i.e., a version control system (VCS). All VCS’s provide a variety of commands that let the user indicate which files should be committed, reverted, and so on. These commands and the way they interact defines each VCS’s “workflow.”

All VCS workflows involve at least two concepts:

Unlike other VCS’s, git adds another concept in the workflow:

Git and many other VCS’s also have concepts of branches, pushes and pulls, etc. These significantly complicate matters so we will not worry about them here. We are only going to work with the workspace, index, and (local) repository.

The following diagram shows the operations that need to be understood by the git planner, and how they impact the workspace, index, and repository. See the notes below for details about each command.

Git workflow

Predicates

Recall that in a planning problem, a “predicate” is a property of a state. The predicate can be true or false. These predicates correspond to the status shown by git status (more specifically, git status --porcelain).

Actions

Recall that in a planning problem, an “action” transforms one state to another, and typically changes the truth-value of some predicates. These changes are the action’s “effects.” Relevant git actions are listed below. I’ve intentionally not described the actions. Refer to the man pages, e.g., man git-add or man git-checkout to understand the effects of each action.

Task

Write a domain.pddl file that solves the planning problems shown below. All files are available on londo at /home/jeckroth/csci431/assignment/A02, except the missing domain.pddl file.

You can test your PDDL code by running fast-downward.py prob1.pddl --search "astar(blind())" where prob1.pddl is whichever problem file you want to test. Your domain.pddl file will be loaded automatically. Feel free to try different search strategies and heuristics (see the PDDL notes).

Deliverables

You only need to define and submit the domain.pddl file. The various problem files that your domain needs to solve are listed below. All files are available on londo at /home/jeckroth/csci431/assignment/A02. Name your repository csci431-A02.

Example problems

Here are some examples that your domain file must be able to solve. The setup (with actual git commands) is just for illustration; you do not need to actually create an example repository and example files. The corresponding PDDL problem file and a generated plan, as found by Fast Downward, are also given. All that is missing is your domain file, domain.pddl.

Example 1

Setup:

mkdir prob1
cd prob1
git init
echo "aaa" > a.txt

Goal:

Solution:

git add a.txt
git commit

Corresponding problem file:

(define (problem p)
  (:domain git)
  (:objects "a.txt")
  (:init
   ;; initial conditions determined by 'git status --porcelain' output
   ;; ?? a.txt
   (untracked "a.txt")
   )
  (:goal
   (committed "a.txt")
   )
)

Plan as found by fast-downward:

$ fast-downward.py prob1.pddl --search "astar(blind())"

$ cat sas_plan
(add "a.txt")
(commit )
; cost = 2 (unit cost)

Example 2

Setup:

mkdir prob2
cd prob2
git init
echo "aaa" > a.txt
echo "bbb" > b.txt
git add a.txt

Goals:

Solution (one possible ordering):

git reset a.txt
git add b.txt
git commit

Corresponding problem file:

(define (problem p)
  (:domain git)
  (:objects "a.txt" "b.txt")
  (:init
   ;; initial conditions determined by 'git status --porcelain' output
   ;; A  a.txt
   (added-to-index "a.txt")
   ;; ?? b.txt
   (untracked "b.txt")
   )
  (:goal
   (and (untracked "a.txt")
        (committed "b.txt"))
  )
)

Plan as found by fast-downward:

$ fast-downward.py prob1.pddl --search "astar(blind())"

$ cat sas_plan
(add "b.txt")
(reset "a.txt")
(commit )
; cost = 3 (unit cost)

Example 3

Setup:

mkdir prob3
cd prob3
git init
echo "aaa" > a.txt
echo "bbb" > b.txt
git add b.txt

Goals:

Solution:

git reset --hard

A reset-hard action erases b.txt from the workspace since it was added to the index. If it were never added to the index (i.e., remained untracked), then reset-hard would have left it alone.

Corresponding problem file:

(define (problem p)
  (:domain git)
  (:objects "b.txt" "a.txt")
  (:init
   ;; initial conditions determined by 'git status --porcelain' output
   ;; A  b.txt
   (added-to-index "b.txt")
   ;; ?? a.txt
   (untracked "a.txt")
   )
  (:goal
   (and (untracked "a.txt")
        (not (untracked "b.txt"))
        (not (committed "b.txt"))
        (not (modified-in-workspace "b.txt"))
        (not (deleted-in-workspace "b.txt"))
        (not (updated-in-index "b.txt"))
        (not (added-to-index "b.txt"))
        (not (deleted-from-index "b.txt")))
  )
)

Plan as found by fast-downward:

$ fast-downward.py prob3.pddl --search "astar(blind())"

$ cat sas_plan
(reset-hard )
; cost = 1 (unit cost)

Example 4

Setup:

mkdir prob4
cd prob4
git init
echo "aaa" > a.txt
echo "bbb" > b.txt
git add a.txt
git add b.txt
git commit -m "message..."
echo "xxx" > a.txt
rm b.txt

Goals:

Solution:

git add a.txt
git commit -m "message..."
git add b.txt

Corresponding problem file:

(define (problem p)
  (:domain git)
  (:objects "a.txt" "b.txt")
  (:init
   ;; initial conditions determined by 'git status --porcelain' output
   ;;  M a.txt
   (modified-in-workspace "a.txt")
   ;;  D b.txt
   (deleted-in-workspace "b.txt")
   )
  (:goal
   (and
    (deleted-from-index "b.txt")
    (committed "a.txt"))
  )
)

Plan as found by fast-downward:

$ fast-downward.py prob4.pddl --search "astar(blind())"

$ cat sas_plan
(add "a.txt")
(commit )
(add "b.txt")
; cost = 3 (unit cost)

Example 5

Setup:

mkdir prob4
cd prob4
git init
echo "aaa" > a.txt
echo "bbb" > b.txt
echo "ccc" > c.txt
git add a.txt
git add b.txt
git commit -m "message..."
echo "xxx" > a.txt
git add a.txt
rm b.txt
echo "yyy" > c.txt

Goals:

Solution:

git reset a.txt
git add c.txt
git commit -m "message..."
git add b.txt

Corresponding problem file:

(define (problem p)
  (:domain git)
  (:objects "a.txt" "b.txt" "c.txt")
  (:init
   ;; initial conditions determined by 'git status --porcelain' output
   ;; M  a.txt
   (updated-in-index "a.txt")
   ;;  D b.txt
   (deleted-in-workspace "b.txt")
   ;; ?? c.txt
   (untracked "c.txt")
   )
  (:goal
   (and
    (modified-in-workspace "a.txt")
    (deleted-from-index "b.txt")
    (committed "c.txt"))
  )
)

Plan as found by fast-downward:

$ fast-downward.py prob4.pddl --search "astar(blind())"

$ cat sas_plan
(add "c.txt")
(reset "a.txt")
(commit )
(add "b.txt")
; cost = 4 (unit cost)

Grading rubric

Out of 5 points:

CSCI 431 material by Joshua Eckroth is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License. Source code for this website available at GitHub.