Page 172 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes Introduction

In the field of artificial intelligence, “planning” is defined as designing the behavior of some
entity that acts an individual, a group, or an organization. The output is some kind of blueprint
for behavior, which we call a plan. There are wide variety of planning problems, differentiated
by the types of their inputs and outputs. Typically, planning problems get more and more
difficult as more flexible inputs are allowed and fewer constraints on the output are required. As
this flexibility increases, the space of possibilities needing to be explored by the planning
algorithm grows extremely quickly. This problem is the essence of the planning problem, and
it arises regardless of which specific planning methodology is used (nonlinear planning,
deductive planning, hierarchical planning, etc.) – in all of these controlling an exponentially
growing search space is a central problem. In all planning formalizations, it is critical that some
sort of knowledge (heuristic or otherwise) is used to make reasonable decisions at any of the
many choice points which arise in planning. Such choice points can concern:

ordering of subgoals
selection of operators/control structures
resolution of conflicts/threats by different techniques
choosing between differing commitment strategies
selecting/choosing the right control regime
In all of these cases, picking the right control knowledge can result in an algorithm that is able
to identify and prune many dead-end branches of the search space before the algorithm explores
them, ideally while preserving the soundness and completeness of the planner. However,
designing search control approaches is difficult and it is often impossible to ensure various
qualitative and quantitative properties of the “controlled algorithms”.

9.1 Preliminary Concepts

Deductive planning systems rely on an expressive logical representation formalism, a proper
formal semantics, and a calculus the rules of which are used to implement the planner. Plans are
generated by constructive proof of so-called plan specification formulae. In the simplest case,
specification formulae describe the initial state and the goal state and demand for the existence
of a plan that transforms the one into the other. Starting from a plan specification, a proof (tree)
is developed by applying logical inference rules in a backward-chaining manner, and by
instantiating the plan variable accordingly. We have introduced the modal temporal planning
logic TPL, as an example, and have demonstrated how deductive planning works in this context.
TPL is an expressive formalism that allows for the distinction of rigid and flexible symbols and
provides a programming language for plans, including control structures like conditionals and
loops. The search problems and solutions we have addressed are concerned with the guidance of
the theorem proving = planning process, the selection of appropriate basic actions, and the
selection of subgoals.

Notes Since a carefully designed domain model is an essential prerequisite for acting
safely and efficiently in this context, the planning environment we have introduced provides
deductive support in setting up provably consistent domain models.

The general context for the research is the design of integrated planning and scheduling
architectures for constraint-based activity management. A number of aspects useful to improve

166 LOVELY PROFESSIONAL UNIVERSITY