Navigation – Plan du site

AccueilRubriquesSystèmes, Modélisation, Géostatis...1997The use of distributed artificial...

1997
20

The use of distributed artificial intelligence techniques to investigate the roles of Cartesians and stochasts in cooperative problem solving

Application de l'intelligence artificielle distribuée à l'étude des comportements de coopération entre des acteurs cartésiens ou désordonnés
Paul Jeffrey

Résumés

Cet article décrit un travail en cours élaborant un programme de simulation informatique afin d'étudier comment des acteurs ayant des stratégies différentes peuvent contribuer à la résolution de tâches. Le modèle emploie des techniques d'intelligence artificielle distribuée (IAD) et est conçu pour appliquer des notions évolutionnistes à des problèmes économiques, sociaux ou institutionnels. On décrit d'abord le contexte de la recherche en soulignant l'intérêt du modèle en tant qu'application de l'IAD à des questions d'aménagement concernant les économistes, les géographes et les sociologues. La conception technique du modèle est brièvement présentée, ainsi que les résultats de simulations comparant les performances d'agents cartésiens ou au comportement plus aléatoire.

Haut de page

Texte intégral

Background to development of the simulation tool

1Recent advances in computer modelling techniques, particularly within the fields of Distributed Artificial Intelligence (DAI) and Evolutionary Computing, are opening up new opportunities for researchers in a variety of fields. The application of DAI techniques can be classified into two domains. The first of these concerns the search for effective and efficient methods and architectures for distributed problem solving in computational settings (Levi, 1989; Bond & Gasser, 1988). The second domain involves the use of a DAI approach (mostly in the form of simulation) to investigate the dynamics of behaviour between individuals and groups of individuals, characterised as human-actors or agents. Such investigations are commonly concerned with issues of co-operation, adaptivity, and group dynamics in social, economic and organisational settings. It should be noted here that there is significant cross-fertilisation between these areas, providing opportunities for emergent research topics and applications (for example see Clark & Smyth, 1993). Whilst the DAI approach is still in its infancy as a distinct field of research, there are already a range of applications that reflect the new opportunities outlined above. For example, the use of multi-actor simulations to study anthropological and socio-cultural, and spatial development is providing new insights into issues of ranking, specialisation, and territoriality in prehistoric hunter-gatherer societies.(Doran & Palmer, 1991).

2The foundation of the work presented here is provided by the second DAI research domain outlined above (e.g. that of simulating multi-agent systems in a social, organisational or economic context). In particular, the work of Huberman & Glance (1993) and Huberman (1988) at Xerox's Palo Alto Research Centre, and of the researchers at the Santa Fe Institute (e.g. Kurz, 1991) provide challenging starting points for further work into issues of diversity, co-operation and resiliency in multi-actor environments.. Much of this work has roots in earlier, more well known, attempts to adopt evolutionary analogies to social and economic problems (e.g. Coll & Hirshleifer, 1988), and their output has implications for organisation theory, social policy, economics (in particular behavioural economics), and industrial policy. Developments in the field of DAI are particularly relevant to these areas of research as it constitutes a new approach to the examination of several classes of problem.

3Investigations of social, economic, organisational and spatially distributed processes have traditionally been caught in something of a methodological dilemma concerning relevant levels of aggregation. To state this problem briefly; as the level of aggregation increases so lower level characteristics and patterns need to be assumed or averaged out so as to make the analysis either computationally efficient or conceptually manageable. DAI overcomes this restriction as it enables lower levels of structural granularity and detail to be maintained whilst allowing macro level attributes to be investigated. Simulations can thereby capture both micro (individual / behavioural) and macro (communal / interactive) characteristics within one model structure. The opportunities that such a modelling framework provides for the investigation of both structural and process aspects of multi-actor systems constitutes the motivation for the work reported here.

4The particular issues that will be investigated with the simulation model are emergent from the application of evolutionary analogies to social, economic and organisational systems. The use of parallels from the natural world in other fields of investigation is not a new phenomenon. Indeed, both Adam Smith (economics) and Ludwig von Bertalanffy (systems theory) were greatly influenced by the natural world as a template for their ideas. However, the use of biological, and more relevantly here, of evolutionary, analogies has increased in recent years under the influence of developments in the field of Self-Organising systems (Kampis, 1990; Kauffman, 1993) and a general trend towards a more 'gaia centred' approach to problem solving and planning. Furthermore, the development of fundamentally new types of tools and techniques by the Artificial Intelligence community has promoted renewed interest in many evolutionary aspects of organisational and social behaviour that were previously difficult to investigate. Specifically, the areas of interest include the following: (N.B. the term 'community' is used generically here to denote any collection of individuals and may include commercial, social, institutional or economic groupings).

  • The influence of behavioural traits such as selfishness, altruism, competition, co-operation, specialism, and generalism on the performance of goal seeking communities.

  • The benefits / costs of diversity in communities and the interactions between different levels of diversity at different levels of community aggregation.

  • The dynamics of co-operation in communities.

  • The influence of diverse problem solving approaches (e.g. cartesian verses stochastic) on community problem solving performance.

  • The performance of different community problem solving strategies under conditions of non-stationary problem solution (i.e. where the objective function is dynamic).

