The aim of this paper is to brie y introduce some of our experiences with agent oriented programming, in particular combined with logic programming paradigm, in the context of software engineering, and with a focus on formal approaches for software development. The paper brie y reports some of the lessons learnt from carrying out few small research applications, employing agent-oriented logic programming languages including ECLiPSe-CLP and AgentSpeak(L) / Jason. The main contribution is to present complexity results of few small agent-oriented programming projects based on logical reasoning. Such approaches are traditionally the focus of arti cial intelligence research, while our concern here is on the more pragmatic perspective of software complexity.
2:2 nity, that focuses on sound and robust software development methodologies, in particular showcasing formal approaches based on computational logic. Different flavors of logic programming, including for example constraint logic programming (CLP hereafter) or satisfiability checking (SAT) have been proposed for tackling various software engineering problems such as: testing, verification, symbolic execution, and quality assurance [Meudec 2001; Doyle and Meudec 2003; Anderson et al. 2005; Rojas and Go´mez-Zamalloa 2013; Visser et al. 2014]. On the other hand, agent-oriented logic programming practices are by far less mature and under-represented from the software engineering point of view than other programming paradigms, like for example object-orientation.
The main contribution of this paper is to present complexity results of few small agent-oriented programming projects based on logical reasoning. Such approaches are traditionally the focus of artificial intelligence research, while our concern here is on the more pragmatic perspective of software complexity. We employ basic complexity measures specific to rule-based and logic programming, adapted to the agent-oriented context, and we provide estimations of these measures for the projects briefly reviewed in this paper. In our opinion these results could be of interest to both artificial intelligence and software engineering research communities.
Our paper is structured as follows. We start in Section 2 with a brief overview of agent-oriented logic programming. In Section 3 we introduce a number of small research projects that employ agentoriented logic programming in different application areas, including logistics, reinforcement learning, as well as modeling and simulation of dynamic systems. For each application we provide summary complexity figures emphasizing various aspects, like size of the knowledge base, size of belief base, size of plan base, number of agents, as well as number of agent interactions. Section 4 concludes the paper and points to future works.
Computational logic has a quite long tradition in the field of classical artificial intelligence that advocates the use of logic for knowledge representation and reasoning. This led to the development of a plethora of AI methods and languages which allow the capturing of the cognitive and problem solving capabilities of intelligent agents.
Logic Programming is a programming paradigm comprising a collection of declarative programming languages that use logic as the underlying computational mechanism of intelligent agents [Levesque 2012]. The prototypical language of this class is Prolog, while state-of-the-art extensions refer to Answer Set Programming and Constraint Logic Programming.
A logic program is a set of facts and a set of rules. In the context of intelligent agents, a logic program is sometimes called knowledge base. Facts are atomic formulae composed of a predicate name and a number of arguments. Arguments can be constants, variables or compound terms. Facts can be used to capture the description of a situation, problem case or an agent’s belief base.
Prolog rules are logical formulae equivalent to definite clauses. A definite clause is a disjunction of literals (direct or negated atomic formulas) such that exactly one literal is positive. Rules can be used to capture reasoning patterns of problem solving strategies of intelligent agents.
Intelligence is extracted, consulted and applied using queries addressed to the agent’s knowledge base. A query may have an external origin from another agent or human, seeking for consultancy of the intelligent agent or internally, from the intelligent agent itself through introspection mechanisms, during the problem solving process.
CLP in general and ECLiPSe-CLP in particular distinguish between normal Prolog predicates as used by standard Prolog and constraints that are specific to CLP [Schimpf and Shen 2012]. This distinction is mandatory as constraints are handled by specialized constraint satisfaction algorithms that provide more efficient problem solving methods than the standard Prolog’s backtracking search.
AgentSpeak(L) is an abstract agent-oriented programming language introduced in [Rao 1996]. Jason is a Java-based implementation, as well as an extension of AgentSpeak(L) [Bordini et al. 2007].
AgentSpeak(L) follows the paradigm of practical reasoning, i.e. reasoning directed towards actions, and it provides an implementation of the Belief-Desire-Intention (BDI hereafter) architecture of software agents. According to this view an agent is a software module that (i) provides a software interface with the external world and (ii) contains three components: belief base, plan library and reasoning engine.
The agent’s external world consists of the outer environment, as well as possibly other agents. The agent interface provides three elements: sensing interface, actuation interface and communication interface. The integration of agents with their external environment can be done using a Java API.
The belief base defines what an agent “knows” or “believes” about its environment at a certain time point. The BDI architecture does not impose a specific structuring of the belief base other than as a generic container of beliefs. By default AgentSpeak(L) and Jason are using a logical model of beliefs by structuring the belief base as a logic program composed of facts and rules. So, the agent can reason about its own beliefs using logic programming.
The plan library defines the agent’s “know-how” structured as a set of behavioral elements called plans. A plan follows the general pattern of event-condition-action rules and it is composed of three elements: triggering event, context and body. Events are triggered by belief and goal updates. AgentSpeak(L) distinguishes between test goals and achievement goals. Test goals closely correspond to logic programming queries addressed to the agent belief base. Moreover, plan context matching with agent’s belief base is also using logic programming queries.
The reasoning engine implements an update-select-act cycle that includes several activities: perception and communication, event handling and plan selection, as well as action selection and execution.
In this section we introduce a series of small applications having in common the use of logic and agent-oriented programming for problem solving in the following areas: optimization, learning, and simulation. These applications mainly serve research needs, but they can be also used in an educational setting centered on artificial intelligence and / or multi-agent systems curricula. We provide a brief description of each application, highlighting the role of agents and logic.
Freight brokering business aims to coordinate transportation arrangements of transport customers with transport resource providers. In this work we focused on the main function of this business to find available trucks and to define their feasible routes for serving customer transportation requests. We proposed a knowledge-based freight broker based on agents and constraint programming.
The brokering function is defined as a special type of vehicle routing with pickup and delivery problem. Our main achievement was the development of a declarative optimization model based on constraint logic programming [Ba˘ dica˘ et al. 2018b]. This model was implemented and evaluated using the state-of-the-art ECLiPSe-CLP engine [Schimpf and Shen 2012].
We focus on the freight broker agent that mediates the indirect interaction between customer agents and freight transportation provider agents. This agent records the transport requests issued by customer agents, records provisions of transportation resources, including available trucks and/or vehicles, as well as their characteristics, and determines feasible and possibly optimal allocations of transport resources to transport requests.
The freight broker agent is a typical knowledge-based agent composed of knowledge base and inference engine. The knowledge base is structured into: facts, rules & queries, and constraints. The input description of the scheduling problem (vehicles characteristics, customer orders, transportation hops) is converted to an internal representation captured by a set of logical facts that share a predefined and self-explanatory schema. The constraints are general and they represent reusable knowledge for solving different problem instances. The rules and queries define additional predicates, including the generic search predicates, that are internally used by the agent to solve the given transportation scheduling problem. The inference engine is represented by a constraints solver engine.
Useful metrics of the freight broker agent refer to the size of the knowledge base estimated by the number of facts, number of rules, and number of constraints.
This research was conducted in the context of approaching reinforcement learning (RL hereafter), a typical task calling for intelligence of agents acting in an environment [Sutton and G. Barto 1998], within the framework of agent-oriented programming. Agents, single or in group, can use RL to learn how to choose their actions in an uncertain, dynamic and possibly unknown environment, in order to improve their long-term utility.
Our research was concerned with somehow trying to narrow the gap between agent research and the practical use of agent-oriented programming. In particular we approached classical RL methods based on temporal-difference learning (TDL hereafter) and Q-learning using BDI languages. Using our proposal, BDI agents programmed in Jason can be endowed with RL skills, possibly resulting in new forms of hybrid reasoning that can benefit from combining BDI reasoning and machine learning into a unique cognitive architecture [Ba˘ dica˘ et al. 2015].
Our prototype system was designed to serve the purpose of assisting researchers in experimenting with BDI learning agents [B a˘dica˘ et al. 2018a]. It contains RL agents situated in a two dimensional grid environment. Agents can take one step up, down, left or right in this grid. The result of their action is stochastic, i.e. it can produce a successful move to the desired direction, or an erroneous move by slightly deviating to left or right from the desired direction. The action’s effect uncertainty captures the agents ignorance about their environment.
A basic abstraction for the development of our system was to decouple the agents from their environment. The simple sensing and acting interface provided by Jason platform proved very useful to effortlessly achieve this desiderate. Agents can use their sensorial capabilities to perceive their environment, while percepts can provide reward and state information, according to the RL paradigm. Moreover, agents can use their acting capabilities specific to practical reasoning in order to perform their actions, again complying with the RL paradigm. This model can be easily extended to multiple agents sharing their environment that can act either asynchronously (in isolation) through independent actions or synchronously (in coordination) through joint actions.
The specific RL method was encoded using event-condition-action plans of BDI agents. We devised BDI representations for the basic TDL approach in passive context, when the agent is only interested to accurately estimate its long-term utility, as well as for classic Q-learning and SARSA methods in active context, when the agent is interested to improve its long-term utility. Finally, taking into account the rigor of our approach, we have reasons to believe that this method can be adapted for agent-oriented programming languages following the BDI paradigm, thus supporting its generality [Ba˘ dic a˘ et al. 2011; Kravari and Bassiliades 2015].
Useful metrics for the RL agents are: size of the belief base in number of facts and number of rules, as well as size of plan base in number of plans and number of agent actions. 3.3
In this section we consider three research applications having in common the modelling and simulation of continuous and discrete dynamic systems using BDI agents implemented in Jason in the areas of game theory, business processes and ecology.
3.3.1 Patrolling Games. This project was focused on developing a BDI-based modelling and simulation framework of patrolling games. This topic is part of the larger domain of game theory for security that is interested in the development of intelligent defence strategies for enhancing the trustworthiness of cyber-physical systems.
We introduce a formal model of two-person patrolling game as Bayesian normal form game [LeytonBrown and Shoham 2008]. This game involves two agents (robber and guardian) and it is suitable for the scheduling of guardian patrols in surveillance applications. The model is mapped to agent-based simulation using Jason agent-oriented language [Ba˘ dica˘ et al. 2017].
The application involves two BDI agents representing the robber and the guardian that iteratively play the patrolling game in a sequence of rounds. During each round the agents submit a joint action to the game environment that reacts by providing to each of them the corresponding utilities in the form of agent percepts1. In our experiments agents adopt mixed strategies that are fixed during a playing round [Leyton-Brown and Shoham 2008]. Sampling of mixed strategy spaces and agent decision making based on these strategies were implemented using logic programming.
We can observe that this application uses the same model as the RL application, by letting the agents to indirectly interact by jointly acting upon and separately perceiving their environment. The game logic is encapsulated by the environment that exposes a sense and act interface allowing the agents to play the game and to receive the corresponding utilities. This framework can be used to experiment with more complex agent strategies possibly combining results of game theory and RL.
Similarly to the RL application, useful metrics for the robber and guardian agents are: size of the belief base and size of plan base.
3.3.2 Knowledge Based Business Agents. This project was focused on modeling and enactment of business processes using state-of-the-art agent-oriented programming. In particular we proposed a method of capturing business process models expressed using role-activity diagrams [Ould 2005] by AgentSpeak(L) / Jason programs. This approach of combining sound methods of business process and agent-oriented modeling paves the way for the development of agent-based business organizations.
Roles chunk business processes into units of responsibility that structure the set of activities they are carrying out into single of multiple threads of work. Each role is mapped to a proactive Jason agent, while the state of each role is captured by the set of beliefs of its corresponding agent. State transitions are modeled by event-condition-action rules. Role coordination is achieved by letting involved agents share their beliefs about their current state by direct interaction via message exchange.
Our main achievement in this work was the generalization of the mapping of role activity diagrams to Jason by proposing a generic knowledge-based business agent architecture (KB2A2 in what follows) [Ba˘ dica˘ et al. 2016]. KB2A2 proposes the configuration of each agent representing a role of a business process using the following components: i) a knowledge base defined as the set of facts capturing the operational knowledge of the role; ii) a set of template plans capturing the generic behavioral patterns of business agents. 1https://github.com/IntelligentDistributedSystems/Antoine-Conor
2 2 compliant multi-agent system based on are: number of agents, size
Some useful metrics of a KB A of the knowledge base as number of facts, and number of agent interactions. Note that the plan base is unique and shared by all the agents of the business organization.
3.3.3 Modeling and Simulation of Graph-Based Predator-Prey Systems. The goal of this research was to investigate the suitability of multi-agent systems based on BDI architecture for capturing the details of the simulation models of continuous dynamic systems, as encountered in science and engineering. Our achievement is the proposal of a framework based on BDI agents for the macroscopic modeling and simulation of continuous dynamic systems. Our framework was used for the modeling and simulation of an ecological system comprising a number of species that behave according to a given set of predator-prey relationships described by an acyclic directed graph [Ba˘ dica˘ et al. 2018].
While traditionally, agent-based modeling has been mostly applied for micro-modeling and microsimulation, this work can be seen as a contribution of employing BDI-based agent-oriented programming for the macro-modeling and macro-simulation of dynamic systems.
The idea was to break down the target system model into a collection of autonomous and looselycoupled interacting components endowed with message-based interfaces and local intelligence. Each component has a type that precisely characterizes its behavior as a (possibly state-based) mathematical function, as well as a finite number of inputs and outputs.
Each component is mapped to a Jason agent that captures its state as a set of logical facts and its behavioral patterns as a set of plans. Agents are configured to include: the agent type, the set of parameters completely defining the mathematical function performed by the agent, the component state, and the agent acquaintance model that is necessary for the dissemination of simulation information.
This approach provides a natural mapping of a dynamic system model to a distributed computational system that can bring modularity, scalability, reusability, and flexibility to a network-based implementation. The building blocks of our solution are highly reusable. Their configuration is simply achieved by initializing accordingly the agents’ belief bases.
Useful metrics include number of agents and number of agent types. Agents of a given type share their plan base, while agent interaction is achieved by message passing, like the KB2A2 architecture.
The analysis of software complexity is an important problem in software engineering. Moreover, multiagent systems are a special type of software developed using multi-agent platforms and languages. Therefore, their systematic analysis from the complexity and performance points of view attracted the interest of the computer science research community [Camacho and Aler 2005; Jordan and Collier 2012; Ivanovic´ et al. 2016].
In this section we propose a brief comparative analysis of the software projects introduced in this paper, based on their quantitative and qualitative characteristics. In principle, we can reuse already existing analysis proposals and frameworks. Nevertheless, our endeavour is a bit special because our work is focused on logic based agent-oriented programming languages. The research literature contains also proposals for measuring software complexity of logic programs, in particular based on Prolog language [Moores 1998], as well as of rule-based expert systems [Chen and Suen 1994]. These works provided us some source of inspiration, as reasoning with agent beliefs in Jason is actually based on logic programming, while Jason plans resemble some-how production rules of expert systems.
In what follows we consider the five agent-based software projects presented in this paper from the following perspectives. The resulted summary figures are presented in Table I.
On Software Complexity of Agent-Oriented Logic Programs: an Empirical Analysis 2:7 n u ] r m b 8 n y ˘a y ˘a r ˘a l c l c o c n i n i f i o d o d d
˘a ˘a ly ˘a s n o i t a c i l p ts + + p n a ia ) 1 2 ) 5 r d t e s t n ++ )n o t n s e n g la a P d # e s a s
e b l - u 7 c R 1 i g e # o s l a 5 B 2
f k r e y t i n x io e t l c p ra
e m t o n c I m s u t S en . A I
# e l b a T
t t y n c r e e a g ir
A d m r e k o r b n o i t p t i rc igh tn s e e e r g D F a . o
N : g 1
1 2 3 7
6 9 4 1 1 1 1
0 + 5
6 1. In the case of the freight brokering system introduced in Section 3.1, the analysis is exclusively focused on the freight broker agent. 2. In the case of RL agents introduced in Section 3.2, the analysis is focused on the implementation of classic RL strategies in Jason (so the Java-based implementation of the environment, as well as the other components of the system that use classical object-oriented programming are ignored). 3. In the case of the patrolling game simulation introduced in Section 3.3.1, we focus only on the guardian and robber agents, while the Java-based implementation of the environment, as well as the other components of the system are omitted. 4. In the case of KB2A2 framework introduced in Section 3.3.2, we focus on the sample project management process presented in [Ba˘ dica˘ et al. 2016]. 5. In the case of the BDI-based framework for the modeling and simulation of continuous dynamic systems from Section 3.3.3, we consider the predator-prey system introduced in [Ba˘ dica˘ et al. 2018].
Table I reveals interesting aspects. In 2 projects (1 and 2) the number of facts in the belief base depends on the problem instance, actually increasing with the values of the input parameters of the problem. On the other hand, number of rules and plans are constant for each agent. Finally, for the constraint-based agent (project 1), the number of constraints also depends on the problem instance, actually increasing drastically with the values of the input parameters of the problem. Frankly speaking, constrains are actually represented as Prolog facts, so this observation is consistent with our finding referring to the number of facts of the belief base.
Moreover, while application 3 can be described as relatively simple, involving the modeling and simulation of the strategic interaction of two intelligent agents, applications 4 and 5 actually incorporate hidden sources of complexity that are not immediately noticeable from the quantitative figures presented in Table I. The sources are represented by the size of the the RAD process model, respectively by the size of the dynamic system under consideration. They directly impact the size of the agents’ belief base and the number of agents (in project 4), as well as the number of agents (in project 5).
Finally, it is interesting to observe that with the modular approach employed by project 5, the complexity of the dynamic system under consideration is reflected into the complex interaction structure (acquaintance model) of the multi-agent system, while the internal model, as well as the belief base of each agent are kept as simple as possible.
This simple analysis provides some useful insights into the main sources of complexity of knowledgebased applications based on logical reasoning. We can observe that, in our simple projects, the number of logical facts (representing agents’ belief bases or problem constraints), as well as the number of agents and their interactions can represent the main source of complexity. Both (beliefs and constraints) are actually derived from the domain conceptualization that in our opinion plays a crucial aspect in knowledge-based systems. This supports the conclusion that the knowledge engineer’s experience, as well as his or her insight into the problem domain have a significant impact on the provided solution. Finally, the number of agents and their interactions clearly depend on the problem solving approach, also carrying out a significant impact on the provided solution.
We briefly reviewed from a software engineering perspective, several research prototypes employing logic-based agent programming. We provided a comparative analysis of summary complexity figures of these projects. As future work, this analysis can be further deepened and consequently the conclusions strengthened, by considering more complexity figures, possibly applied to other research prototypes involving logic-based agent programming. This will involve at least two aspects that we plan to consider in our future work: i) expanding the repository of considered applications with more projects in the area of agent-based logic programming; one source could be the sample applications and examples available within Jason distribution; ii) developing a more systematic analysis approach, possibly enabled by a suitable tool support.
ACKNOWLEDGMENT This paper is a part of the Serbia-Romania-Poland collaboration within multilateral agreement on “Agent systems and applications” and Romania-Poland collaboration within bilateral project “Semantic foundation of the Internet of Things”.