International Journal of Computers, Communications & Control Vol. I (2006), No. 3, pp. 5-12 From Algorithms to (Sub-)Symbolic Inferences in Multi-Agent Systems Boldur E. Bărbat, Sorin C. Negulescu Abstract: Extending metaphorically the Moisilean idea of “nuanced-reasoning logic” and adapting it to the e-world age of Information Technology (IT), the paper aims at showing that new logics, already useful in modern software engineering, be- come necessary mainly for Multi-Agent Systems (MAS), despite obvious adversities. The first sections are typical for a position paper, defending such logics from an an- thropocentric perspective. Through this sieve, Section 4 outlines the features asked for by the paradigm of computing as intelligent interaction, based on “nuances of nuanced-reasoning”, that should be reflected by agent logics. To keep the approach credible, Section 5 illustrates how quantifiable synergy can be reached - even in ad- vanced challenging domains, such as stigmergic coordination - by injecting symbolic reasoning in systems based on sub-symbolic “emergent synthesis”. Since for future work too the preferred logics are doxastic, the conclusions could be structured in line with the well-known agent architecture: Beliefs, Desires, Intentions. Keywords: Nuanced-reasoning logic, Multi-Agent Systems, Sub-symbolic infer- ences, Stigmergic coordination, Synergy 1 Introduction. From Chrysippus, via Moisil, to Agent Logics For over 40 years, determinism and bivalence of Chrysippean logic were the pillars of Computer Science; likewise, algorithms were the backbone of computer programs, complying with their etymon: pro-gramma = what is written in advance. They sufficed for both FORTRAN-like number crunching and COBOL-like business data processing. When early real-time applications (firstly, operating systems) re- quired less autistic programs, algorithms tried to adapt and bizarre terms, such as “unsolicited input”, were coined to fit the incipient non-determinism due to user free will. Bivalence not only survived, but also grew in importance strongly backed by hardware. Indeed, in the early 70’s, the role of bivalent logic transcended the borders of narrow data processing, penetrating “Computer-Aided x”, where x stays for almost any intellectual activity. Thus, “algorithmic reasoning”, instead of being perceived as a side effect of “analogue humans loosing the battle with digital computers”, became a paradigm in the very sense of Kuhn. Emerging within this “digital Zeitgeist”, nuanced-reasoning [12] was too anti-paradigmatic to redress the balance - at least in IT (besides, it was technologically useless, as most fascinating heresies). Only after the “PC-Windows-WWW” revolution was this “nuanced” kind of fuzzy logic - developed by Zadeh as “computing with words” - acknowledged as an alternative approach to software development (albeit seldom necessary). On the other hand, after a decade of success stories, within artificial intelligence (AI) - the perpetual stronghold of applied logics and symbolic processing -, expert systems (based on the Newell-Simon hy- pothesis) began to disappoint, because of their brittleness (in all nuances of the word), showing the actual limits of the symbolic paradigm. The reaction was prompt, overwhelming, and exaggerated: “GOFAI” (Good Old-Fashioned AI) has to be replaced by “BIC” (Biologically Inspired Computing), based on sub-symbolic paradigms. The most nihilist and powerful one, i.e. the ethological paradigm (based on the physical-grounding hypothesis), is, for good reasons, still in vogue. However, paradoxically, new, “much nuanced” logics are already used in modern software engineering, tending to become necessary mainly for non-trivial MAS, despite many, major, and obvious adversities. The paper aims to: a) defend not just those logics but also the inexorable need of symbolic processing, Copyright c© 2006 by CCC Publications Selected paper from ICCCC 2006 6 Boldur E. Bărbat, Sorin C. Negulescu even in systems where intelligent behaviour emerges sub-symbolically (because of its synergistic poten- tial); b) after explaining why synergy, show how it can be reached. (That is why the title contains the unusual term “(Sub-)Symbolic”.) Thus, after a short history (Section 2), the approach is rendered from an anthropocentric perspective: the agent shall behave naturally (i.e., closer to human behaviour), not the opposite (Section 3). Through this sieve, Section 4 outlines the features and symbolic mechanisms asked for by the paradigm of “computing as intelligent interaction”, based on “nuances of nuanced- reasoning”. To keep the approach credible, Section 5 sums up recent research showing how quantifiable interparadigmatic synergy can be reached - even in advanced challenging domains, such as stigmergic coordination - by injecting symbolic reasoning in systems based on sub-symbolic “emergent synthesis”. Since for future work the preferred logics are doxastic, the conclusions (Section 6) - far from being apodictic - can be structured in line with the well-known agent architecture: Beliefs, Desires, Intentions. 2 History. In Search of Synergy The research roots are in over 20 papers/articles published in 1997-2002 and synthesised in [3]. After 2002 there are two history strands having the common denominator “looking for synergy in the world of humans and agents”: • Stigmergic Coordination. After minor improvements in 2003, in [13] some (less quantifiable) synergy was achieved deviating from the biological model applied in the Elitist Ant Systems by adding symbolic processing components (firstly adapting the environment and secondly instituting limited central coordination). In [7] a refined experimental model attested that in operational research, through “stigsynergy” the same solution quality could be reached with fewer ants than used in common benchmarks, saving thus at least one order of magnitude of processing time. • Human-Agent Communication. User-avatar interaction was illustrated in medical captology, em- ploying pathematic agents as virtual therapists [4]. The framework was widened (in the con- text of broadband communication) to any anthropocentric interface in [5], focusing on the lan- guages enabled by modern multimodal interfaces. On a more abstract level, [6] showed how trans-disciplinary metaphors, applied in communication procedures, can help humanists and tech- nologists get close. 3 Approach. Towards Natural Behaviour of Artificial Entities Two perspectives guide the approach: anthropocentric systems, as non-negotiable goal, and agent- oriented software engineering (AOSE), as amendable means - depending on long-range effectiveness. (Anthropocentrism means focusing on the human being as user, beneficiary, and, ultimately, raison d’être of any application or, more general, technology [5]. Here, “anthropocentric” is synonymous to “human- centred”). The premises are: 1. Regarding the goal: • Despite their fast rising technological level, most IT applications involving intense human- computer interaction (HCI) have low degree of user acceptance, ignoring the very slogan: “computing as interaction” [1]. • That drawback holds mainly for AI systems, widening the gap between humanists and tech- nologists. • The main cause: system development is rather technocentric than anthropocentric. From Algorithms to (Sub-)Symbolic Inferences in Multi-Agent Systems 7 • The main neglected human features are: 1F) Invariants: humans are intrinsically analogue in information processing and multimodal in perception. 2F) Prevalent in HCI: humans prefer symbolic communication but sub-symbolic response. 2. Regarding the means: • The IT infrastructure is sufficiently advanced (in both facts and trends: nanoelectronics, broadband communication, semantic web, multimodal interfaces, etc.) to allow anthropocen- trism for most IT applications. • Intelligent system behaviour - whatever that could mean - becomes a crucial user expectation. Regrettably, in AI neither technology, nor design philosophy were yet able to offer it in a user-relevant manner. • Nevertheless, agent technology, as AI flagship, proved to be a significant step towards user acceptance. • AOSE is not bounded to AI, but tends to become the dominant IT development paradigm [11], [15]. While the first premises in each category are generally accepted, the last ones are debatable (e.g., A4b is rather an “author thesis” and B4 is strongly contested by object-oriented designers). The corollaries relevant for the paper are: • C1. The geometrically increasing computing power (due to Moore’s law) promotes at least five factors tending to reduce radically the role of any species of logic in IT - at least for applications affordable on usual configurations: 1. Since deterministic applications are vanishing, the conventional algorithm is not anymore program backbone. 2. Even when still useful, the conventional algorithm is not anymore the main programming instrument (being hidden in procedures easily reached in a host of libraries or being generated by 4GL). 3. In AI the symbolic paradigm is steadily replaced by several sub-symbolic ones, based on fine-grain parallelism. 4. Even when symbols are used, they are stored in and retrieved from huge and cheap memory, rather than processed through sophisticated reasoning schemes (case-based reasoning is just a blatant example). 5. Cognitive complexity of new, sophisticated logics is too high for a designer, when “cut and try” is affordable. • C2. The rules for human-agent interaction can and should be set by users (at least while we have the Demiurgic privilege of shaping agents as we like it!): 1. Since interaction is carried out through the interface, anything behind it is user-irrelevant. 2. Since natural and artificial intelligence encounter at interface level, they shall join, not col- lide. 3. To join closer to human demeanour, users should engage interface agents as naturally as possible. 4. Hence, let agents behave more and more naturally (e.g., it is not difficult to go beyond ges- tures to show emotivity, since not emotion has to be replicated, but its appearance - firstly forged, later more genuine [5]). 8 Boldur E. Bărbat, Sorin C. Negulescu 5. Since interaction involves communication, the communication procedures (the term “pro- cedures” is here a prudent, albeit partial, place holder for “language” or, even, “empathy”) must be those humans are familiar with (e.g., body language can and shall be added to verbal messages). 6. Since beside how to communicate (the vehicle), it is vital what (the message), beyond the procedures, there must be a representational compatibility between humans and agents (ex- pressed through common ontologies, primitive surrogate of a yet impossible common “Weltan- schauung”). If regarding C2.1-C2.4, the blend “symbolic/sub-symbolic” is unclear, C2.5 implies symbols, whereas C2.6 is stronger, implying symbolic inferences. At least some of them shall be based on logic(s). For short, acknowledging the decline of logic (because of C1), its necessity is asserted (in line with C2). Anyway, the role of desirable features of new logics could be credibly defended - outside large- scale systems, were the proof is futile - only comparing diverse implemented MAS designed with or without employing such logics. Because of C1.5, this is impractical. To weaken this main approach drawback, the argument is split to render two complementary paths, both based on the idea that the blend “symbolic/sub-symbolic” yields synergy: a) axiological perspective: why and what symbolic processing (Section 4, closer to a position paper); b) praxiological perspective: how can symbolic processing be added in experimental sub-symbolic models (Section 5, closer to a technical report). 4 Nuances of Nuanced-Reasoning in Human-Agent Dialogue It would be both arrogant and absurd if authors lacking educational background in both mathematics and logic would utter value judgments in these fields. Hence: • Without claiming that Moisil actually attached to “nuanced” other connotation than “fuzzy”, bear- ing in mind his gifted baroque way of catalysing brainstorming, it is legitimate to use undertones of three (partial) synonyms - “degree”, “gradation (sequence, development)”, “fine distinction” - as metaphor sources. • All assertions about existing or desirable logics mirror the angle of potential users of such log- ics, mainly in interface agents and MAS based on stigmergy. They convey “calls for help”, not requests, and are uttered as desires. • Since, as regards logics dealing with agent-related aspects, for many basic AOSE requests, Fisher’s logic [9] seems for a non-specialist by far to be the most responsive and appropriate, all desiderata below refer to it. ¥ Diversified inferences. Smith’s propositional-representation theory should be: a) revisited and thor- oughly extended; it shall include all main mechanisms (symbolic or not) employed by humans to infer and to make decisions (even “right-hemisphere based” processes, as educated guess, intuition or gam- bling); b) applied, depending on the sub-field; such mechanisms should be replicated - as “omomorph”, as adequate (not as possible!) - in agent decision making schemata. If all of them would reach the ele- gance and dependability of logic, it would be nice, but let it be yet a kind of “princess lointaine”, because in real-world systems most concepts involved tend to become blurred. For instance, even metalogic is now nuanced: soundness remains crucial (still - apart from time-critical applications - it can be cir- cumvented through revisable reasoning); completeness is more negotiable (the oversimplified solution: “otherwise, nothing happens”). ¥ “More time for agents”. Nowadays, any software piece unable to interact efficiently with unpre- dictable environments (humans included) and with its peers is hardly useful outside toy-problems. That From Algorithms to (Sub-)Symbolic Inferences in Multi-Agent Systems 9 means: parallelism, temporal dimension, non-determinism, reactivity. Corollary: any such program entity has to be implemented as execution thread (atomic, sequential, asynchronous and dynamic) [3]. To develop into an agent, the thread needs also non-trivial informational and motivational components. (However, the “dynamic component” is a treble confusing term: a) it is not a component but the very agent nature; b) the “sense of time” refers to much more than activity - e.g., “waiting” is rather inactivity; c) “dynamic activity” sounds pleonastic from any stance.). ¥ No “start” and no “synchronous agents”. If for e-commerce, it is conceivable to consider that the entire world restarts with each transaction, for process control (even for discrete manufacturing) such eternal re-birth is practically excluded. Moreover, it is against the very spirit of: a) the (still dom- inant) “client-server” paradigm (the tailor is not spawned every time a client needs new clothes); b) real-time software engineering (to react timely to environment stimuli, the thread must exist to han- dle the interrupt); c) agency itself: the basic feature of autonomy (implying asynchronous behaviour) is endangered. Luckily, current timers permit a “fine-grain universal metronome”, avoiding the costly implication: “asynchronously executing agents → temporal logic of the reals”. Thus, “asynchronously executing agents” should be perceived as pleonasm, despite their logic is still based upon a discrete model of time, with both infinite past and future. (In real-world MAS, there is no “Big-Bang”.) ¥ No “negative introspection”. Unable to comment upon the advantages of ideal doxastic logics out- side large-scale MAS, the authors feel that positive introspection is highly desirable but that assuming the negative one is ineffective for both agents and humans. Thus, if it makes sense and simplifies the features, maybe KD4, not KD45. ¥ No more certitude. Less checking. Until agent logics offer mechanisms to deal with uncertainty, at least, in simple expressions, the “ugly chasm” separating formal theory and practical system develop- ment [9] cannot be avoided. Just a plain example of a badly needed such mechanism: exception handling. Even primeval animals move “algorithmically” (“if gap then get round, else go on”) only a few steps, in very hostile environments. Moreover, reaction to stimuli cannot mean perpetual looking for the stimu- lus. (Instead, the stimulus causes an interrupt that can be treated as exception.) The cardinal hindrance stems not from logic, but from the mechanisms employed: neither nature, nor technology can afford in the long run mechanisms involving large amount of testing because they are too time-consuming tools: “if temperature > n oC then alarm”. Thus, the main problem is not the semantics of “unless”, but the repeated checking of “if ”. From this angle, the semantics of “unless” in Reiter’s default logic would be more tempting if it would be rather diachronic than synchronic (a bird is or is not a penguin but will never become one). However, a kind of M operator meaning roughly “while no alarm is heard it is consistent to believe that nothing happened”. Indeed, the agent is condemned to be a risk-taker, hearing (reactively) the environment, not listening (proactively) to it: the agent stops performing a task only if he hears the alarm bell. The point is that this “if ” belongs to the metalanguage and does not involve ther- mometer reading! Perhaps a non-monotonic logic with “Reiter-unless” inserted in a temporal logic with “Fisher- unless” is what designers dream of. (Since dreams are forward-thinking, maybe more: a graph- ical “flowchart-like” symbol of this M shall be understood by an interpreter of an “AOSE-ML” -without “object legacy” - that can create code for defining, raising, propagating, and handling exceptions. 5 Down to Ants: Synergy, Stigmergy, AND Symbols Since as regards stigmergic coordination the research was recently summarised in [7], [8], [13] and the current results are presented in [7], here, only the approach and some relevant aspects of achieving synergy through grafting symbolic processing onto sub-symbolic systems are emphasised. The AND written in capitals emphasises the similarity with the synonymous boolean operator, i.e. synergy is searched for in all possible combinations. The MAS that relies on sub-symbolic processing more than any other is the biologically inspired Ant System (AS) where the sub-symbolic echelon is represented by the pheromones in such a way that global 10 Boldur E. Bărbat, Sorin C. Negulescu information is available locally. Moreover, this system is not only sub-symbolic by itself but it also manifests autopoiesis (it emerges subsymbolic) and the trouble to understand what is in fact going on at system level, is less upsetting than in the case of more familiar sub-symbolic paradigms (as artificial neural networks or evolutionary algorithms) since ant behaviour is easier to follow due to its simplicity. The stigmergy related to MAS, “describes a form of asynchronous interaction and information exchange between agents mediated by an ‘active’ environment”, or “the production of certain behaviour in agents as a consequence of the effects produced in the local environment by previous behaviour”. In this con- text: “the agents are simple, reactive, and unaware of other agents or of the emerging complex activities of the agent society; the environment is an important mechanism to guide activities of these agents and to accumulate information about ongoing activities of the whole agent society” [13]. Whereas in [2], [10], [14], the approach was mainly based on self-organization, the approach is an alter- native one by obtaining synergy through adding symbolic processing (firstly adapting the environment and secondly instituting limited central coordination). As shown in [7], the AS manifests a threshold and it depends on problem type and complexity; the same solution quality can be obtained with fewer ants than used in common benchmarks, saving thus at least one order of magnitude of processing time. Details can be found in [13] (improvements to conventional EAS), [8] (motivation, approach and new perspective), and [7] (experimental results about moving the threshold - in fact modifying the sigmoid function to improve efficiency). Possible scientific openings - e.g. whether in real-life problems there are instances when “many starts from four” - can be found also in [7]. 6 Conclusions: Beliefs, Desires, Intentions The conclusions are presented within the BDI frame not just to keep up the atmosphere, but because: a) the conclusions are far from being apodictic and the logics preferred for MAS are doxastic; b) using the meanings given by Smets, the belief functions have rather dispersed values, and the plausibility functions have quite low values for Section 4 and some assertions of Section 3; c) the largest part of Section 3 is actually a gathering of desires; d) intentions is more humble than “future work”; d) if we intend to interact keener with agents, we have to make steps towards common ontologies - preferably based on success stories. Beliefs: • Despite the fall of conventional algorithms and the fast rise of sub-symbolic paradigms, symbolic processing is unavoidable in AOSE and agent logics become necessary even outside large-scale systems. • An essential problem in designing agents is implementing their reactivity; main cause: current development environments admit rather very poor exception handling. • Even MAS based on the most radical sub-symbolic paradigm (stigmergy being “a-symbolic” par excellence), become more effective grafting upon symbolic processing. • Taking into account the increasing weight of MAS acting as man-machine systems, the anthro- pocentric perspective requires that human-agent communication should be the model for agent- agent communication. • Although the brains-surrogate of current agents is still primitive, it shall have two hemispheres, as human do. The left hemisphere, where logic is king, is designed predominantly to implement pro-activeness, whereas the right one, as realm of its instincts, emerges sub-symbolically, and is the main source of reactivity (again, similar to humans). Desires: They are addressed to future agent logics, from an outsider (but outspoken AOSE) perspective: From Algorithms to (Sub-)Symbolic Inferences in Multi-Agent Systems 11 • Tackle neglected problems common to all kinds of agent-based systems (dwarfs and trolls wel- comed). • Give us sectorial solutions. They are just fine to begin with. Completeness - in its polysemy - can follow. (If the MAS is sound, nobody minds if agents manifest a bit of schizophrenia.) • Don’t give us sectorial approaches. They are less applicable (e.g., time without uncertainty or vice versa). • Let MAS be lasting, even if some agents are mortal. • Don’t condemn MAS to act synchronously. Both environment and users are too capricious to accept it. (Instead, we promise to be happy with discrete time.) • Don’t sentence us to perpetual testing. To rephrase Dijkstra: (the condition in) if is harmful. (Allow us to handle exceptions, and we promise not to exaggerate eliminating all “iffs”.) • Help us pass the mental Rubicon separating objects from agents. (No agent is fond of being considered “intelligent and responsive like an object”.) Intentions: • As regards stimergic coordination, the intentions are those states in [7]: for short, increasing “stigsynergy”. • Showing how agent reactivity can be significantly improved, through exception-driven multimodal interfaces. • Trying dialectics as inference mechanism for negotiation strategies used by e-commerce agents. Acknowledgment. This paper is related to the EU-sponsored action COST-298. References [1] “AgentLink Roadmap: Overview and Consultation Report”, AgentLink III. Agent based computing, University of Southampton, 2004. [2] Banzhaf, W., “Self-organizing Systems”, Encyclopedia of Physical Science and Technology, Aca- demic Press, New York, 14, pp. 589-598, 2002. [3] Bărbat, B.E., “Sisteme inteligente orientate spre agent”, Ed. Academiei Române, Bucureşti, 467 pages, 2002. [4] Bărbat, B.E., “The Avatar - A Pseudo-Human Extending the Genuine One”, The good, the bad and the irrelevant: The user and the future of information and communication technologies, (L. Haddon et al, Eds.), pp. 38-42, Media Lab/University of Art and Design, Helsinki, 2003. [5] Bărbat, B.E., “The Impact of Broad-Band Communication upon HMI Language(s). (Chapter 7.) Communicating in the world of humans and ICTs. (Chapter 8.)”, COST Action 269. e-Citizens in the Arena of Social and Political Communication, (L. Fortunati, Ed.), pp. 113-142, EUR21803, Office for Official Publications of the European Communities, Luxembourg, 2005. [6] Bărbat, B.E., N. Bulz, “E-World and Real World. From Analysing Concepts towards Integrating Ap- proaches”, Proc. of the WOSC 13th International Congress of Cybernetics and Systems, University of Maribor in cooperation with Encyclopaedia of Life Support Systems, 1, pp. 47-57, 2005. 12 Boldur E. Bărbat, Sorin C. Negulescu [7] Bărbat, B.E., S.C. Negulescu, C.B. Zamfirescu, “Human-Driven Stigmergic Control. Moving the Threshold”, Proc. of the 17th IMACS World Congress (Scientific Computation, Applied Mathematics and Simulation), Paris, July 11-15, 2005. [8] Bărbat, B.E., C.B. Zamfirescu, S.C. Negulescu, “The Best from Ants and Humans: Synergy in Agent-Based Systems”, Studies in Informatics and Control Journal, 13, 1, 47-59, 2004. [9] Fisher, M., “Temporal Development Methods for Agent-Based Systems”, Autonomous Agents and Multi-Agent Systems, 10, pp. 41-66, Springer Science + Business Media Inc., 2005. [10] Knyazeva, H., Haken, H., “Synergetics of Human Creativity. Dynamics, Synergetics, Autonomous Agents”, ANonlinear Systems Approaches to Cognitive Psychology and Cognitive Science Singa- pore: World Scientific, pp. 64-79, 1999. [11] Luck, M., McBurney, P., Priest, C., “A Manifesto for Agent Technology: Towards Next Generation Computing”, Autonomous Agents and Multi-Agent Systems, 9, 203-252, Kluwer Academic Publish- ers, 2004. [12] Moisil, Gr.C., “Lecţii despre logica raţionamentului nuanţat”, Ed. Ştiinţifică şi enciclopedică, Bu- cureşti, 1975. [13] Negulescu, S.C., Bărbat, B.E., “Enhancing the Effectiveness of Simple Multi-Agent Systems through Stigmergic Coordination”, Fourth International ICSC Symp. on ENGINEERING OF INTEL- LIGENT SYSTEMS (EIS 2004), ICSC-NAISO Academic Press Canada, 149 (Abstract; full paper on CD-ROM enclosed), 2004. [14] Parunak, H.V.D., Brueckner, S., John A. Sauter, Matthews, R., “Global Convergence of Local Agent Behavior”, Submitted to The Fourth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS’05), 2005, Available at http://www.erim.org/ vparunak/ AA- MAS05Converge.pdf. [15] Zambonelli, F., Omicini, A., “Challenges and Research Directions in Agent-Oriented Software En- gineering”, Autonomous Agents and Multi-Agent Systems, 9, 253-283, Kluwer Academic Publishers, 2004. Boldur E. Bărbat “Lucian Blaga” University of Sibiu Faculty of Science Address: 5-7, Ion Raţiu Street, Sibiu, 550012, România E-mail: bbarbat@gmail.com Sorin C. Negulescu “Lucian Blaga” University of Sibiu Faculty of Engineering Address: 4, Emil Cioran Street, Sibiu, 550025, România E-mail: sorin−negulescu@yahoo.com