Automated Planning

This is an introductory lesson on "Symbolic Logic & Reasoning" and "Planning".

What is logic?

text

How logic is evolved in the field of AI?

text

What's an expert system?

text

Propositional Logic

text

Logical Connectors

AND, OR, NOT, etc.

Truth Tables

text

Some terminology:

We say a sentence is:

• Valid if it's true in every possible model.
• Satisfiable if it's true in some models.
• Unsatisfiable if it cannot be satisfied under any circumstances.

Propositional logic limitations

text

First Order Logic

text

	World	Belief
Propositional Logic	Facts	T/F/?
First Order Logic	Relations, Objects, Functions	T/F/?
Probability Theory	Facts	[0...1]

Representation

Atomic	Factored	Structured
problem solving	variables	relationships between objects

FOL Model

text

FOL Syntax

text

Planning

Planning means figure out a solution ahead of time and when it gets to execution, just execute the plan all the way through. This turns out not to be very good. A better way is to also interact with environment and get some feedback along way, i.e. interleaving planning and execution. There are few reasons why it's the case:

• Stochasticity in environment
• Multiagent
• Partial observability
• Unknown factors
• Some tasks are inheretly hierarchical.

The main idea is that by doing some action (execution) along the way, we can reduce some of the uncertainty.

Vaccum Cleaner Example: Assume there is a vacuum cleaner which is supposed to collect dirt from two locations left(L) and right (R). Locations can have dirt or not. The goal for vacuum cleaner is to collect the dirt. The state space has 8 possible states.

Conformant Planning: Conformant planning means "synthesizing a strong plan under the assumption of null run-time observability". A conformant plan consists of a sequence of actions that is guaranteed to achieve the goal regardless of the uncertainty in the initial condition and in the nondeterministic effects of actions. (This relates to the first Vacuum Cleaner sensorless planning).

Partially observable Vaccum Cleaner: Let's assume the vacuum has some sensors which can do local sensing, meaning that it can see what location it is in and also what is going on in the current location. One thing to note here is that the mere act of observation doesn't necessarily guarantee to reduce uncertainty. In fact, some observation may make it more confusing doesn't necessarily guarantee to reduce uncertainty. In fact, some observation may make it more confusing. Making an observations splits the belief space into smaller space.

In a stochastic partially observable environment the actions tend to increase uncertainty and the observations tend to bring that uncertainty back down.

Infinite Sequences: How to find a successful plan? text

Unbounded & Bounded Solutions: text

Classical Planning

Classical Planning is a representation language dealing with states, actions, and plans. It's also an approach for dealing with the problem of complexity by factoring the world into variables.

So, under Classical Planning state space would be k-boolean of all states (2^k states). Under CP, we have "complete assignment" for World State, but we can have either of "complete assignment", "partial assignment", or even "arbitrary formula" Belief State.

Progression Search: text

Regression Search: text