Doğrusal olmayan planlamaya yeni bir yaklaşım

Abstract

Bu çalışmada bir doğrusal olmayan hiyerarşik planlama sisteminin geliştirilmesi ele alınmıştır. Yapay Zeka biliminin önemli konularından biri olan planlama alanında hedef, belli bir ilk dünya durumundan bir son duruma geçişi sağlayacak eylemler (hareketler) dizisini üretmektir. Bu planın daha sonra bir robota, bir üretim sistemine veya başka bir yürütme birimine geçirildiğinde dünya üzerinde gerekli değişikliklerin yapılacağı varsayılır. Bir planlama sistemi, bir durum uzayı tanımlar ve bu uzay içinde çözüm olarak tanımlanmış bir noktayı arar. Bununla birlikte planlama sistemleri, durum uzayını tanımlama biçimlerinde farklılaşırlar. Araştırma noktalarını, dünyanın değişik anlardaki durumuyla özdeş leş t iren ve başlangıç durumuyla son durum arasındaki farkı azaltacak şekilde operatör dizilerini deneyen doğrusal planlayıcıların aksine doğrusal olmayan sistemler arama uzayını kısmen tamamlanmış planlar olarak tanımlarlar. Bu uzaydaki herhangi bir nokta uygulanabilir bir plan dönüşümü kullanılarak (eylemin daha derin ayrıntı düzeyinde açılımının yapılması, paralel eylemlerin sonuçları arasındaki çatışkıların ortadan kaldırılması, vs.) bir başka noktaya dönüştürülür. Doğrusal olmayan planlar sonuçta maksimum paralelliğe olanak tanıyan planların üretilmesini de sağlar. Bu çalışmada uygulama alanı olarak çok sayıda oda/masa arasında hareket edebilen ve bu odalardaki/masalardaki blokların yerlerini değiştirme yeteneğine sahip robot kolları için plan üretilmesi konusu seçilmiştir. TOWERS adı verilen ve PROLOG dilinde hazırlanan planlayıcı ile doğrusal olmayan hiyerarşik planlar oluşturulmaktadır. NOAH ve NONLIN gibi genel amaçlı planlayıcılarda karşılaşılan ve paralel eylemler arasında yeni sıra bağlantıları eklenmesine yol açan çatışkıların, hedef durumun yeni bir formülasyonu oluşturularak açılımlar yapıldıkça kendiliğinden ortadan kalkması sağlanmıştır. Böylece doğrusal olmayan planlayıcılardaki planlama ağı eleştirisi aşaması benzer paralel kolların birleştirilmesi işlemine indirgenebilmiş tir.

