This paper casts coordination of a team of robots within the framework of game theoretic learning algorithms. A novel variant of fictitious play is proposed, by considering multi-model adaptive filters as a method to estimate other players’ strategies. The proposed algorithm can be used as a coordination mechanism between players when they should take decisions under uncertainty. Each player chooses an action after taking into account the actions of the other players and also the uncertainty. In contrast, to other game-theoretic and heuristic algorithms for distributed optimisation, it is not necessary to find the optimal parameters of the algorithm for a specific problem a priori. Simulations are used to test the performance of the proposed methodology against other game-theoretic learning algorithms.

Boolean networks is a well-established formalism for modelling biological systems. A vital challenge for analyzing a Boolean network is to identify all the attractors. This becomes more challenging for large asynchronous Boolean networks, due to the asynchronous scheme. Existing methods are prohibited due to the well-known state-space explosion problem in large Boolean networks. In this paper, we tackle this challenge by proposing a SCC-based decomposition method. We prove the correctness of our proposed method and demonstrate its efficiency with two real-life biological networks.

Cooperative games-based robot cooperation is analysed for reoccurring scenarios. It is shown that potential games can be used for robot coordination when the robots have a shared objective. By observing each others' behaviour in similar scenarios, they estimate each other's expected actions, which they use for their own choice of action. The resulting learning scheme can enable “tuning” of smooth cooperation by task allocation in teams of robots for various goals and in reoccurring scenarios of their environment. The theoretical results and methods are illustrated in simulation.

Social approaches have been put forward to define semantics for intelligent agent communication messages and to tackle the shortcomings of mental approaches. Formal semantics of those social approaches can be model checked as they are focused on public behaviors instead of private mental states. Social conditional commitments are essential concepts in social approaches that can effectively model agent communications. However, conditional commitments exclusively are not able to model agent communication actions, the cornerstone of the fundamental agent communication theory, namely speech act theory. These actions provide mechanisms for dynamic interactions and enable designers to track the evolution of active conditional commitments. From the perspective of model checking, we need to define a formal and computationally grounded semantics for relevant social actions that can directly be applied to active conditional commitments. This manuscript describes a new symbolic model checker, SMC4AC, developed and implemented to automate the verification of interaction among intelligent agents. SMC4AC is the result of developing a new symbolic model checking algorithm devoted to CTLC α , a combination of CTL and new temporal modalities to represent and reason about conditional commitments and common commitment actions. The core of this paper consists of a new logical language, a detailed description of the symbolic algorithms needed for commitments and their action modalities, complexity analysis, implementation and application. The implementation of our algorithm and its graphical user interface is built on top of the MCMAS symbolic model checker tailored for checking intelligent multi-agent systems. We select business processes and multi-agent interaction protocols as application domains to test and validate the effectiveness and scalability of SMC4AC. We report extensive experimental results, which confirm the theoretical findings and make SMC4AC practical.

We present MCMAS, a model checker for the verification of multi-agent systems. MCMAS supports efficient symbolic techniques for the verification of multi-agent systems against specifications representing temporal, epistemic and strategic properties. We present the underlying semantics of the specification language supported and the algorithms implemented in MCMAS, including its fairness and counterexample generation features. We provide a detailed description of the implementation. We illustrate its use by discussing a number of examples and evaluate its performance by comparing it against other model checkers for multi-agent systems on a common case study.

Boolean networks are an important formalism for modelling biological systems and have attracted much attention in recent years. An important direction in Boolean networks is to exhaustively find attractors, which represent steady states when a biological network evolves for a long term. In this paper, we propose a new approach to improve the efficiency of BDD-based attractor detection. Our approach includes a monolithic algorithm for small networks, an enumerative strategy to deal with large networks, and two heuristics on ordering BDD variables. We demonstrate the performance of our approach on a number of examples, and compare it with one existing technique in the literature.

The ability to compose web services from available services is one of the most crucial problems in the service-oriented computing paradigm. Conventional software engineering approaches and even standard languages compose web services as workflow models that control the business logic required to coordinate data over participating services. Such models would not apply to the design of multiagent-based web services, which offer high-level abstractions that support autonomy, business-level compliance, and flexible dynamic changes. In this paper, we model interactions among multiagent-based services by commitment modalities in the figure of contractual obligations and devote multiagent commitment protocols to regulate such interactions and engineer services composition. We develop and fully implement a symbolic model checking algorithm by enriching the MCMAS model checker with certain symbolic algorithms to verify the correctness of protocols, given properties expressed in a temporal commitment logic, suitably extended with actions. The time complexity and space complexity of the developed algorithm are P-complete for explicit models and for PSPACE-complete concurrent programs. Finally, we report the experimental results of two case studies, adopted to check the algorithm's efficiency.

We consider models of programs that incorporate probability, dense real-time and data. We present a new abstraction refinement method for computing minimum and maximum reachability probabilities for such models. Our approach uses strictly local refinement steps to reduce both the size of abstractions generated and the complexity of operations needed, in comparison to previous approaches of this kind. We implement the techniques and evaluate them on a selection of large case studies, including some infinite-state probabilistic real-time models, demonstrating improvements over existing tools in several cases.

