Page 177 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Unit 9: Search and Control Strategies

as it allows to understand every aspect of (human or animal) life as a problem. This includes Notes
issues like finding food in harsh winters, remembering where you left your provisions, making
decisions about which way to go, learning, repeating and varying all kinds of complex
movements, and so on. Though all these problems were of crucial importance during the
evolutionary process that created us the way we are, they are by no means solved exclusively by
humans. We find a most amazing variety of different solutions for these problems in nature (just
consider, e.g., by which means a bat hunts its prey, compared to a spider). For this, we will
mainly focus on those problems that are not solved by animals or evolution, that is, all kinds of
abstract problems (e.g. playing chess).
Furthermore, we will not consider those situations as problems that have an obvious solution:
Imagine Knut decides to take a sip of coffee from the mug next to his right hand. He does not
even have to think about how to do this. This is not because the situation itself is trivial (a robot
capable of recognising the mug, deciding whether it is full, then grabbing it and moving it to
Knut’s mouth would be a highly complex machine) but because in the context of all possible
situations it is so trivial that it no longer is a problem our consciousness needs to be bothered
with. The problems we will discuss in the following all need some conscious effort, though
some seem to be solved without us being able to say how exactly we got to the solution. Still we
will find that often the strategies we use to solve these problems are applicable to more basic
problems, too.

For many abstract problems it is possible to find an algorithmic solution. We call all those
problems well-defined that can be properly formalised, which comes along with the following
properties:
The problem has a clearly defined given state. This might be the line-up of a chess game,
a given formula you have to solve, or the set-up of the towers of Hanoi game.

There is a finite set of operators, that is, of rules you may apply to the given state. For the
chess game, e.g., these would be the rules that tell you which piece you may move to
which position.
Finally, the problem has a clear goal state: The equations is resolved to x, all discs are
moved to the right stack, or the other player is in checkmate.

Not surprisingly, a problem that fulfils these requirements can be implemented algorithmically.
Therefore many well-defined problems can be very effectively solved by computers, like playing
chess.
Though many problems can be properly formalized (sometimes only if we accept an enormous
complexity) there are still others where this is not the case. Good examples for this are all kinds
of tasks that involve creativity, and, generally speaking, all problems for which it is not possible
to clearly define a given state and a goal state: Formalizing a problem of the kind “Please paint
a beautiful picture” may be impossible. Still this is a problem most people would be able to
access in one way or the other, even if the result may be totally different from person to person.
And while Knut might judge that picture X is gorgeous, you might completely disagree.
Nevertheless ill-defined problems often involve sub-problems that can be totally well-defined.
On the other hand, many everyday problems that seem to be completely well-defined involve-
when examined in detail- a big deal of creativity and ambiguities. If we think of Knut’s fairly
ill-defined task of writing an essay, he will not be able to complete this task without first
understanding the text he has to write about. This step is the first sub goal Knut has to solve.
Interestingly, ill-defined problems often involve sub problems that are well-defined.

!
Caution Searching should be handled carefully.

LOVELY PROFESSIONAL UNIVERSITY 171