3 The Multiset State Representation

8.12

3 The Multiset State Representation🔗ℹ

In the multiset state representation, the world is represented by a multiset. Actions and goals are represented by multiset actions and multiset conditions.

3.1 Multiset Actions🔗ℹ

(require planning/multiset/action)

package: planning

A multiset action is an action on multisets. Multiset actions have four components:

A hash of preconditions, where each key is an element and the corresponding value is a range of natural numbers describing how many copies of the element must be in the multiset for the action to be applicable.
A collection of elements to remove from the multiset. Attempting to remove elements that a multiset does not contain is allowed, but it has no effect.
A collection of elements to add to the multiset.
A hash of replacements, where each key is an element and the corresponding value is a natural number that determines how many copies of the element the multiset will contain after the action is performed.

procedure
(multiset-action? v) → boolean?
v : any/c

A predicate for multiset actions.

procedure
(multiset-action [ #:preconditions preconditions
#:deletions deletions
#:additions additions
#:replacements replacements
#:cost cost])
→ multiset-action?
  preconditions : (hash/c any/c range?) = empty-hash
  deletions : multiset? = empty-multiset
  additions : multiset? = empty-multiset
  replacements : (hash/c any/c natural?) = empty-hash
  cost : (>=/c 0) = 1

Constructs a multiset action.

Examples:

(define make-water
  (multiset-action
   #:preconditions (hash 'hydrogen (at-least-range 2)
                         'oxygen (at-least-range 1))
   #:additions (multiset 'water)
   #:deletions (multiset 'hydrogen 'hydrogen 'oxygen)))

> (multiset-act (multiset 'hydrogen 'hydrogen 'oxygen 'carbon) make-water)
(multiset 'carbon 'water)

procedure
(multiset-act set action) → multiset?
set : multiset?
action : multiset-action?

Performs action on set, returning a new multiset. The action must be applicable to set or else a contract error is raised.

procedure
(multiset-action-applicable? action set) → boolean?
action : multiset-action?
set : multiset?

Determines whether action is applicable to set, based on whether the preconditions of action are satisfied.

Examples:

> (define red-to-blue
    (multiset-action
     #:preconditions (hash 'red (at-least-range 1))
     #:additions (multiset 'blue)
     #:deletions (multiset 'red)))
> (multiset-action-applicable? red-to-blue (multiset 'red))
#t
> (multiset-action-applicable? red-to-blue (multiset 'green))
#f

3.2 Multiset Conditions🔗ℹ

(require planning/multiset/condition)

package: planning

A multiset condition is a condition in the multiset state representation. Multiset conditions contain only a hash of preconditions of the same form as the preconditions in a multiset action.

procedure
(multiset-condition? v) → boolean?
v : any/c

A predicate for multiset conditions.

procedure
(multiset-condition preconditions) → multiset-condition?
preconditions : (hash/c any/c range?)

Constructs a multiset condition.

procedure
(multiset-condition-ignore-frequencies condition)
→ set-condition?
condition : multiset-condition?

Weakens condition into a set condition that only considers whether elements are either present or absent. If a multiset meets condition, then it will meet the returned set condition. If a multiset fails to meet the returned set condition, then it will fail to meet condition. Note that because the returned set condition is weaker than condition, it’s possible for a multiset to fail to meet condition but succeed in meeting the returned set condition.

Examples:

(define can-make-water-for-first-time
  (multiset-condition
   (hash 'hydrogen (at-least-range 2)
         'oxygren (at-least-range 1)
         'water (singleton-range 0))))

> (multiset-condition-ignore-frequencies can-make-water-for-first-time)
(set-condition
  #:obstructions (set 'water)
  #:requirements (set 'oxygren 'hydrogen))

3.3 Multiset Planning Problems🔗ℹ

(require planning/multiset/problem)

package: planning

A multiset planning problem is a combination of a multiset, a set of multiset actions, and a goal multiset condition. A solution to the problem is a list of actions to perform that will transform the multiset into a multiset that satisfies the goal condition.

procedure
(multiset-planning-problem? v) → boolean?
v : any/c

A predicate for multiset planning problems.

procedure
(multiset-planning-problem #:state state
#:actions actions
#:goal goal)
→ multiset-planning-problem?
  state : multiset?
  actions : (set/c multiset-action?)
  goal : multiset-condition?

Constructs a multiset planning problem.

procedure
(multiset-planning-problem-state problem) → multiset?
problem : multiset-planning-problem?

Returns the multiset representing the initial state in problem.

procedure
(multiset-planning-problem-actions problem)
→ (set/c multiset-action?)
problem : multiset-planning-problem?

Returns the multiset actions that may be performed as part of a plan for problem.

procedure
(multiset-planning-problem-goal problem) → multiset-condition?
problem : multiset-planning-problem?

Returns the goal multiset condition that a plan for problem must achieve.

procedure
(multiset-plan problem) → (option/c (listof multiset-action?))
problem : multiset-planning-problem?

Attempts to solve problem and return a plan in the form of a list of actions to take to achieve the problem’s goal. A solution may not exist. The current planner is not implemented efficiently, so it is possible to construct multiset problems that take too long to solve or for which the planner fails to terminate.

Examples:

(define destroy-water
  (multiset-action
   #:preconditions (hash 'water (at-least-range 1))
   #:deletions (multiset 'water)
   #:additions (multiset 'hydrogen 'hydrogen 'oxygen)))

(define create-peroxide
  (multiset-action
   #:preconditions (hash 'hydrogen (at-least-range 2)
                         'oxygen (at-least-range 2))
   #:deletions (multiset 'hydrogen 'hydrogen 'oxygen 'oxygen)
   #:additions (multiset 'peroxide)))

(define initial-state (multiset 'water 'water))

(define create-peroxide-from-water
  (multiset-planning-problem
   #:state initial-state
   #:actions (set destroy-water create-peroxide)
   #:goal (multiset-condition (hash 'peroxide (singleton-range 1)))))

> (define the-plan (multiset-plan create-peroxide-from-water))
> (multiset-action-perform-all (present-value the-plan) initial-state)
'(#<multiset: water water>
  #<multiset: hydrogen hydrogen oxygen water>
  #<multiset: hydrogen hydrogen hydrogen hydrogen oxygen oxygen>
  #<multiset: hydrogen hydrogen peroxide>)

1	Overview
2	The Set State Representation
3	The Multiset State Representation
4	The Hash State Representation
5	Phase Transitions
6	Sokoban

3.1	Multiset Actions
3.2	Multiset Conditions
3.3	Multiset Planning Problems