PowerPoint Presentation
Classical Planning
Improving Heuristic Search
Copyright By PowCoder代写加微信 assignmentchef
6CCS3AIP – Artificial Intelligence Planning
Dr Tommy Thompson
FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS
Hi I’m Tommy Thompson and welcome to this series on classical planning.This segment of the module is oriented around the foundational principles of planning as discussed in the introduction to the Artificial Intelligence Planning class.Here we will aim to expand on these core elements in several ways and how to address the increasing complexity of planning problems.
Classical Planning: Material Overview
Classical Planning: The fundamentals.
Improving Search
Heuristic Design (RPG/LAMA)
Dual Openlist Search
Optimal Planning
Pattern Databases
Non-Forward Search
SAT Planning
POP Planning
HTN Planning
Planning Under Uncertainty
FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS
To give you an overview of the material we will be covering in this part of the module, I’ll be referring back to this list throughout to highlight our progress but also as means to stop and think about how the content discussed in class is related to one another.All of these topics are designed such that we have a basis from which to build into more complex variants of planning later in the module as we handle greater complexity in planning domains.
It’s important to recognise now that once we establish the fundamentals, we were be exploring different variations of how to execute the planning process.This is very much a reflection of how planning research has grown, with particular strands of planning emerging as specific problems or ideas of how to approach existing problems are explored.So while the principles of classical planning will hold true throughout this part of the module, we will see a lot of variation in the approaches taken as part of the planning process.
Fundamentals
Definition of the problem – PDDL
Forward Search
Breadth/Depth First
Introducing Heuristics
Destination point
Constraints:
Truck capacity
Number of drivers
Goal: all cargos at a destination point
Initial State
FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS
If we return to the opening of this module, we discussed the idea of how to formulate a planning problem.Such as the logistics domain of driving packages between locations using the available trucks.We need to make sure that we successfully encapsulate all of the knowledge required to express any possible permutation of the problem – this being the domain – alongside the individual problems themselves.We then encapsulate this within the PDDL language as means to express the planning problem in a way that numerous planning systems can look towards searching for a solution.
After this, we can then begin to search for a solution to the problem.We may perhaps use a simple solution forward search algorithm such as Breadth or Depth First search which allows us to explore the search space in a simple, methodical fashion.But this of course quite suboptimal, we want something more effective.
Fundamentals
Definition of the problem – PDDL
Forward Search
Breadth/Depth First
Introducing Heuristics
FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS
We want to find a more effective means of calculating which of the open nodes should be explored next.Hence we have the ‘open list’ data structure which maintains the collection of ‘open nodes’ to visit.In Breadth First Search, this is just a queue.In depth first search, it’s a stack.But what we really want, is to prioritise them within the open list based on some criteria.
Hence we begin to consider the heuristics of the problem: a simple rule of thumb metric where we can utilise that knowledge in a manner that will allow us to search the state space faster.
This is in effect, a goal distance estimation: how far away do we think roughly that we are from the goal state of the problem.
Heuristic Search Planning
h: estimate of scurrent to goal
g: cost of path from sinit to scurrent
Prioritise open nodes with heuristic
Different algorithms exploit heuristic and costs.
Uniform Cost Search: Expand node with minimum g
Greedy Best-First Search: Expand node with minimum h.
A*: Expand node with minimum (g+h)
FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS
So to use heuristic search planning, we need to have established our heuristic of the problem space, which tells us information about how close we are to the goal, denoted as h.
As well as how far we have travelled in the problem space to date, which is expressed as g.This is the cost of everything we have done to reach this point.
Depending on the algorithm, we can exploit g and or h to help us prioritise how to explore the problem space.
Hence for example, uniform cost search expands open nodes with the lowest g value, which best-first search uses the h value.
It’s then we combine them in A* to achieve a much more effective technique.A search process that is both prioritising states that are closer to the goal and detracting from those reached using expensive paths.
Building Heuristics
Admissible
If h(s) is a lower bound of the cost of all goal-reaching plans starting at s.
i.e. Heuristic value is less than or equal to the actual cost.
Consistent
h(s) is always less than or equal to estimated value from any neighbouring vertex, plus the cost of reaching it.
i.e. if we travel from s s’ using action a
whereadmissible.
FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS
But building a heuristic is a difficult challenge, especially on a problem to problem basis and – as we’ll see soon in this module – in situations in planning where we need to create something that is domain independent.
There are three key features of a heuristic that we hope to achieve in order to achieve the best search process…
Admissible, whereby the heuristic never overestimates the cost of reaching the goal from a given destination.It either underestimates or – in the worst case – calculates exactly how far away we are from the goal.This might seem weird to have it underestimate, and ideally we don’t want it to underestimate too much, but if it overestimates it’s more likely for it to detract us from exploring a given state as a valid path from the goal.
Consistent, meaning that for any child states, the heuristic value will be equivalent to the parent’s heuristic value minus the cost it took us to reach it.
Lastly, Additive, where two heuristics h1 and h2 are additive, if they and a third heuristic, which is the summation of the two are all admissible.
Outstanding Problems
Building Domain-Independent Heuristics
Improving Search
FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS
However, while we have established these base principles, there are a lot of issues we still need to address.Namely…
How do we build a heuristic for a given domain or problem?
Especially if using a planning system that relies on PDDL, where we’re not going to be giving it this information.We just give the domain and problem notation.
How can we search more effectively in the state space?
All the heuristic search systems we’ve seen to-date work fine, but we’re going to be dealing with large and complex problem spaces.So we need to find a way to further optimise the search process.
How do we build more effective heuristics that help us better search the state space?
Can we build heuristics that help not just prioritise states on the path to the goal, but also help us search the space more efficiently.
Improving Heuristic Search
Problem Relaxation and Relaxed Planning (RPG Heuristic)
Planning Landmarks
Landmark Counting (and LAMA)
FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS
Now there are multiple approaches to doing all of this and like many facets of planning, these are ongoing research endeavours.For this segment of the module, we’re going to look at three particular approaches that are useful for building on basic heuristic search.
First of all there is the relaxation, whereby we create a simpler – relaxed – version of the problem that removes some of the constraints.We then solve the relaxed version of the problem from this state and this gives us an estimate of goal distance.This creates a domain-independent heuristic for any given problem.
Secondly, there are landmarks, these are facts that must be true at some point in every valid solution to a problem.For example, if we were to consider the driver log domain again, than all trucks need to visit the packages and in turn those packages need to be on a truck at some point in order for them to reach their destination.This is actually a useful means not just to estimate distance to goal, but can help decompose planning problems into smaller tasks that need to be solved.
Thirdly, we can look at the Landmark Count Heuristic and the LAMA system, whereby once we have landmarks for a given problem, we can actually estimate the goal distance by counting how many landmarks we have yet to solve for a that problem.
Let me address now that there are other approaches we’re not going to cover yet, given these will actually relate to heuristics for optimal planning, but will come to look at them later in the module.
Classical Planning
Improving Heuristic Search
6CCS3AIP – Artificial Intelligence Planning
Dr Tommy Thompson
FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS
And with this, we’ll conclude this opening video and in the next chapter, we will now begin to move into relaxed planning and preparing the RPG heuristic.
Thanks for watching this first video and we will begin to get into more detail in the next chapter.
/docProps/thumbnail.jpeg
程序代写 CS代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]
Reviews
There are no reviews yet.