Learning to play Pac-Man: An evolutionary, rule-based approach

Pac-Man is a well-known, real-time computer game that provides an interesting platform for research. We describe an initial approach to developing an artificial agent that replaces the human to play a simplified version of Pac-Man. The agent is specified as a simple finite state machine and ruleset. with parameters that control the probability of movement by the agent given the constraints of the maze at some instant of time. In contrast to previous approaches, the agent represents a dynamic strategy for playing Pac-Man, rather than a pre-programmed maze-solving method. The agent adaptively "learns" through the application of population-based incremental learning (PBIL) to adjust the agents' parameters. Experimental results are presented that give insight into some of the complexities of the game, as well as highlighting the limitations and difficulties of the representation of the agent.

A diffusion approach to approximating preservation probabilities for gene duplicates

Consider a haploid population and, within its genome, a gene whose presence is vital for the survival of any individual. Each copy of this gene is subject to mutations which destroy its function. Suppose one member of the population somehow acquires a duplicate copy of the gene, where the duplicate is fully linked to the original gene's locus. Preservation is said to occur if eventually the entire population consists of individuals descended from this one which initially carried the duplicate. The system is modelled by a finite state-space Markov process which in turn is approximated by a diffusion process, whence an explicit expression for the probability of preservation is derived. The event of preservation can be compared to the fixation of a selectively neutral gene variant initially present in a single individual, the probability of which is the reciprocal of the population size. For very weak mutation, this and the probability of preservation are equal, while as mutation becomes stronger, the preservation probability tends to double this reciprocal. This is in excellent agreement with simulation studies.

On parameter estimation in population models

We describe methods for estimating the parameters of Markovian population processes in continuous time, thus increasing their utility in modelling real biological systems. A general approach, applicable to any finite-state continuous-time Markovian model, is presented, and this is specialised to a computationally more efficient method applicable to a class of models called density-dependent Markov population processes. We illustrate the versatility of both approaches by estimating the parameters of the stochastic SIS logistic model from simulated data. This model is also fitted to data from a population of Bay checkerspot butterfly (Euphydryas editha bayensis), allowing us to assess the viability of this population. (c) 2006 Elsevier Inc. All rights reserved.

UML approach to the generation of test sequences for Java-based concurrent systems

Starting with a UML specification that captures the underlying functionality of some given Java-based concurrent system, we describe a systematic way to construct, from this specification, test sequences for validating an implementation of the system. The approach is to first extend the specification to create UML state machines that directly address those aspects of the system we wish to test. To be specific, the extended UML state machines can capture state information about the number of waiting threads or the number of threads blocked on a given object. Using the SAL model checker we can generate from the extended UML state machines sequences that cover all the various possibilities of events and states. These sequences can then be directly transformed into test sequences suitable for input into a testing tool such as ConAn. As an illustration, the methodology is applied to generate sequences for testing a Java implementation of the producer-consumer system. © 2005 IEEE

Multi-threaded Communicating Agents in Qu-Prolog

In this tutorial paper we summarise the key features of the multi-threaded Qu-Prolog language for implementing multi-threaded communicating agent applications. Internal threads of an agent communicate using the shared dynamic database used as a generalisation of Linda tuple store. Threads in different agents, perhaps on different hosts, communicate using either a thread-to-thread store and forward communication system, or by a publish and subscribe mechanism in which messages are routed to their destinations based on content test subscriptions. We illustrate the features using an auction house application. This is fully distributed with multiple auctioneers and bidders which participate in simultaneous auctions. The application makes essential use of the three forms of inter-thread communication of Qu-Prolog. The agent bidding behaviour is specified graphically as a finite state automaton and its implementation is essentially the execution of its state transition function. The paper assumes familiarity with Prolog and the basic concepts of multi-agent systems.

Interfacing ASM with the MDG tool

In this paper we describe an approach to interface Abstract State Machines (ASM) with Multiway Decision Graphs (MDG) to enable tool support for the formal verification of ASM descriptions. ASM is a specification method for software and hardware providing a powerful means of modeling various kinds of systems. MDGs are decision diagrams based on abstract representation of data and axe used primarily for modeling hardware systems. The notions of ASM and MDG axe hence closely related to each other, making it appealing to link these two concepts. The proposed interface between ASM and MDG uses two steps: first, the ASM model is transformed into a flat, simple transition system as an intermediate model. Second, this intermediate model is transformed into the syntax of the input language of the MDG tool, MDG-HDL. We have successfully applied this transformation scheme on a case study, the Island Tunnel Controller, where we automatically generated the corresponding MDG-HDL models from ASM specifications.

Existence and uniqueness of Q-processes with a given finite μ-invariant measure