5These areas of interest can be used as the basis for a set of research questions, the investigation of which will provide useful data to inform social, industrial, and economic policy making.

Simulating Communities of Artificial Actors

6As mentioned above, there is a wide spectrum of subjects currently being addressed by the use of DAI techniques. A distinct sub-group of these involves the simulation of groups of actors or agents in communities, and is referred to by a variety of terms including 'Artificial Societies' (Gilbert, 1991), 'Artificial Adaptive Agents' (Holland & Miller, 1991), and 'Artificial Ecologies', (Assad & Packard, 1992; Huberman & Hogg, 1988). Contributions to this field of research are also forthcoming from those engaged in Evolutionary Computing, where evolutionary strategies are investigated under varying environmental conditions. The simulation model described here is complimentary to and has been informed by all these contributions.

7The work reported below can be seen as an attempt to meld the DAI and evolutionary approaches to address some research issues that are extant in both fields and which call for cross-fertilisation of techniques to achieve new insights into the relevant problem set. For example, the time scales over which phenomena such as diversity and adaptation have a distinguishable effect on many communities are often extended (i.e. beyond the life expectancy of any individual within the community). Therefore, simulating some transfer of knowledge or other characteristics between generations of individuals is a desirable model attribute. Evolutionary computing techniques have the tools to accomplish this via the use of genetic algorithms. However, Evolutionary Computing techniques do not allow for the richness of individual attributes that are possible with DAI approaches. Hence, a hybrid approach is needed that enables the benefits of each technique to be exploited.

8The broad aim of the modelling activity is to develop a (generic ?) simulation model that can be used to investigate some of the questions raised by the application of evolutionary analogies to the sustainability of social, organisational and economic systems. By analogy, the model comprises a number of individuals that seek to solve a problem based on a popular children's game (the solution to the game can remain static or be changed so as to provide a dynamic problem). The individuals use a variety of strategies to address the game problem and formulate conjectures about the solution based on their own memory of their previous actions and, if they have formed coalitions, the memories of other individuals. Feedback from the environment is simulated by information passed to the individual concerning the accuracy of its conjecture. A payoff is also associated with each conjecture, reflecting the 'goodness of fit' between conjecture and solution. This framework falls within a group of models where individual actors are considered 'cognitive' (as described in Sichman et al [1992]), Such actors possess both an explicit representation of their environment and the ability to reason about their actions.

9An overview of the computer model's structure is presented in Figure 1 (below)

Figure 1

10As a problem solving task, the actor(s) are confronted with an augmented version of a popular children's game. This game involves 'Player A' attempting to ascertain the sequence of a row of 4 coloured pegs that have been hidden from view by 'Player B'. After Player A has made a guess, Player B passes information back to Player A of the following two types

  • How many pegs are the correct colour but in the wrong place.

  • How many pegs are the correct colour and in the right place.

11In the traditional version of the game, only one peg of each colour (there are six colours altogether) can be used for the problem sequence.

12There are a number of strategies that can be adopted for developing conjectures about the sequence of pegs. These include a purely random approach, and an approach based on ensuring the consistency of conjectures with information concerning the accuracy of previous conjectures. Additionally, the available strategies may themselves be used in a random way so that an actor uses a mix of strategies to formulate a conjecture.

13For the purposes of the research reported here, this basic form of the game has been enhanced to expand the range of variables. Furthermore, the solution can be changed periodically to simulate a non-stationary objective. Agent design has proceeded along an incremental path using an Object Oriented Programming Language approach. Figure 2 depicts the core elements of each agent.

Figure 2

14As can be seen from Figure 2, each agent possesses the following attributes:

  • A set of algorithms that govern the internal co-ordination of the actor's own actions and manages co-operative actions with other actors.

  • Memory of its own previous conjectures and the associated information feedback and payoff.

  • Memory of other actors previous conjectures, associated information feedback and payoff (dependent on being part of a co-operative effort).

  • A conjecture formulation strategy.

  • An identification number.

