BDI agent testability revisited

Agent-based systems are deployed to solve a wide range of problems in a wide range of domains. Before software is deployed, it is important to obtain assurance that it will function correctly. Traditionally, this assurance is obtained by testing. However, there is an intuition that agents exhibit more complex behaviour than traditional software, which raises the question: how testable are agent systems? We focus on BDI agent programs, and analyse their testability with respect to the all edges test adequacy criterion (also known as “branch coverage”). Our results augment earlier results that considered the all paths criterion to provide a richer and more nuanced understanding of the testability of BDI agents. We show that the number of tests required with respect to the all edges criterion is much lower than that required with respect to the all paths criterion. We also show that, as for the previous analysis, BDI programs are harder to test than equivalently-sized procedural programs, even if exception handling is introduced. Overall, our conclusions lend strength to the earlier work, and motivate the need for work on formal methods for agent systems.

1. More precisely: “software quality assurance (SQA) is a set of activities that define and assess the adequacy of software processes to provide evidence that establishes confidence that the software processes are appropriate and produce software products of suitable quality for their intended purposes.” (ISO/IEC TR 19759:2015(E), p. 10-5)

2. There is also a body of work on formal methods (primarily model checking) as a means of assurance [4, 12,13,14, 18, 32, 44]. However, despite considerable progress, these are not yet ready to handle realistic programs (e.g. see [14]).

3. To avoid confusion between this paper and the earlier work, I will refer to my earlier work with Stephen Cranefield as “Winikoff and Cranefield” in the remainder of this paper.

4. Note that this is a path through an (abstract) control-flow graph. This is different from a trace in that variable values are not considered. For example, the trivial program \(x {:=} x+1\) has a single path, but many traces for different values of x.

5. Our analysis of BDI programs is agnostic to whether these represent a part of the whole agent system, or the entire system. In other words, the distinction between unit and system level testing is in the application of the analysis and the interpretation of the results, not the analysis itself. We return to this point in Sect. 9.

6. There is one issue we need to consider: since “all paths” is a strong criterion, it is possible that, even in the absence (or bounding) of loops, this criterion always results in an infeasibly large numbers of paths. [40, Section 1.1]

7. For the purposes of this paper we ignore other possible plan triggers provided by some AOPLs, such as the addition/removal of belief, and the removal of goals.

8. For the moment we avoid specifying whether \(\mathcal {P}\) is the set of relevant plans or applicable plans. The analysis in the next section considers both cases.

9. Colour is used to assist readability, but is not essential.

10. Proof by cases: consider the possible cases for \(b < c\) (true or false) and for \(a+b<c\). Case 1 (\(b<c\), \(a+b<c\)): then \(max(a+b,c) \le a+ \max (b, c)\) iff \(c\le a+c\). Case 2 (\(b\ge c\), \(a+b<c\)): this case cannot occur since \(b \ge c\) implies that \(b+a > c\) (since \(b+a>b \ge c\)) which contradicts the second assumption that \(a+b<c\). Case 3 (\(b<c\), \(a+b \ge c\)): \(max(a+b,c) \le a+ \max (b, c)\) iff \(a+b \le a+c\) iff \(b < c\) which holds for this case. Case 4 (\(b \ge c\), \(a+b \ge c\)): \(max(a+b,c) \le a+ \max (b, c)\) iff \(a+b \le a+b\) which trivially holds.

11. Proof: consider . If we assume the simplest case, where \(\mathcal {P}= \{P\}\), then we have . \(\square \)

12. We can derive either using a; (g; a) or (a; g); a, which give identical results.

13. If \(j=1\) we end up with , with , and with . These cases are included in the equations of Fig. 8.

14. We return later to consider the case where \(Q_1\) can only throw an exception that is handled by \(Q_2\), in which case we would have .

15. .

16. Which is .

17. The results are only presented in a graph, and for the larger programs the precise numbers could not be determined from the graph.

18. Note that since for a given sub-program we may not have any exceptions to use, we can no longer argue that the exception case subsumes the alternative case ().

19. (since ).

Authors and Affiliations

1. Department of Information Science, University of Otago, Dunedin, New Zealand

   Michael Winikoff

Corresponding author

Correspondence to Michael Winikoff.

Appendix 1: Derivation of with a single exception type

In Sect. 7 we noted that we had to decide whether programs had multiple exception types or a single exception type. The former led to higher values for . This is because for \(Q_1 \blacktriangleright Q_2\) the sub-program \(Q_1\) can throw an exception that is not handled by \(Q_2\), and therefore the number of places where an exception can be thrown is . On the other hand, if we assume that a program only has a single exception type then in \(Q_1 \blacktriangleright Q_2\) an exception can only be generated from \(Q_2\), since if \(Q_1\) throws an exception then \(Q_2\) will handle it. This means that .

