Modular self-organization for a long-living autonomous agent

1 Modelling A Mono-Task Autonomous Agent

Markov Decision processes [Puterman, 1994] provide the theoretical foundations of challenging problems such as plan­ ning under uncertainty and reinforcement learning [Sutton and Barto, 1998]. They stand for a fundamental model for se­ quential decision making and they have been applied to many real worls problems [Sutton, 1997]. This section describes this formalism and presents a general scheme for approach­ ing difficult problems (that is problems in large domains) .

A Markov Decision Process (MDP) is a controlled stochas­ tic process satisfying the Markov property with rewards (nu­ merical values) assigned to state-control pairs. Formally, an MDP is a four-tuple (S, A, T, R) where S is the state space, A is the action space, Tis the transition function and R is the reward function. Tis the state-transition probability distribu­ tion conditioned by the control :

R(s, a) E 1R is the instantaneous reward for taking action a E A in state S.

The usual MDP problem consists in finding an optimal pol­ icy, that is a mapping 1r : S --+ A from states to actions, that maximises the following performance criterion, also called value function of policy 1r:

Abstract

The aim of this paper is to provide a sound frame­ work for addressing a difficult problem: the auto­ matic construction of an autonomous agent's mod­ ular architecture. We briefly present two appar­ ently uncorrelated frameworks: Autonomous plan­ ning through Markov Decision Processes and Ker­ nel Clustering. Our fundamental idea is that the former addresses autonomy whereas the latter al­ lows to tackle self-organizing issues. Relying on both frameworks, we show that modular self­ organization can be formalized as a clustering prob­ lem in the space of MDPs. We derive a modular self-organizing algorithm in which an autonomous agent learns to efficiently spread n planning prob­ lems over m initially blank modules with m < n.

Introduction

This paper addresses the problem of building a long-living autonomous agent; by long-living, we mean that this agent has a large number of relatively complex and varying tasks to perform. Biology suggests some ideas about the way an­ imals deal with a variety of tasks: brains are made of spe­ cialized and complementary areas/modules; skills are spread over modules. On the one hand, distributing functions and representations has immediate advantages: parallel process­ ing implies reaction speed-up; a relative independence be­ tween modules gives more robustness. Both properties might clearly increase the agent's efficiency. On the other hand, the fact of distributing a system raises a fundamental issue: how does the organization process of the modules happen during the life-time ?

There has been much research about the design of modu­ lar intelligent architectures (e.g. [Theocharous et al., 2000] [Hauskrecht et al. , 1998] [Kaelbling, 1993]). It is neverthe­ less very often the (human) designer who decides the way modules are connected to each other and how they behave with respect to the others. Few works study the construc­ tion of these modules. To our knowledge, there are no ef­ fective works about modular self-organisation except for re­ active tasks (stimulus-response associations) (e.g. [Jacobs et al., 1991] [Digney, 1996]).

It is shown that there exists a unique optimal value function V*; once V* is computed, an optimal policy can immediately be derived (e.g. see [Puterman, 1994]).

In brief, solving an MDP problem amounts to computing the optimal value function. Well-known algorithms for doing so are Value Iteration and Policy Iteration (see [Puterman, 1994]). Their temporal complexity dramatically grows with the number of states [Littman et al., 1995], so they can only be applied in small domains.

In large domains, it is impossible to solve an MDP ex­ actly, so one usually actresses a complexity/quality compro­ mis through an approximation scheme. Ideally, an approxi­ mation scheme for MDPs should consist of a set of tractable algorithms for

• computing an approximate optimal value function
• evaluating (an upper bound of) the approximation error
• improving the quality of approximation (by reducing the approximation error) while constraining the complexity.

The first two points are the fundamental theoretical bases for sound approximation. The third one is often interpreted as a learning process and corresponds to what most Machine Learning researchers study. For convenience, we respectively call these three procedures Approximate(), Error() and Learn(). Then, the practical use of an approximate scheme can be sketched by algorithm 1. One successively applies the

Algorithm 1 A general approximation scheme for a large state MDP

Input: ~large state space MDP M and an initial approximation M. ~

Output: a good approximate value function V*.

Learn() procedure in order to minimize the approximation error; when this is done, one can compute a good approxi­ mate optimal value function.

2 Kernel Clustering

