The fourth week of Intelligent systems provided an introduction to Planning. The question that stands out in my mind from the tutorial is: what is the difference between problem solving via search and problem solving via planning? After running through the weeks material I hope to be able to answer that question.
First off the two learning objectives for the week (hmm seems to simple):
- Goal stack planning
- Partial order planning
What do we need to do goal based planning?
- a world model
- an action model
- a problem solving strategy
Planning uses a divide and conquer strategy, allowing for sub goals to be identified. One must be careful to ensure that interrelation between sub goals is identified. This can reduce branching factors and assist in problems where heuristics are difficult to define.
Planning algorithms can work forwards or backwards, it seems that in most situations working backwards from the goal proves to be more efficient and further reduces branching factors.
Here is an example of a Goal stack planner from the lecture:
World model: Objects, states and goals
Action model: Operators
Problem solving strategy: Goal-stack planning
States are defined using first order logic, ie: AT(home) ΛHAVE(milk) ΛHAVE(bananas)
At this point we were introduced to the frame problem
The frame problem is that specifying only which conditions are changed by the actions do not allow, in logic, to conclude that all other conditions are not changed.
I don’t really understand why this is such an issue at present, the human brain does not reconfirm every fact after an action and it can still function effectively. Perhaps the reasoning this is considered such a big issue will become more apparent as I learn a bit more on the topic.
So, with an action in the goal stack planning systems [ using STRIPS] would appear as such:
>ACTION: GO(market)
>PRECONDITION: AT(home) ΛCAR-AT(home)
>ADD: AT(market), CAR-AT(market)
>DELETE: AT(home), CAR-AT(home)
From the goal state, one can define the preconditions, identifying which action is required to generate those conditions and work back until the initial state is reached. I do have some questions on how actions are selected and backtracking occurs. As in box world if B is picked up, why would it not be placed back on C (see lecture notes) unless there is an explored set.
After the box world example we moved onto Partial order Planning:
Partial order planning allows for less commitment in the search, reducing backtracking. I am still a little fuzzy on how this would be implemented so I will have to review the text book.
So, planning is clearly different from searching which simply applies valid operations to an initial state until it stumbles onto the goal state (this stumbling can be guided by heuristics).