Stochasts and Cartesians

15In order to briefly demonstrate the type of dynamics which can be investigated with the model, we report the results of a set of simulations which investigate the roles of 'Stochasts' and 'Cartesians' in co-operative problem solving activities. The significance of the roles of Stochasts and Cartesians as behavioural groups within a community has already been alluded to above. In brief, community resilience through adaptivity is a central component of sustainability. Knowledge of our environment provides us with information concerning threats and opportunities. Such knowledge is of little use however unless we can exploit it. Policies for managing change require information concerning both elements of sustainability; the nature of the threat, and the response characteristics of those exposed to possible damage.. These policy relevant insights have led us to propose a general theoretical model of the determinants of resilient adaptive communities (see Jeffrey & Lemon, 1996). In detail, the theoretical model of community adaptivity is centred around the dynamics between environment, risk taking behaviour and the socio-economic networks that govern relationships between risk takers (Stochasts) and the reactive mass of the community (Cartesians). The two terms, 'Stochasts' and 'Cartesians' are intended to emphasise a broad distinction between knowledge seekers and knowledge exploiters (although the precise behavioural traits associated with these terms will be context specific). Figure 3 depicts a generic representation of these dynamics.

Figure 3

16In process terms, the dynamics of the model presented in Figure 3 can be characterised as complex but not complicated. Resilience is characterised by the maintenance of a Stochastic potential (flexibility), the ability of Cartesians to exploit identified opportunities (adaptability), and crucially, socio-economic structures that maintain an equitable and effective balance between the two functions. Risk takers are thereby the driving force of adaptive change; the broad mass of reactive community members moving in to exploit new knowledge after the utility (not necessarily economic ?) of the new opportunity has been proven. It is against this theoretical background that the simulation model has been used to investigate the dynamics of co-operative problem solving.

Simulation results

17The results presented below were generated from a sequence of model validation exercises carried out to investigate the behaviour of the simulations. Each combination of agent behaviour and problem configuration was simulated 100 times to enable a profile of the agents problem solving performance to be constructed. Figures 4 and 5 show how the number of attempts and time taken to identify a correct conjecture varies in relation to problem solving type (Stochast or Cartesian) and complexity of the problem. The Stochasts are doing no more than guessing a sequence of peg colours and positions at each time step by randomly selecting a conjecture and checking to ensure that it has not been proposed before. However, the Cartesians are using information regarding the results of previous conjectures to improve the accuracy of current ones. The Cartesian actor in the simulation model uses an advanced rule based reasoning technique to construct and test the validity of a conjecture. Instead of randomly selecting a string and then testing it, the Cartesian actor works by selecting the best previous conjecture and using it as a starting point for the current conjecture The number of pegs contained in the target sequence constitute the 'solution size' for the problem whilst the number of possible colours which any one peg can assume constitutes the 'block size'.

Figure 5

18For purposes of model verification, the trends depicted in Figures 4 and 5 have been compared with functions for similar processes found in the field of communication studies and found to correlate satisfactorily. As we would expect, the Stochastic agents perform less consistently and with significantly less success than their Cartesian counterparts. However, the data presented in these figures are from two specific (but typical) simulations. Other simulations showed that the Stochasts were capable of, though unlikely, to solve the problem both in less time and with less conjectures than the Cartesians.

19The following set of results (Figures 6 & 7) depict the influence of information sharing between the Stochast and Cartesian agents. The data presented in Figure 6 shows the total number of conjectures to find a solution for a Cartesian agent acting alone, a pair of co-operating Stochast and Cartesian agents and a pair of co-operating Cartesian agents. For this simulation, the Cartesian was allowed access to another Cartesian and a Stochast's game histories in terms of conjecture formulation and feedback. Total number of conjectures to solution (including those made by the Stochast) are not significantly greater than for the Cartesian agent acting alone (Figure 6). However, in terms of the time taken to reach a solution, the results show more variation and less consistency of performance. For example, for several of the block and solution sizes, the average combined time for solution is less than the average Cartesian time for solution.

Figure 7

20Finally, we used the model to investigate the effects of error-making on the performance of the Cartesian agent. Figure 8 shows the data generated from two runs of the simulation; the first of which allows the Cartesian agent to operate normally whilst the second forces an error making behaviour where there is a 20% chance that 10% of the coding sequence that represents a conjecture will be corrupted.

Figure 8

Next steps