Planning is a major research area in Artificial Intelligence. In nature, life forms of high level must be able to anticipate the future and form plans of action to achieve their goals. Reasoning about actions and plans can thus be seen as fundamental to the development of intelligent machines that are capable of dealing effectively with real-world problems. A planning system has to describe a set of actions (or plan) which can be expected to allow the system to reach a desired goal. Ideally, the set of actions so produced is then passed on to a robot, a manifacturing system or some other form of effector, which can follow the plan and produce the desired result. The plan generated will be composed out of operator schemata provided to the system for each domain of application. A problem is characterized by an initial state and goal state description. The initial state description tells the planning system the way the world is "right now". The goal state description tells the planning system the way we want the world to look when the plan has been executed. The world in which planning takes place is often called the application domain. The goal state description is sometimes referred to as "the goal". In many systems, a goal may be transformed into a set of other, usually simpler, goals called " sub-goals". The traditional approach has been to consider that, at any given moment, the world is in one of a potentially infinite number of states or situations. A world state may be viewed as a snapshot of the world at a given instant of time. A sequence of world states is usually called a behavior. The world can change its state only by an occurrence of an event or action. An action is a special kind of event - namely, one that is performed by some agent, usually in some intentional way. VI Operator schemata characterize actions. Schemata primarily describe actions in terms of their preconditions and effects. Plans are built out of these operator schemata. Each operator schemata characterizes a class of possible actions, by containing a set of variables which can be replaced by constants to derive operator instances that describe specific, individual actions. In this work, the term operator is referred to stand for both operator schemata and operator instances. An action which the planner considers to be directly executable is a primitive action. A plan is an organized collection of operators. A plan is said to be a solution to a given problem if the plan is applicable in the problem's initial state and if after plan execution, the goal is true. The inputs to a typical Artificial Intelligence planning system are a set of operator schemata and a problem that is characterized by an initial state description and goal. The output from the planner is a plan which satisfies goal under projection. The process connecting the input and output is known by various names. Common names are plan generation, plan synthesis and plan construction. A planner is called domain independent in the sense that the plan representation language and plan generation algorithms are expected to work for a reasonably large variety of application domains. There are many different aspects of planning that one could attempt to formalize. The representation of the world and the representation of actions have received the most attention. Another central area of planning in need of formal analysis concerns the issues of search (Chapman, 1987). Research in formal models view planning as a reasoning process within some mathematical language, typically a logic of some sort. These models allow one to consider how planning systems may be extended or integrated into more general reasoning systems. To deal with non-toy worlds, a planning system may need to support common-sense reasoning about the world, reasoning about natural processes, causal effects, other agent's actions and motivations as many other issues. vii A basic representation technique, which has been most influential in the systems built to date, is the STRIPS state-based representation. These systems maintain a database of atomic propositions that represent a state of the world at a particular instant of time. As such, the propositions are atemporal and represent static properties of the world. Actions are not explicitly represented in the world representation - i.e. as part of the state. Rather actions are state-transformation operators, which map a state capturing the world before the action to a state immediately following the action using syntactic transformations. These transformations are defined by specifying the explicit manipulation of the assertions in the database : an action's effects specify what formulas to delete from the initial database and which formulas to add. Succesful use of this representation depends on making several very restrictive assumptions about the domains, namely: - Only one action can occur at any time; - Nothing changes except as the result of the planned actions; - Actions are effectively instantaneous (since nothing may happen or change while they are being performed ). Although STRIPS representation is almost powerful in domains where these assumptions hold (as in the domain of this work), it is unsufficient for dealing with real- world problems. Complex interactions between the actions and the world are simply not expressible. The situation calculus is a considerably more powerful representation that explicitly includes actions in the representation. A situation is a complete snapshot of the world at some instant in time, essentially an abstraction of the STRIPS state. Since situations are infinite, they are not explicitly describable by listing all the propositions as in the state-based approach. Instead, the situation calculus provide a language for partially specifying knowledge about a situation. Situations are objects in the domain and described by terms in logic. They define a notion of fluents, which are functions operating on situations. There is no assumption that nothing changes except for the effects explicitly indicated in the action definition. While this allows richer problems and plans to be described, it opens the door to a wide range of new viii problems often commonly referred to as the "frame problem". The more complex the interactions allowed between actions, the more difficult is to precisely state the necessary prerequisites of an action or predict the effects of an action. A planner is organized so that it defines a search space and then seeks a point in that search space which is defined as asolution. Planners differ as to how define their search space. Some (most of the pre-1975 planners) define points in the search space as "states" of the application's world at various times. This "world state" can be traversed by applying any applicable operator to some chosen state leading to a different point in the search space. A problem solution can be defined as a sequence of operators that can traverse the search space from some initial state to some state defined as satisfying the goal. Thus, a state-space plan contains descriptions of states of the world the plan is to be executed in, and move operators which correspond to the actions to be carried out to execute the plan. A state-space solution is trivial to recognize: it is quite simply a path from some initial state to a state satisfying the goal specification. Other (most of the post-1975) planners define points in the search space as partially elaborated plans. One point in this space is changed into another using any applicable planning transformation such as the expansion of an action to greater level of detail, the inclusion of an additional ordering constraint between actions to resolve some interaction between effects of unordered actions, etc. Given some initial (skeleton) plan defining a point in this "partial plan search space", a sequence of plan transformations must be applied which lead to fully detailed plan that satisfies the goal. A plan is considered to be complete when all of the goals can be realized as a set of primitive actions. Systems which search through the space of partial plans have typically represented plans as an "action- ordering" in which the actions, described by operators, are strung together with temporal ordering relations. Action-ordering plans describe the relationships among actions directly, rather than through states and predicates contained within states. ix In an action-ordering representation a plan need not completely specify the conditions that each action affects. The plan can simply order two actions without specifying intermediate states. In contrast, state-based plan structures typically require complete specification of these intermediate states. This is particularly difficult for use in describing complicated causal and temporal relationships between actions. Thus, many complex domains are quite difficult to encode using a state-based approach and action-ordering approaches have become the more generally used technique. Nonlinear planners allow the partial plans formed during the search to be arbitrary partial orders over plan elements. Nonlinear planners therefore do not have to commit themselves prematurely to a specific linear order of actions and can get by with less backtracking than otherwise. The method of hierarchical planning is first to construct an abstract plan in which the details are left unspecified, and then to refine these components into more detailed subplans until enough of the plan has been elaborated to ensure its success. The advantage of this approach is that the plan is first developed at a level at which the details are not computationally overwhe lming. A nonlinear hierarchical planner for robot tasks is presented. The domain consists of several rooms or tables. Each room( table) contains a collection of blocks. Operators have been defined that model the robot's ability to pickup blocks, to bring them into another room (table) and to put them on other blocks. In contrast to general purpose nonlinear planners like NOAH and NONLIN which have to deal with conflicts between parallel goals/actions by adding partial order relations to planning network, TOWERS (the planner) first re-formulates the final situation by 'tower' predicates, essentially a method of using higher level of goals of which expansions introduce ordering constraints directly. Critic of eliminating redundant parallel branches must still be achieved on each cycle, but the need of detecting/correcting interactions due to undetermined ordering relations is avoided as well as the need of keeping a few complex look-up tables.