L06: Nesting

Question 1

What is nesting?

Answer 1

In the context of constraint programming, nesting occurs when one combinatorial object is nested inside another (do not have to be the same type of object)

E.g.
- A set of sets
- A sequence of functions

Question 2

How do planning problems employ nested types?

Answer 2

Planning problem: Find a sequence of actions to transform an initial state into a goal state

When a planning problem allows us actions to be performed in parallel in a single step, it is natural to characterise it as a sequence of sets of actions.

Question 3

How can we represent nesting inside sequences using explicit representation?

Answer 3

We can have a 2D array where the top index is the is the index of the outer elements, and the left index is the index of the elements within the sequence element.
The domain for each variable is all values for the inner object + a dummy variable in case the inner object has a bounded length

We can have a row at the bottom for switches to indicate whether the corresponding column is part of the sequence

E.g. Sequence of sets
The top index is indexed by the outer sequence elements
For each column (each element of the sequence), the elements are the elements of a set

Question 4

How can we represent nesting inside sequences using occurrence representation?

Answer 4

We can have a 2D array where the top index is the index of the outer object and the left index is the values of the inner object