21The simulation model described here is currently being refined and transferred to a different computer platform to enable further development and phenomena investigation. Plans for future work include:

  • Provision of a spatial element to the simulation to allow investigation of patterns and networks of co-operative problem solving. Investigation of the dynamics between location, knowledge and access to information would thereby also be possible.

  • Additional work on the roles of imperfect information and error making.

  • Addition of a cost function to the agent modules so that the pricing of information and its relative value to different types of agent can be investigated.

  • Inclusion of additional problem solving types (hybrid ?) and multi-function problem domains.

Haut de page

Bibliographie

Assad, A.M. & Packard, N.H. (1992) 'Emergent Colonization in an Artificial Ecology.' Proceedings of the first European Conference on Artificial Life, 143-152.

Bond, A.H. & Gasser, L. (eds) (1988). 'Readings in distributed Artificial Intelligence.' Morgan Kaufmann Publishers. San Mateo. CA.

Clarke, A.A. & Smyth, M.G.G. (1993) 'A cooperative computer based on the principles of human cooperation.' International Journal of Man-Machine Studies. Vol 38. No 1, 3-22.

Coll, M and Hirschleifer, J. (1988) "What Strategies can Support the Evolutionary Emergence of Cooperation?" Journal of Conflict Resolution. Vol. 32 No 2, 367-398

Doran, J.E. & Palmer, M. (1991) 'Modelling Prehistoric Sociocultural Trajectories.' Proceedings of the First European Symposium on Computing in Archeology.' Saint-Germain-en-Laye. France. November.

Gilbert, G.N. (1991) 'Artificial Societies.' Inaugural Lecture. University of Surrey. 6th November.

Holland, J.H. & Miller, J.H. (1991) 'Artificial Adaptive Agents in Economic Theory.' AEA papers and proceedings. Vol 81. No 2, 365-370.

Huberman, B.A. (1988) 'The Ecology of Computation.' North-Holland. Amsterdam.

Huberman, B.A. & Glance, N. (1993) 'Diversity and Collective Action.' in Haken, H, & Mikhailov, A. (Eds). 'Interdisciplinary Approaches to Complex Non-Linear Phenomena.' Springer. Berlin.

Huberman, B.A. & Hogg, T. (1988) 'The Behaviour of Computational Ecologies,' in Huberman, B.A. 'The Ecology of Computation.', 77-115. North Holland. Amsterdam.

Jeffrey,P. & Lemon, M. (1996) 'Understanding the Dynamics of Sustainable Communities: Stochasts, Cartesians and Social Networks.' Paper presented at 'Ecology, Society and Economy' the inaugural conference of the European Society for Ecological Economics. Versailles. France. May 23-25th 1996

Kampis, G. (1990) 'Self Modifying Systems in Biology and Cognitive Science: A New Framework for Dynamics, Information and Complexity.' Pregamon Press. Oxford.

Kauffman, S.A. (1993) 'The Origins of Order: Self Organisation and Selection in Evolution.' Oxford University Press. Oxford. 1993.

Kurz, M. (1991) 'On The Structure And Diversity Of Rational Beliefs' Santa Fe Institute Working Paper 91-02-013.

Levi, P. (1990) 'Architectures of Individual and distributed Autonomous Agents.' in Kanade, T. et al (Eds). 'Intelligent Autonomous Systems 2.' 315-324. The IAS Foundation.

Sichman, J.S. Demazeau, Y. & Boissier, O. (1992) 'When can Knowledge-Based Systems be Called Agents ?' in Proceedings of the 9th Brasilian Symposium on Artificial Intelligence Brasilian Computing Society. 172-185.

Haut de page

Pour citer cet article

Référence électronique

Paul Jeffrey, « The use of distributed artificial intelligence techniques to investigate the roles of Cartesians and stochasts in cooperative problem solving », Cybergeo: European Journal of Geography [En ligne], Systèmes, Modélisation, Géostatistiques, document 20, mis en ligne le 26 mars 1997, consulté le 03 décembre 2021. URL : http://journals.openedition.org/cybergeo/5554 ; DOI : https://doi.org/10.4000/cybergeo.5554

Haut de page

Auteur

Paul Jeffrey

P.J.Jeffrey@cranfield.ac.uk
International Ecotechnology Research Centre, Cranfield University, United Kingdom

Haut de page

Droits d’auteur

Licence Creative Commons
La revue Cybergeo est mise à disposition selon les termes de la Licence Creative Commons Attribution 4.0 International.

Haut de page
Rechercher dans OpenEdition Search

Vous allez être redirigé vers OpenEdition Search