Mobile

12 pages
10 views

A knowledge-level model of co-ordination

of 12
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
A knowledge-level model of co-ordination
Transcript
  A K NOWLEDGE - LEVEL M ODEL OF C O - ORDINATION * Sascha Ossowski and Ana García-Serrano Department of Artificial IntelligenceTechnical University of MadridCampus de Montegancedo s/n28660 Boadilla del MonteMadrid, SpainTel: (+34-1) 336-7390; Fax: (+34-1) 352-4819{ossowski, agarcia}@dia.fi.upm.es Abstract . Co-ordination is one of the central research issues in Dis-tributed Artificial Intelligence. Most of the efforts in designing co-ordina-tion mechanisms set out from an agent-centred point of view: they see theindividual actor with its local beliefs and reasoning capabilities as thefoundation of all system properties. Our thesis is that co-ordination is bestmodelled from an environment-centred, social perspective, that considersthe whole, situated system as the starting point of any analysis. We arguethat this stance is reflected in Clancey’s modification of the Knowledge-level hypothesis. On the basis of this modified hypothesis we introduce adistinction between co-ordination at the Knowledge- and at the Symbol-level. Finally, we present a Knowledge-level model of co-ordination andillustrate it by specifying the co-ordination processes of an intelligent traf-fic management system. 1 Introduction The phenomenon of co-ordination is being tackled by a variety of scientific disci-plines. Sociologists, by means of observation, want to explain how particular co-or-dination mechanisms work within a certain society of people and why they emerged.Economists study the market as a particular co-ordination mechanism. OrganisationalTheorists not only try to explain the co-ordination behaviour of an organisation, butalso aim to predict its future behaviour, assuming the validity of a certain co-ordina-tion mechanism [7].Within Computer Science, the area of Distributed Artificial Intelligence (DAI) isdeeply concerned with the problem of co-ordination. Its focus is different from thosedescribed above, as it aims to design co-ordination mechanisms for groups of artifi-cial, (boundedly) rational agents. Following the habits of traditional Artificial Intelli-gence, which was moved by the desire to model individual intelligence, DAI has putthe individual agent in the centre of analysis of distributed intelligent systems. Al-though the boundaries of research agendas in DAI have become blurred, two majorpaths, represented by the Multi-agent Systems (MAS) and the Distributed ProblemSolving (DPS) communities, can be distinguished [9]. *This work was supported by the Human Capital and Mobility Program (HCM) of theEuropean Union, contract ERBCHBICT941611  The MAS community within DAI focuses on the development of Agent-Technology.Formal theories are developed to specify requirements for agent behaviour, and agentarchitectures constructed to operationalise it. Following Dennet’s philosophicalstance, agents are usually seen as intentional systems and described by “mental” ter-minology [23]. This leads to the so-called BDI-architectures (belief, desire, intention):all agent actions srcinate from a current set of beliefs (knowledge) and desires (goals),which are linked together by intentions. Co-ordination here is an emergent phenome-non: agents generate individual commitments on the basis of their local beliefs andcommunicate them to other agents, which then change their beliefs, due to their reli-ance on certain actions to be performed by the former. Gasser [11] notes, that there isa circularity in this approach to model co-ordination: facts and beliefs provide com-mitments, but they are themselves commitments.Contrary to MAS, which in general makes assumptions about the properties of indi-viduals and then considers what properties will emerge internally from among theagents, the DPS community deals with macro-phenomena more directly. DPS sys-tems also assume some basic internal properties, such as benevolent agents and com-mon goals, but are primarily concerned with how to achieve desired external properties(robustness etc.) in line with these assumptions [9]. Agent co-ordination strategies aredeveloped, and their effectiveness measured in terms of the degree to which theyachieve the required external properties. Co-ordination in DPS architectures is usuallyconcerned with reducing local control uncertainty, which results from partial and pos-sibly conflicting views of the agents of the global system state. Thus, in DPS sys-tems co-ordination is not driven by external, environmental uncertainty, but dependsto a greater extent on the internal uncertainty, which is due to the (designed-in) distri-bution of control. 2 Co-ordination from a Social Perspective Within the traditional DAI perspective described above both communities try to ex-plain co-ordination behaviour in terms of the attributes of individual agents. Such anagent-centred view distracts from the simple truth, that co-ordination primarily is asocial phenomenon: it is a global property of a system and should be characterised interms that abstract from the properties of the system’s components (i.e. its con-stituent agents). In Sociology and related sciences, such a social perspective on co-ordination, and on the nature of intelligent behaviour in general, is not new. For in-stance, by the early years of this century Mead had already stated: We are not, in social psychology, building up the behaviour of thesocial group in terms of the behaviour of the separate individualscomposing it; rather we are starting with a given social whole of complex group activities, into which we analyse as elements thebehaviour of each of the separate individuals composing it. [...]. For social psychology, the whole (society) is prior to the part (theindividual) [10]This viewpoint leads to a characterisation of co-ordination in terms of the relationsthat exist between an entire system and its environment. It stresses the simple fact,that all real systems are situated  . The behaviour of an intelligent system can only beunderstood by focusing on its interactions with the real world in a particular situation  in which it has to act. Consequently, a model of co-ordination must set out by relat-ing a system’s co-ordination behaviour to the characteristics of its environment.As a prerequisite for this enterprise, the precise meaning of the term under study needsto be further clarified. For this purpose, we adopt the definition of Malone and col-leagues [13], who identify co-ordination with the act of managing dependencies be-tween activities . This stance already includes many aspects of a social perspective onco-ordination.Firstly, it does not require several actors to be present in order for the phenomenon of co-ordination to arise. Instead, co-ordination is seen as a result of performing several activities , which need not but may be carried out by the same actor. 1 Secondly, it puts emphasis on the “situatedness” of co-ordinated systems, due to thefact that dependencies arise as a consequence of activities being performed in the sameenvironment. Activities interact by referring to the same environmental entity. This isoften a physical, usually limited resource, which has to be shared by a set of activities(i.e. the processor of a multi-tasking workstation), or which is produced by one activ-ity and “consumed” by another (i.e. the carburettor in a motor assembly process).However, “immaterial” information resources, such as an interface specification orknowledge about possible task decompositions, can also be related to a system’s ac-tivities, and consequently need to be considered, too.Finally, the management of the dependencies, as mentioned in the definition, consistsof the exhibition of certain co-ordination behaviour in response to them. For this, theenvironment has to be perceived, dependencies detected and co-ordination behaviour as-sociated. This process suffers from the uncertainty which is intrinsic to co-ordination,as the perception of the environment may be ambiguous, a dependency not detected orout of date due to a change in the environment, outcomes of actions unpredictableetc.. This uncertainty is implied by the environment (or by the system’s global per-ception of the environment), but not by the incomplete views of the overall problem-solving state that some components of the system may have.From a social perspective, co-ordination can only be modelled by dropping the closed-systems assumption and seeing “situatedness” as the essential system property. A sys-tem’s co-ordination behaviour is primarily determined by its environment, which isthe source of dependency and uncertainty, in relation to which it envisions and per-forms its actions. 3 Modelling Co-ordination at the Knowledge-level The Knowledge-level hypothesis has been introduced by Newell [16] as an attempt toclarify the relation between knowledge on the one hand and symbolic representationson the other. It claims that there is a computer systems level lying directly above theSymbol-level (SL). This Knowledge-level (KL) is characterised by knowledge as themedium and the principle of rationality as the law of behaviour. A KL-description of asystem consists of the knowledge and the goals, that an observer ascribes to an“agent”, in order that it can exhibit an observed behaviour by applying its knowledgeaccording to the principle of rationality. Such a description is radically different from 1This accounts for the common sense meaning of the term, according to which one soleagent can act in an “uncoordinated” fashion.  traditional viewpoints, in that it constitutes a (subjective) abstraction, made by an ob-server, and thus completely ignores any considerations concerning architectures orphysical structures. In the following we will apply the KL-hypothesis to the phenom-enon of co-ordination. 3.1 Co-ordination and the Knowledge-level Newell’s KL-hypothesis has been shown to be useful in many areas of Artificial Intel-ligence, such as knowledge acquisition, knowledge-based systems construction etc.[17]. Dietterich first applied it to machine learning. He distinguishes Knowledge-levellearning, where a system acquires a new KL description, from Symbol-level learning,where the system learns only to evoke the knowledge it already has faster and more re-liable [8]. Schreiber and colleagues transfer the KL-hypothesis to control [19]. In theterm Knowledge-level control they include strategic knowledge in regard to task de-compositions and orderings as well as meta-knowledge about a system’s components.Symbol-level control is concerned with control issues that arise when a particular rep-resentation or AI technique is selected to realise a problem-solving component.A similar distinction concerning co-ordination is complicated by the fact that Newelldefines the observed entity, an agent, only vaguely as composed of  a set of actions, aset of goals and a body [16]. Hence, according to Newell, the term agent refers to abroad variety of things, from a simple computational process up to a complex MAS,the important point is that actions, goals and knowledge can be ascribed to it. 2 Thisraises the question, as to whether the agents in DAI are the same as the agents thatNewell refers to. We claim that, seen from a social stance, this is not the case. Thisidea is underpinned by Clancey’s modification of the KL hypothesis:  A KL description is about a situated system, not an agent in isolation.That is, the systems level being described is above that one of individ-ual agents. Therefore, a knowledge-level description cannot be identified with (isomorphically mapped to) something pre-existing inside an indi-vidual head, but rather concerns patterns that emerge in interactions theagent has in some (social) world  [2]Thus, we conceive a KL description as a characterisation of an entire system as awhole, while the system’s components, the agents, are SL entities. 3 Consequently,we can distinguish between two levels of co-ordination: Knowledge-level co-ordina-tion refers to whole systems. It is a property, that can be observed by the actions thata certain system performs, in relation to dependencies and uncertainty that exist in itsenvironment. Symbol-level co-ordination results from a specific system architecture,i.e. from the symbolic representation of the system, its internal structure. Hence, thedifferent co-ordination techniques applied in DPS to reduce a system’s internal controluncertainty, including individual commitments, exchange of meta-information etc.,are located at the SL. 2In fact, Shoham [20] notes that everything can be described using this kind of mentalterminology. The point lies in whether it is advantageous or not to do so.3As van de Velde [22] argues, in practice a KL-description usually imposes a structure onthe system’s knowledge. This might be interpreted as a set of functional KL-agents.However, these functional “agents” are the result of an observer’s description. Thus,they have no a priori characteristics and definitely no physical base at all.  3.2 A Knowledge-level Model of Co-ordinated Systems The above characterisation provides the basis for a KL-model of co-ordination. Themodel will be expressed using the KSM methodology [14,15] as a KL modelling lan-guage. In this methodology the central modelling primitive is an entity called Knowl-edge Unit (KU) , which represents a knowledge area of the system. A KU is defined bywhat it knows, described by a collection of knowledge (sub-)areas, and what it is ca-pable of, specified by a collection of  tasks . Optional Conceptual Vocabularies (CV)provide the conceptual framework, a common ontology, for the knowledge areas to beused in the KU. In the design process the entire knowledge of the system is structuredin knowledge areas, which leads to an organisation of the system knowledge in a net-work of KUs. Dynamic information is contained in information models, called stores ,which are modified by the accomplishment of tasks. The relationship between tasksand stores is specified by a task-store diagram.As shown in the KU-net of figure 1, we propose to model a co-ordinated system at theKL by means of a System KU  , whose knowledge is made up of three areas: world in-teraction, co-ordination and management knowledge. The system’s dynamics are re-alised by the operate -task, which, on the basis of the actual contents of the informa-tion models, determines which of the tasks associated to one of these knowledge areasto accomplish next.The World Interaction KU  integrates all the knowledge areas necessary for the sys-tem’s interactions with the environment. These include mere perceiving activities,that build or update the system’s model of the environment, as well as environment-manipulating actions, which are intended to change the state of the outside world in adesired way. The latter can be either problem-solving actions, such as the productionof a resource, or co-ordination actions, such as the adaptation or standardisation of aresource involved in a producer-consumer relationship.The Co-ordination KU  provides a set of co-ordination tasks, that allow for differentstyles of co-ordination. It covers two knowledge areas. The first one, integrated in the Structure Discovery KU  , builds a structured abstraction of the system’s perception.This is done by detect  -tasks that use  Detection KUs to discover dependencies. The  De- pendency CV  ontology specifies the taxonomy of dependencies, on the basis of which detect  -tasks are accomplished.It is worthwhile pointing out, that the process of structure discovery is far from beingtrivial. Consider, for instance, the detection of a new task-subtask dependency. Such afact implies the dynamic generation of a new problem decomposition. So, the struc-ture of a system’s problem-solving process is not designed-in a priori, but emergesduring problem-solving.The  Behaviour Association KU  determines which co-ordination behaviour will beshown by the system in response to the detected dependencies. The corresponding as-sociation knowledge may be either complicated inference processes, or a simpleKnowledge Base, that links every element of the dependency taxonomy to at least oneelement of the taxonomy of behaviours defined in the Co-ordination Behaviour CV  .These behaviours constitute co-ordination activities which may have mere internal ef-fects, for instance restricting the envisioned execution time of certain external actions,or may themselves be external, as for the action of adaptation or standardisation of aresource mentioned above.
Related Documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x