Page 173 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Unit 9: Search and Control Strategies

the applicability of such architectures have been addressed. One aspect is connected with the Notes
involvement of users in actively exploiting such systems. Relevant problems are: the definition
of a domain representation language powerful enough to represent the physical constraints of
a domain, and endowed with clear semantics as a basis for automated verification tools; the
investigation of various aspects of the interaction with the user like the “cognitive intelligibility”
of the plan representation and the planning process.
A second aspect consists in the study of specialized classes of constraint propagation techniques:
interesting results on the efficiency and flexibility of manipulating quantitative temporal
networks have been obtained through the synthesis of dynamic algorithms for constraint posting
and retraction; also the problem of mixed resource and time constraints representation has been
studied and some techniques proposed for the synthesis of implicit temporal constraints from
the analysis of resource representation. A further aspect consists in the integration of the
incremental constructive way of building a solution with local search techniques: in particular
a taboo search algorithm has been proposed that take advantage of the given temporal
representation to solve planning problems requiring multiple resources.
Early AI researchers developed algorithms that imitated the step-by-step reasoning that humans
use when they solve puzzles or make logical deductions. By the late 1980s and 1990s, AI research
had also developed highly successful methods for dealing with uncertain or incomplete
information, employing concepts from probability and economics.

Did u know? For difficult problems, most of these algorithms can require enormous
computational resources – most experience a “combinatorial explosion”: the amount of
memory or computer time required becomes astronomical when the problem goes beyond
a certain size. The search for more efficient problem-solving algorithms is a high priority
for AI research.

Human beings solve most of their problems using fast, intuitive judgments rather than the
conscious, step-by-step deduction that early AI research was able to model. AI has made some
progress at imitating this kind of “sub-symbolic” problem solving: embodied agent approaches
emphasize the importance of sensor motor skills to higher reasoning; neural net research attempts
to simulate the structures inside the brain that give rise to this skill; statistical approaches to AI
mimic the probabilistic nature of the human ability to guess.

Self Assessment

State whether the following statements are true or false:
1. Plans are generated by constructive proof of so-called plan specification formulae.
2. By the late 1940s and 1960s, AI research had also developed highly successful methods for
dealing with uncertain or incomplete information, employing concepts from probability
and economics.

3. AI has made some progress at imitating kind of “sub-symbolic” problem solving.
4. TPL is an expressive formalism that allows for the distinction of rigid and flexible symbols.
9.2 Examples of Search Problems

9.2.1 Water Container Problem

Search plays a major role in solving many Artificial Intelligence (AI) problems. Search is a
universal problem-solving mechanism in AI. In many problems, sequence of steps required to

LOVELY PROFESSIONAL UNIVERSITY 167