Page 70 - Introduction to AI Robotics

2.3 2.3 Closed World Assumption and the Frame Problem 53
Closed World Assumption and the Frame Problem
CLOSED WORLD Strips sensitized the robotics community to two pervasive issues: the closed
ASSUMPTION world assumption and the frame problem. As defined earlier, the closed world
FRAME PROBLEM
assumption says that the world model contains everything the robot needs to
know: there can be no surprises. If the closed world assumption is violated,
the robot may not be able to function correctly. But, on the other hand, it is
very easy to forget to put all the necessary details into the world model. As a
result, the success of the robot depends on how well the human programmer
can think of everything.
But even assuming that the programmer did come up with all the cases,
the resulting world model is likely to be huge. Consider how big and cum-
bersome the world model was just for moving between 2 rooms. And there
were no obstacles! People began to realize that the number of facts (or ax-
ioms) that the program would have to sort through for each pass through
the difference table was going to become intractable for any realistic appli-
cation. The problem of representing a real-world situation in a way that was
computationally tractable became known as the frame problem. The oppo-
OPEN WORLD site of the closed world assumption is known as the open world assumption.
ASSUMPTION When roboticists say that “a robot must function in the open world,” they
are saying the closed world assumption cannot be applied to that particular
domain.
The above example, although trivial, shows how tedious Strips is (though
computers are good at tedious algorithms). In particular, the need to for-
mally represent the world and then maintain every change about it is non-
intuitive. It also illustrates the advantage of a closed-world assumption:
imagine how difficult it would be to modify the planning algorithm if the
world model could suddenly change. The algorithm could get lost between
recursions. The example should also bring home the meaning of the frame
problem: imagine what happens to the size of the world model if a third
room is added with boxes for the robot to move to and pick up! And this is
only for a world of rooms and boxes. Clearly the axioms which frame the
world will become too numerous for any realistic domain.
One early solution was ABStrips which tried to divide the problem into
multiple layers of abstraction, i.e., solve the problem on a coarse level first.
That had its drawbacks, and soon many people who had started out in ro-
botics found themselves working on an area of AI called planning. The
two fields became distinct, and by the 1980’s, the planning and robotics re-
searchers had separate conferences and publications. Many roboticists dur-