Before addressing the problem of modular self-organization, we need to present the Kernel Clustering paradigm. In [Di­ day, 1973], the author introduces the Kernel Clustering ap­ proach as an abstract generalization of vector quantization. Indeed, the author argues that, in general, a clustering prob­ lem is based on three elements:

• (x;);EJ: a set of data points taken from a data space X
• { L 1 , ·· , Lm}: a set of kernels taken from a kernel space £
• d : X x £ -+ IR +: A distance measure between any data point and any kernel. The smaller the distance d(x, L), the more Lis representative of the point x.

Given a set of kernels { L1 , 00, Lm}, a data point :r is naturally associated to its most representative kernel L(:r:), i.e. the one that is the closest according to distance d:

Conversely, a set of kernels { L 1 , 00 , Lm} naturally induces a partition of the data set (X; )iE I into m classes { cl ' 00' Cm}, each class corresponding to a kernel:

Given a data space, a data set, a kernel space and a distance d(), the goal of the Kernel Clustering problem is to find the set of kernels { Li , 00, L;',.,} that minimizes the distortion D for the data set (x;);Er, which is defined as follows :

A general procedure for suboptimally solving this problem is known as the Dynamic Cluster algorithm [Diday, 1973], which we present in an online version in algorithm 2. It is

Algorithm 2 The on-line dynamic cluster algorithm

Input: A data set (x;)iE/

Output: A set of kernels { L 1 , ·· , Lm} that optimizes the clustering (i.e. that minimizes the distortion)

Initialization:

Let { L 1 , ·. , Lm} be any set of kernels

Iterations:

while the distortion goes on diminishing do

Randomly pick a data point .T from the data set Find the kernel the most representative kernel of x:

Update L so that d(x, L) diminishes

end while

a very intUitive process: for each piece of data x, one finds its most representative kernel L, and one updates L so that it gets even more representative of x. Little by little, one might expect that such a procedure will minimize the global distortion and eventually give a good clustering.

3 Modular Self-Organization

This final section shows how the Kernel Clustering paradigm can be used to formalize a modular self-organization prob­ lem in the MDP framework, the algorithmic solution of which will be given by the on-line Dynamic Cluster procedure (al­ gorithm 2).

If one carefully compares the general learning scheme we have described in order to address a large state space MDP (algorithm 1) and the on-line Dynamic Cluster procedure (al­ gorithm 2), one can see that the former is a specific case of the latter. More precisely, algorithm I solves a simple Kernel Clustering problem where

• the data space is the space of all possible MDPs and the data set is a unique task corresponding to an MDP M

• the kernel space is the space of all possible approxima­ tions and there is one and only one kernel: M
• the distanced is the Error() function .

It is then straightforward to extend this simple clustering problem to a more general one (with n tasks/data points and m approximate models/kernels). Given a set of m approximate models {M1 , ·. , Mm}, an MDP M is naturally associ­ ated to the approximate model M(M) that makes the small­ est error:

As before, a set of approximate models { M 1 , ·. , M m} nat­ urally induces a partition of any set of n MDPs (Mi ) 1 <i<n into m classes { C1 , . · , Cm}, each class corresponding to 1m approximate model :

The transpositon of the on-line Dynamic Cluster Algorithm into the MDP framework (algorithm 3) therefore allows to find a set of m approximate models that globally minimize the approximation error for n MDPs:

In other words, it optimizes the tuning of m modules in

Algorithm 3 Modular Self-Organization

Input: A set of MDPs (Mi )iET

Output: A set of approximate models (M1 , .. , M m) that globally minimizes the approximation error Initialization:

Let (M1 , .. , M m) be any set of approximate models Iterations:

while the global approximation error goes on diminishing do

Randomly pick a task M from the set of MDPs Find the best module for solving M:

end while

order to efficiently solve n tasks, or, as we might say, it self­ organizes the m modules in order to improve the resolution of the n tasks.

Conclusion

In this paper, we have described a general scheme for ad­ dressing large state space Markov Decision Processes. We have then showed how such an approach could be extended to an interesting problem: modular self-organization. Indeed, we have formalized modular self-organization as a clustering problem in the space of MDPs. A natural algorithmic solu­ tion to this clustering problem (algorithm 3) uses an on-line version of the Dynamic Cluster algorithm (algorithm 2). Due to lack of space, we could not show any experimental evalu­ ation; interested readers will find some in [Scherrer, 2003b] and [Scherrer, 2003a].