manner. The presented formalism allows manipulating structures, which describe entire MDP classes rather than a speci c process.
An arti cial agent acting in natural environments has to deal with uncertainty
at di erent levels. In a changing environment meta-cognitive abilities can be
useful to recognize also when two tasks are instances of the same problem with
di erent parameters. The work presented in this paper tries to address some
of the issues related to such an agent as expressed above. The rationale of the
work derives from the previous research of the authors in the eld of planning
in uncertain environments [
Algebraic Decision Diagrams
A Binary Decision Diagram (BDD) is a directed acyclic graph intended for
representing boolean functions. It represents a compressed decision tree is. Given a
variable ordering, any path from the root to a leaf node in the tree can contain
a variable just once. An Algebraic Decision Diagram (ADD) [
Representing ADDs in Higher-order logic In our work ADDs have been described in Prolog using rst-order logic as a fact in a knowledge base to exploit the Prolog capabilities of managing higher-order logic. An ADD can be regarded as a couple hS; vi where S is the tree's structure, which is made up by nodes, arcs, and labels, and v is the vector containing the values in terminal nodes of the ADD. Let's consider the ADD described in the previous section. Figure 1 shows its decomposition in the structure-vector pair. Terminal nodes are substituted with variables, and the ADD is transformed into its structure. Each element of the vector v is a couple made up by a proper variable inserted into the i-th leaf node of the structure, and a probability value that was stored originally into the i-th leaf node.
In general, ADDs can be represented compactly through a recursive de nition due to the presence of isomorphic sub-graphs. At the same manner, a structure can be de ned recursively. The gure 2 shows an example.
high v low S= p left A right left B C p right v=
D
A 0.1 B 0.2 C 0.3
Following this logic, we can introduce the concept of MetaADD (MADD), which is a structure-vector pair hS; vi where S is the plain ADD structure, while v is an array of variables that are uni ed with no value (see gure 3). A MADD expresses the class of all the di erent instances of the same function, which involve the same variables but can produce di erent results.
An operator op can be applied to MADDs just like in the case of ADDs. In this way, the de nition of the operator is implicitly extended. The actual implementation of an operator op applied to MADDs can be derived by the corresponding operator de ned for ADDs. Given three ADDs, add1, add2, and add3, and their corresponding MADDs madd1, madd2, and madd3, then add1 op add2 = add3 ) madd1 op madd2 = madd3.
The de nition of the variables in madd3 depends on the operator. We will start explaining the implementation of a generic operator for ADDs. Assume that the structure-vector pairs for two ADD's are given: add1 = hS1; v1i, add2 = hS2; v2i. Running the operator will give the following result:
add1 op add2 = hS3; v3i
Actual execution is split into two phases. At rst, the operator is applied to both structures and vectors of the input ADDs separately, then the resulting temporary ADD is simpli ed.
Stemp = S1 op S2 vtemp = v1 op v2 simplify(Stemp; vtemp) ! hS3; v3i
Here op is the \expanded" form of the operator where the structure-vector pair is computed plainly. The equations above show that Stemp depends only on S1 and S2, and it is the same for vtemp with respect to v1 and v2.The simplify( ; ) function represents the pruning process, which takes place when all the leaf nodes with the same parent share the same value. In this case, such leaves can be pruned, and their value is assigned to the parent itself. This process is repeated until there are no leaves with the same value and the same parent in any location of the tree (see gure 4). Such a general formulation of the e ects produced by an operator on a couple of MADDs can be stored in memory as Abstract Result (ABR). ABRs are de ned recursively to save both memory and computation too. An ABR is a t-uple hM1; M2; Op; M3; F i, where M1, M2 and M3 are MADDs, Op is the operator that combines M1, M2 and returns M3, while F is a list of relationships between the variables in M1, M2 and M3, which in turn depend on Op. We applied the abstraction process described so far, to MADDs also by replacing its labels with non uni ed variables. The resulting structure-vector pairs have been called MetaMetaADDs (MMADD) (see gure left v1 p right left v2 v3 p
+ right left p right left
p v4 w1 w2 w3 = right left w4 s1 p 5). We called such computational entity meta-structure M S. It has neither values nor labels: all its elements are variables. M S is coupled with a corresponding vector v, which contains variable-label couples (see Figure 5). The de nition of MetaMetaStructure operators, their abstraction, and the concept of ABR remain unchanged also at this level of abstraction. 4
Discussion of the Presented Formalism and Conclusions The generalizations of ADDs to second- and third-order logic that were introduced in the previous section, allow managing MDPs in a more e cient way than a plain rst-order logic approach. Most part of MDPs used currently, share many regularities in either transition or reward function. As said before, such functions can be described by ADDs. If these regularities appear, ADDs are made up by sub-ADDs sharing the same structures. In these case, computing a plan involves many times the same structure with the same elaboration in di erent steps of the process. Our formalism allows to compute them only once and save it in a second- and third-order ABR. Every time the agent has to compute structures that have been used already, it can retrieve the proper ABR to make the whole computation faster. Computation can be reduced also by comparing results in di erent MDPs. In many cases, two MDPs can share common descriptions of the world, similar actions, or goals, so the results found for a MDP could be suitable for the other one. A second-order description allows comparing MDPs that manage problems de ned in similar domains, with the same structure but di erent values. Finally, a third-order description allows to compare MDPSs, which manage problems de ned in di erent domains but own homomorphic structures. In this case, every second- and third- order ABR computed for the rst MDP can be useful to the other one. This knowledge can be shared by di erent agents. Adding ABRs to the knowledge base enlarges the knowledge of the agent, and reduces the computational e ort but implies a memory overhead. Our future investigation will be devoted to devise more e cient ways for storing and retrieving ABRs thus improving the overall performances of the agent.