# Proceedings

The 2011 Imperial College Computing Student Workshop proceedings are available online as well as individual submissions below.

### Combining Markov Decision Processes with Linear Optimal Controllers

#### Ekaterina Abramova, Daniel Kuhn, and Aldo Faisal

##### Imperial College London

*Abstract.* Linear Quadratic Gaussian (LQG) control has a known
analytical solution but non-linear problems do not. The state of the art
method used to ﬁnd approximate solutions to non-linear control problems
(iterative LQG) carries a large computational cost associated with
iterative calculations. We propose a novel approach for solving
nonlinear Optimal Control (OC) problems which combines Reinforcement
Learning (RL) with OC. The new algorithm, RLOC, uses a small set of
localized optimal linear controllers and applies a Monte Carlo algorithm
that learns the mapping from the state space to controllers. We
illustrate our approach by solving a non-linear OC problem of the
2-joint arm operating in a plane with two point masses. We show that
controlling the arm with the RLOC is less costly than using the Linear
Quadratic Regulator (LQR). This ﬁnding shows that non-linear optimal
control problems can be solved using a novel approach of adaptive RL.

### Neural-Symbolic Cognitive Agents: Architecture and Theory

#### H.L.H. de Penning, A.S. d'Avila Garcez, L.C. Lamb, J-J.C. Meyer

##### TNO Behaviour and Societal Sciences, City University London, Universidade Federal do Rio Grande do Sul, Utrecht University

*Abstract.* In real-world applications, the effective integration of
learning and reasoning in a cognitive agent model is a difficult task.
However, such integration may lead to a better understanding, use and
construction of more realistic models. Unfortunately, existing models
are either oversimplified or require much processing time, which is
unsuitable for online learning and reasoning. Currently, controlled
environments like training simulators do not effectively integrate
learning and reasoning. In particular, higher-order concepts and
cognitive abilities have many unknown temporal relations with the data,
making it impossible to represent such relationships by hand. We
introduce a novel cognitive agent model and architecture for online
learning and reasoning that seeks to effectively represent, learn and
reason in complex real-world applications. The agent architecture of the
model combines neural learning with symbolic knowledge representation.
It is capable of learning new hypotheses from observed data, and
inferring new beliefs based on these hypotheses. Furthermore, it deals
with uncertainty and errors in the data using a Bayesian inference
model. The model has successfully been applied in real-time simulation
and visual intelligence systems.

### Time-Bounded Veriﬁcation of CTMCs against MTL speciﬁcations

### Taolue Chen, Marco Diciolla, Marta Kwiatkowska, and Alexandru Mereacre

##### Oxford University

*Abstract.* In this paper we study time-bounded veriﬁcation of a ﬁnite
continuoustime Markov chain (CTMC) C against a real-time speciﬁcation,
provided as a metric temporal logic (MTL) property ϕ. The key question
is: what is the probability of the set of timed paths of C that satisfy
ϕ over a time interval of ﬁxed, bounded length? We provide approximation
algorithms to solve these problems. We ﬁrst derive a bound N such that
timed paths of C with at most N discrete jumps are sufﬁcient to
approximate the desired probability up to ε. Then, for each discrete
(untimed) path σ of length at most N , we generate timed constraints
over variables determining the residence time of each state along σ,
depending on the real-time speciﬁcation under consideration. The
probability of the set of timed paths, determined by the discrete path
and the associated timed constraints, can thus be formulated as a
multidimensional integral. Summing up all such probabilities yields the
result.

### MASSPA-Modeller: A Spatial Stochastic Process Algebra modelling tool

#### Marcel C. Guenther and Jeremy T. Bradley

##### Imperial College London

*Abstract.* We introduce MASSPA–Modeller, a visual modelling tool for
the recently developed spatial stochastic process algebra MASSPA which
describes Markovian Agent Models (MAM)s. The major advantage of using a
visual editor to generate MASSPA models is that the laborious task of
modelling the communication between agents is partially automated by the
tool. Furthermore the tool can separately check the correctness of local
and spatial aspects of the model and thereby help users to ﬁnd mistakes.
For the analysis of the resulting models MASSPA–Modeller uses the
powerful GPA–analyser engine. Additionally we brieﬂy summarise the
latest developments in spatial stochastic process algebras.