We noted that this change had the profound effect of making the maximal number of tests required for Q be just (for programs containing exceptions, i.e. where ). We now prove this.

Recall that we have defined the following and that we ignore the case \(Q\, {::=}\, Q_1 ; Q_2\) since we know that , and therefore allowing “; ” cannot increase .

Theorem 1

Proof

We begin by showing that this holds for a program that has a single instance of \(\blacktriangleright \). We then show that a program containing two (or more) instances of \(\blacktriangleright \) can be rewritten in a way that reduces the number of instances of \(\blacktriangleright \) while retaining or increasing .

We therefore begin by considering a program that contains a single exception. We have that . There are two cases: if then this reduces to , which is the same equation as for , which we know leads to (Lemma 1). We therefore assume that , so we have . Since this does not use , then the highest value for is when \(Q = Q' \blacktriangleright s\) (i.e. make \(Q_2\) as small as possible). In this case, if \(Q'\) has no exceptions then we have , which from Lemma 1, is less than or equal to . By definition we have that , and therefore that as desired.

We now consider a program Q that has two instances of \(\blacktriangleright \). We consider the possible ways in which the program can be constructed, and argue that in each case we can either rewrite the program in a way that reduces the number of instances of \(\blacktriangleright \), or in a way that reduces the distance between two instances of \(\blacktriangleright \), which eventually makes one of the other cases (for adjacent \(\blacktriangleright \)) applicable.

• The top-level construct is \(\blacktriangleright \): We begin by considering \(Q = (Q_1 \blacktriangleright Q_2) \blacktriangleright Q_3\). In all cases, this can be rewritten to a different program using \(Q_1, Q_2, Q_3\) in a way that retains or increases , but only has a single instance of \(\blacktriangleright \) (outside of \(Q_1, Q_2, Q_3\)). From the definition of we have that:

  

  Now, we consider the following (exhaustive) three cases:

  1. 1.

     If then can be simplified to , and we observe that the program \(Q' = (Q_1 + Q_2) \blacktriangleright Q_3\) satisfies :

     
  2. 2.

     If and : then can be simplified to . We then observe that has , but only a single instance of \(\blacktriangleright \) outside of \(Q_1, Q_2, Q_3\).

  3. 3.

     If and : then can be simplified to . Consider . This has

     

     In other words, \(Q'\) has , only a single instance of \(\blacktriangleright \) (outside \(Q_1, Q_2, Q_3\)), and .

  So \(Q = (Q_1 \blacktriangleright Q_2) \blacktriangleright Q_3\) can, in all cases, be rewritten into another program \(Q'\) which has the same size, at least as large , and only one instance of \(\blacktriangleright \) (outside of \(Q_1, Q_2, Q_3\)).

• The top-level construct is \(\blacktriangleright \): we have already considered the case \((Q_1 \blacktriangleright Q_2) \blacktriangleright Q_3\), so we now only need to consider the case \(Q_1 \blacktriangleright (Q_2 \blacktriangleright Q_3)\).

  

  Now we have two cases:

  1. 1.

     if then can be simplified to and we can define \(Q' = Q_1 + (Q_2 \blacktriangleright Q_3)\) which has the same size and , but only a single instance of \(\blacktriangleright \) outside of \(Q_1, Q_2, Q_3\).

  2. 2.

     if then can be simplified to and we can define \(Q' = Q_1 \blacktriangleright s\) which has smaller size and equal .

• The top-level construct is \(+\): without loss of generality (since “\(+\)” is symmetrical) we consider \(Q = (Q_1 \blacktriangleright Q_2) + Q_3\). We observe that \(Q' = (Q_1 + Q_3) \blacktriangleright Q_2\) has the same size, satisfies , and moves the \(\blacktriangleright \) upwards (where it eventually either becomes the top-most \(\blacktriangleright \) or “meets” another \(\blacktriangleright \) at which point one of the other cases applies).

  

We have shown that we can always modify a program by shifting instances of \(\blacktriangleright \) upwards, and that adjacent instances of \(\blacktriangleright \) can be merged. If we apply these transformations to a given program Q repeatedly, then we can rewrite it in a way that eventually results in a program that has only a single instance of \(\blacktriangleright \), which is the top connective. In other words, the new program is of the form

Now, in fact, given a fixed program size, we can obtain the highest possible by having

Since:

This means that the worst case for single-exception-type (i.e. Q with highest ) is

for which we have \(\square \)

Reprints and permissions