While modeling interactions using social commitments provides a fundamental basis for capturing flexible and declarative interactions and helps in addressing the challenge of ensuring compliance with specifications, the designers of the system cannot guarantee that an agent complies with its commitments as it is supposed to, or at least an agent doesn't want to violate its commitments. They may still wish to develop efficient and scalable algorithms by which model checking conditional commitments, a natural and universal frame of social commitments, is feasible at design time. However, distinguishing between different but related types of conditional commitments, and developing dedicated algorithms to tackle the problem of model checking conditional commitments, is still an active research topic. In this article, we develop the temporal logic CTL cc that extends Computation Tree Logic (CTL) with new modalities which allow representing and reasoning about two types of communicating conditional commitments and their fulfillments using the formalism of interpreted systems. We introduce a set of rules to reason about conditional commitments and their fulfillments. The verification technique is based on developing a new symbolic model checking algorithm to address this verification problem. We analyze the computational complexity and present the full implementation of the developed algorithm on top of the MCMAS model checker. We also evaluate the algorithm's effectiveness and scalability by verifying the compliance of the NetBill protocol, taken from the business domain, and the process of breast cancer diagnosis and treatment, taken from the health-care domain, with specifications expressed in CTL cc . We finally compare the experimental results with existing proposals.

Markov decision processes (MDPs) are often used for modelling distributed systems with probabilistic failure or randomisation. We consider the problem of model repair for MDPs defined as follows: if the MDP fails to satisfy a property, we aim to find new values for the transition probabilities so that the property is guaranteed to hold, while at the same time the cost of repair is minimised. Because solving the MDP repair problem exactly is infeasible, in this paper we focus on approximate solution methods. We first formulate a region-based approach, which yields an interval in which the minimal repair cost is contained. As an alternative, we also consider sampling based approaches, which are faster but unable to provide lower bounds on the repair cost. We have integrated both methods into the probabilistic model checker PRISM and demonstrated their usefulness in practice using a computer virus case study.

Compositional approaches to verification offer a powerful means to address the challenge of scalability. In this paper, we develop techniques for compositional verification of probabilistic systems based on the assume-guarantee paradigm. We target systems that exhibit both nondeterministic and stochastic behaviour, modelled as probabilistic automata, and augment these models with costs or rewards to reason about, for example, energy usage or performance metrics. Despite significant theoretical advances in compositional reasoning for probabilistic automata, there has been a distinct lack of practical progress regarding automated verification. We propose a new assume-guarantee framework based on multi-objective probabilistic model checking which supports compositional verification for a range of quantitative properties, including probabilistic ω-regular specifications and expected total cost or reward measures. We present a wide selection of assume-guarantee proof rules, including asymmetric, circular and asynchronous variants, and also show how to obtain numerical results in a compositional fashion. Given appropriate assumptions to be used in the proof rules, our compositional verification methods are, in contrast to previously proposed approaches, efficient and fully automated. Experimental results demonstrate their practical applicability on several large case studies, including instances where conventional probabilistic verification is infeasible.

Quantitative verification techniques provide an effective means of computing performance and reliability properties for a wide range of systems. However, the computation required can be expensive, particularly if it has to be performed multiple times, for example to determine optimal system parameters. We present efficient incremental techniques for quantitative verification of Markov decision processes, which are able to re-use results from previous verification runs, based on a decomposition of the model into its strongly connected components (SCCs). We also show how this SCC-based approach can be further optimised to improve verification speed and how it can be combined with symbolic data structures to offer better scalability. We illustrate the effectiveness of the approach on a selection of large case studies.

We investigate the problem of the verification of multi-agent systems by means of parallel algorithms. We present algorithms for CTLK, a logic combining branching time temporal logic with epistemic modalities. We report on an implementation of these algorithms and present the experimental results obtained. The results point to a significant speed-up in the verification step.

We investigate partial order reduction techniques for the verification of multi-agent systems. We investigate the case of interleaved interpreted systems. These are a particular class of interpreted systems, a mainstream MAS formalism, in which only one action at the time is performed in the system. We present a notion of stuttering-equivalence and prove the semantical equivalence of stuttering-equivalent traces with respect to linear and branching time temporal logics for knowledge without the next operator. We give algorithms to reduce the size of the models before the model checking step and show preservation properties. We evaluate the technique by discussing implementations and the experimental results obtained against well-known examples in the MAS literature.

Model-based test derivation for real-time system has been proven to be a hard problem for exhaustive test suites. Therefore, techniques for real-time testing do not aim to exhaustiveness but Instead respond to particular coverage criteria. Since it Is not feasible to generate complete test suites for real time systems, It IsI very Important that test case are executed In a way that they can achieve the best possible resuIlt As a consequence, It is imperative to Increase the probabilty of success of a test case execution (by 'success' we actually mean 'the test finds an error'). This work presents a technique to guide the execution of a test case towards a particular objective with the highest possible probability. Thke technique takes as a starting point a model described In terms of an input/output stochastic automata, where input actions are fully controlled by the tester and the occurrece time of output action responds to uniform distributions. Derived test cases are sequences of Inputs and outputs actions. This work discusses several techniques to obtain the optimum times In which the tester must feed the inputs of the test case in order to achieve maxhmum probabilty of success in a test case execution. In particular~, we show this optimization problem Is equivalent to maximizing the sectional volume of a convex polytope when the probabilty distributions Involved are uniform.

In this paper, we present Reo2MC, a tool chain for the performance evaluation of coordination models. Given a coordination model represented by a stochastic Reo connector, Reo2MC is able to automatically generate the Quantitative Intentional Automaton (QIA) as its operational semantics, and the corresponding Continuous-Time Markov Chain (CTMC), which allows us to apply existing CTMC tools, e.g., PRISM, for performance analysis of Reo connectors. In support of understanding connector behavior and performance properties, the tool also provides the graphical representation of the QIA and Markov Chains.

We report on a novel approach to (semi-)automatically compile and verify contract-regulated service compositions. We specify Web services and the contracts governing them as WSBPEL behaviours. We compile WSBPEL behaviours into the specialised system description language ISPL, to be used with the model checker MCMAS to verify behaviours automatically. We use the formalism of temporal-epistemic logic suitably extended to deal with compliance/violations of contracts. We illustrate these concepts using a motivating example whose state space is approximately 106and discuss experimental results.