### Argumentation and Temporal Persistence

#### E. Hadjisoteriou and A. Kakas

##### University of Cyprus

*Abstract.* We study how the problem of temporal projection can be
formalized in terms of argumentation. In particular, we extend earlier
work of translating the language E for Reasoning about Actions and
Change into a Logic Programming argumentation framework, by introducing
new types of arguments for (i) backward persistence and (ii) persistence
from observations. This forms a conservative extension of the language E
that gives semantic meaning to domains that cannot be interpreted in the
language E.

### Facial Action Recognition using sparse appearance descriptors and their pyramid representations

#### Bihan Jiang, Michel F. Valstar, and Maja Pantic

##### Imperial College London, University of Twente

*Abstract.* Most existing work on automatic analysis of facial
expressions has focused on a small set of prototypic emotional facial
expressions such as fear, happiness, and surprise. The system proposed
here enables detection of a much larger range of facial behaviour by
detecting facial muscle actions (action units, AUs). It automatically
detect all 9 upper face AUs using local apperance descriptors.
Meanwhile, the merits of the family of local binary pattern descriptors
are investigated. We compare Local Binary Patterns, Local Phase
Quantisation, Pyramid Local Binary Pattern, as well as our proposed
descriptors Block-based Pyramid Local Binary Pattern and Block-based
Pyramid Local Phase Quantisation for AU detection. Results show that our
proposed descriptor Block-based pyramid Local Binary Pattern outperforms
all other tested methods for the problem of FACS Action Unit analysis
and the systems that utilise pyramid representation outperform those
that use basic appearance descriptors.

### Note on a Dichotomy for the Classes W[P](C) Deﬁned via Symmetric Connectives

#### Bjorn Lellmann

##### Imperial College London

*Abstract.* Adopting a generalised notion of connectives as
ptime-computable symmetric boolean functions, for ﬁnite sets C of such
connectives the classes W[P](C) are deﬁned via the parameterised
weighted satisﬁability problem for circuits with C-gates. This note will
prove the following dichotomy result: for all ﬁnite sets C of
connectives W[P](C) = FPT or W[P](C) = W[P].

### Agent Oriented Programming: from Revolution to Evolution (Position Paper)

#### Alex Muscar

##### University of Craiova

*Abstract.* Despite being around for quite some time, agents have failed
to gain wide acceptance. Their AI heritage has forced them into a niche
from which they cannot seem to escape: being the vehicle of AI
experimentation. Even though the premises of Agent Oriented Programming
(AOP) is a revolutionary departure from Object Oriented Programming
(OOP) the vision has not materialized. In this paper we propose taking a
step back and looking at AOP as an evolution from OOP. Rather than
viewing agents as specialized AI tools, we adopt a view on agents as a
generic metaphor for building complex software systems. The guiding
lines of our approach are: (i) overall conceptual simplicity; and (ii)
the use of programming languages as the main means of expression. We
will explore some paradigms and approaches that we think can greatly
beneﬁt the view of agents as an evolution from OOP.

### Conditional Labelling for Abstract Argumentation

#### Guido Boella, Dov M. Gabbay, Alan Perotti, Leendert van der Torre, and Serena Villata

##### Universita di Torino, King’s College London, University of Luxembourg, INRIA

*Abstract.* Agents engage in dialogues having as goals to make some
arguments acceptable or unacceptable. To do so they may put forward
arguments, adding them to the argumentation framework. Argumentation
semantics can relate a change in the framework to the resulting
extensions but it is not clear, given an argumentation framework and a
desired acceptance state for a given set of arguments, which further
arguments should be added in order to achieve those justiﬁcation
statuses. Our methodology, called conditional labelling, is based on
argument labelling and assigns to each argument three propositional
formulae. These formulae describe which arguments should be attacked by
the agent in order to get a particular argument in, out, or undecided,
respectively. Given a conditional labelling, the agents have a full
knowledge about the consequences of their attacks on the acceptability
of each arguments, without having to recompute the overall labelling of
the framework for each possible set of attacks they may raise.

### A Persuasive Dialogue Game for Coalition Formation

#### Luke Riley

##### University of Liverpool