Let Q be a stable and conservative Q-matrix over a countable state space S consisting of an irreducible class C and a single absorbing state 0 that is accessible from C. Suppose that Q admits a finite mu-subinvariant measure in on C. We derive necessary and sufficient conditions for there to exist a Q-process for which m is mu-invariant on C, as well as a necessary condition for the uniqueness of such a process.

Coherent state construction of representations of osp(2|2) and primary fields of osp(2|2) conformal field theory

Representations of the superalgebra osp(2/2)(k)((1)) and current superalgebra. osp(2/2)k in the standard basis are investigated. All finite-dimensional typical and atypical representations of osp(2/2) are constructed by the vector coherent state method. Primary fields of the non-unitary conformal field theory associated with osp(2/2)(k)((1)) in the standard basis are obtained for arbitrary level k. (C) 2004 Elsevier B.V. All rights reserved.

Optimal cloning for finite distributions of coherent states

We derive optimal cloning limits for finite Gaussian distributions of coherent states and describe techniques for achieving them. We discuss the relation of these limits to state estimation and the no-cloning limit in teleportation. A qualitatively different cloning limit is derived for a single-quadrature Gaussian quantum cloner.

The effect of finite bandwidth squeezed light on entanglement creation in the Dicke model

We analyse the relation between local two-atom and total multi-atom entanglements in the Dicke system composed of a large number of atoms. We use concurrence as a measure of entanglement between two atoms in the multi-atom system, and the spin squeezing parameter as a measure of entanglement in the whole n-atom system. In addition, the influence of the squeezing phase and bandwidth on entanglement in the steady-state Dicke system is discussed. It is shown that the introduction of a squeezed field leads to a significant enhancement of entanglement between two atoms, and the entanglement increases with increasing degree of squeezing and bandwidth of the incident squeezed field. In the presence of a coherent field the entanglement exhibits a strong dependence on the relative phase between the squeezed and coherent fields, that can jump quite rapidly from unentangled to strongly entangled values when the phase changes from zero to pi. We find that the jump of the degree of entanglement is due to a flip of the spin squeezing from one quadrature component of the atomic spin to the other component when the phase changes from zero to pi. We also analyse the dependence of the entanglement on the number of atoms and find that, despite the reduction in the degree of entanglement between two atoms, a large entanglement is present in the whole n-atom system and the degree of entanglement increases as the number of atoms increases.

Resources required for exact remote state preparation

It has been shown [M.-Y. Ye, Y.-S. Zhang, and G.-C. Guo, Phys. Rev. A. 69, 022310 (2004)] that it is possible to perform exactly faithful remote state preparation using finite classical communication and any entangled state with maximal Schmidt number. Here we give an explicit procedure for performing this remote state preparation. We show that the classical communication required for this scheme is close to optimal for remote state preparation schemes of this type. In addition we prove that it is necessary that the resource state have maximal Schmidt number.

On the steady-state assumption and its application to the rotating disk voltammetry of adsorbed enzymes

Rotating disk voltammetry is routinely used to study electrochemically driven enzyme catalysis because of the assumption that the method produces a steady-state system. This assumption is based on the sigmoidal shape of the voltammograms. We have introduced an electrochemical adaptation of the King-Altman method to simulate voltammograms in which the enzyme catalysis, within an immobilized enzyme layer, is steadystate. This method is readily adaptable to any mechanism and provides a readily programmable means of obtaining closed form analytical equations for a steady-state system. The steady-state simulations are compared to fully implicit finite difference (FIFD) simulations carried out without any steady-state assumptions. On the basis of our simulations, we conclude that, under typical experimental conditions, steady-state enzyme catalysis is unlikely to occur within electrode-immobilized enzyme layers and that typically sigmoidal rotating disk voltammograms merely reflect a mass transfer steady state as opposed to a true steady state of enzyme intermediates at each potential.

On the existence of uni-instantaneous Q-processes with a given finite mu-invariant measure

Let S be a countable set and let Q = (q(ij), i, j is an element of S) be a conservative q-matrix over S with a single instantaneous state b. Suppose that we are given a real number mu >= 0 and a strictly positive probability measure m = (m(j), j is an element of S) such that Sigma(i is an element of S) m(i)q(ij) = -mu m(j), j 0 b. We prove that there exists a Q-process P(t) = (p(ij) (t), i, j E S) for which m is a mu-invariant measure, that is Sigma(i is an element of s) m(i)p(ij)(t) = e(-mu t)m(j), j is an element of S. We illustrate our results with reference to the Kolmogorov 'K 1' chain and a birth-death process with catastrophes and instantaneous resurrection.