*Abstract.* In this paper, I propose a formal dialogue framework that
enables autonomous agents to engage in a process of practical reasoning,
in which they can propose to form coalitions that perform joint actions,
using argumentation. An argumentation scheme is used to drive this
coalition formation process that results in qualitative payoffs. This
paper builds on existing work that uses value-based argumentation in the
context of a dialogue system, which has been empirically veriﬁed. This
framework is designed explicitly for closed cooperative systems where
agents hold different preferences.

### Model-based Self-Adaptive Components: A Preliminary Approach

#### Pedro Rodrigues and Emil Lupu

##### Imperial College London

*Abstract.* Due to the increasing scale, complexity, dynamicity and
heterogeneity of modern software systems, it is not feasible to solely
rely upon human management to guarantee a good service level with such
availability demand. Self-managing systems are needed as an eﬀective
approach to deal with those issues by exploiting adaptive techniques to
adjust a system. On top of that, model-based adaptation improves
reliability, hence enhancing trust in self-managing systems. However, a
centralised approach can be too complex to manage thus compromising
system dependability. This paper presents a preliminary decentralised
approach on model-based self-adaptive components.

### Safe, Flexible Recursive Types for Featherweight Java

#### Reuben N. S. Rowe

##### Imperial College London

*Abstract.* This paper presents a type assignment system with recursive
types for Featherweight Java, inspired by the work of Nakano. Nakano’s
innovation consists in adding a modal type constructor which acts to
control the folding of recursive types, resulting in a
head-normalisation guarantee. We build on this approach by introducing a
second modal type constructor which prevents the unfolding of types in
contexts where doing so results in non-termination. Moreover our system
inherits the ﬂexibility of Nakano’s approach, allowing object-oriented
features (such as binary methods) to be typed in a safe and intuitive
way. The work described in this paper is preliminary, and no formal
results are claimed. However, we conjecture that our type system enjoys
strong normalisation and we motivate this by working through some
apposite examples.

### Measuring minimal change in argument premise revision

#### Mark Snaith and Chris Reed

##### University of Dundee

*Abstract.* The ﬁeld of belief revision studies how information can be
given up in the face of new, conﬂicting information, while argumentation
provides methods through which conﬂict can be modelled and the resultant
acceptability of arguments evaluated. Prominent theories of belief
revision depend on the notion of minimal change, measured in terms of
epistemic entrenchment, to determine what beliefs to give up. In this
paper, we take an initial look at the eﬀects of removing an argument
from a system of structured argumentation, in terms of both argument
construction and acceptability, and how these can be used in the
determination of minimal change.

### Applying Algebraic Specifications on Digital Right Management Systems

#### Nikolaos Triantafyllou, Katerina Ksystra, Petros Stefaneas and Panayiotis Frangos

##### National Technical University of Athens

*Abstract.* Digital Right Management (DRM) Systems have been created to
meet the need for digital content protection and distribution. In this
survey paper we present some of the directions of our ongoing research
on the applications of the algebraic specification techniques on mobile
DRM systems.

### Reduction of Variability in Split–Merge Systems

#### Iryna Tsimashenka and William Knottenbelt

##### Imperial College London

*Abstract.* We consider an optimisation problem applicable to systems
that can be represented as split–merge queueing networks with a limited
buﬀer space for processed subtasks. We assume Poisson arrivals and
generally distributed service times. The proposition is to reduce
variability in terms of the diﬀerence in the times of arrival of the
ﬁrst and last subtasks in systems where the release times of the
subtasks can be controlled. This stands in contrast to the overwhelming
majority of research which is focused on reduction of mean response time
or percentiles of response time. We formally deﬁne our notion of
variability in split–merge systems and construct an associated cost
function and optimisation problem. For two case studies we use
simulation to explore the optimisation landscape and to solve the
associated optimisation problem.

### Real-Time Detection of Process Change using Process Mining

#### Phil Weber, Behzad Bordbar, and Peter Tino

##### University of Birmingham

*Abstract.* Process Mining is the discovery of business processes from
log ﬁles. One application is ensuring conformance to prescribed
processes or business rules. Since businesses operate in real time,
needing to quickly react to change, processes change; but how can such
changes be detected? We consider requirements for process mining to
support this: a notion of real time, and methods to compare processes
and detect signiﬁcant change. We present initial results conﬁrming the
validity of the approach.