Eighth Annual Knowledge Representation and Reasoning
Distinguished Lecturer Series
Date Wednesday 22 January, 2003, 14:00, CS103
Robust Knowledge Representation
Better Half an Answer in Time Than a Full Answer Too Late
Frank van Harmelen
Division of Mathematics and Computer Science
Faculty of Sciences
Vrije University
Abstract: The logical roots of knowledge representation (KR) have given the field much of its strength: well formalised foundations with well understood properties. However, the logical roots are also responsible for some of the major weaknesses in KR. Deduction procedures are typically crisp (answers are either yes or no, with no intermediate values), abrupt (answers are available only at the end of the procedure) and inefficient (computation time cannot be traded against the quality of the answer). These unfortunate properties severely limit the applicability of KR, and also do not make a plausible model of realistic reasoning strategies. This talk presents some of our results towards robust forms of KR which, although still firmly rooted in logic, display anytime behaviour: algorithms can be interrupted at any time during their computation, and will provide an approximation of the final answer. We give both theoretical characterisations of such algorithms, as well as practical results obtained in diagnosis and classification.
Date Friday 21 February, 2003, 12:15, CS202J
Title: Visualisation of binary constraint consistency algorithms
Peter Robinson
Department of Computer Science
University of York
Abstract: The Constraint Satisfaction Problem (CSP) is a means of problem specification for which powerful solution techniques exist. Formulating a problem as a CSP is to express it in terms of variables, variable domains and constraints between variables. Understanding the progress of a solution technique using only textual snapshots of these entities is not easy. My graphical visualisation tool aims to provide a means of viewing the execution of several consistency enforcing algorithms. The tool could be useful for a novice to understand the techniques but also for an expert. The expert may use the tool to compare the efficiencies of different yet equivalent specifications for a problem, or to debug / improve an algorithm that he or she had written.
Date Friday 28 February, 2003, 12:15, CS202J
Title: Behavioral Cloning for First-Person Action Games
Max Dyckhoff
Department of Computer Science
University of York
Abstract: The process of Behavioral Cloning as a method
for teaching computers to play games has been greatly investigated. Very little
research has gone into the application of behavioral cloning a real-time
environment however, where the challenges are very different from turn based
games. In real-time games the state changes constantly and quickly, very quick
responses are required from the computer player, and the state of the world can
have many attributes that make it hard to model. This project has been concerned
with logging the actions of a player of Unreal Tournament, and using a decision
tree learner to create a behavioral clone of the player. All of the scripts and
programs concerned with the creation of decision trees have been completed and
tested, and all that remains is to choose a suitable state representation for
each possible action. Too detailed a state may result in too complicated a
decision tree, and too simple a state may leave out some important detail.
Title: Comparing Algorithms for Learning Bayesian Networks from Data
James Kerruish
Department of Computer Science
University of York
Abstract: A Bayesian network is a graphical model that
encodes probabilistic relationships among variables of interest. This paper
compares two algorithms for constructing Bayesian Networks from complete data.
The two algorithms are the UPSM presented by Copper and the MDL presented by
Rissanen. The two algorithms have different theories behind them and a direct
comparison and analysis is presented here.
Title: Behavioural Cloning for Playing Go
Thomas Walker
Department of Computer Science
University of York
Date Friday 7 March, 2003, 12:20, CS202J
The glacier moves: Learning unification grammar rules from PoS-tagged data
James Cussens
Department of Computer Science
University of York
Abstract: The talk reports on very recent work on learning unification grammar rules from PoS-tagged data, and an initial grammar and lexicon. This is a continuation of joint work with Stephen Pulman (Oxford) which has been progressing (at glacial speed) for a number of years. The goal of the current installment is to actually evaluate the effectiveness of our approach using the Wall St. journal corpus. I don't expect to be able to present solid results at this seminar, but will be able to give a progress report. I'm hoping for comments and criticisms on our approach.
Date Friday 14 March, 2003, 12:15, CS202J
Title: Flexible Planning
Ian Miguel
Department of Computer Science
University of York
Abstract: Traditionally, AI planning problems have been cast in terms of
imperative constraints that are either wholly satisfied or wholly violated: all
plan goals must be achieved, and the application of a plan operator in a given
situation is a Boolean issue. This talk argues that this approach is too rigid
to capture the full subtlety of many real problems. Using fuzzy constraints as a
formal foundation, a flexible planning problem is defined that supports the soft
constraints often found in reality by incorporating preferences into operators
and goals. This allows a range of plans to be generated for a given problem,
trading plan length against the number and severity of the compromises made.
Flexible plan synthesis is performed using Flexible Graphplan, an extended
version of the popular Graphplan planner. It is shown how the plan synthesis
process is underpinned by dynamic fuzzy constraint satisfaction. Weaknesses in
the basic synthesis process are then identified and methods by which it can be
improved are examined. Experimental results are presented to demonstrate the
utility of the resulting system. The talk concludes with a discussion of
possible future extensions.
Date Monday 17 March, 2003, 12:15, CS202J
Title: TEAMCORE Research Group
Nathan Schurr
Computer Science Department
University of Southern California
Abstract: The TEAMCORE research group is focused on research on multiagent systems, where multiple agents (including software agents, robots and people) may interact. Our work has typically focused on situations where such interactions are collaborative, often in the form of agent teams. I will look into our three main areas of research: team coordination algorithms and infrastructures, distributed POMDP based theories of multi-agent teamwork, and resource and decision allocation within teamwork using techniques such as distributed constraints.
Date Friday 25 April, 2003, 12:15, CS202J
Title: The Interaction Between Inference and Branching Heuristics
Lyndon Drake
Department of Computer Science
University of York
Abstract: This is a preliminary version of the talk I
will give at the SAT-2003 conference on propositional satisfiability, for a
paper with Alan Frisch. We study the performance impact on a complete SAT
solver of a resolution-based preprocessing algorithm, and show that its poor
performance is largely due to the interaction between the additional implied
clauses and the branching heuristic used by the SAT solver.
Date Friday 2 May, 2003, 12:15, CS202J
Title: An introduction to Reinforcement (Q) Learning
Daniel Kudenko
Department of Computer Science
University of York
Reinforcement Learning (RL) is a powerful and widely used
technique to implement learning in agents. RL is based on the carrot-and-stick
principle, i.e., the agent is rewarded for "good" behavior and
punished for "bad" actions. This talk will introduce Q learning, the
most popular RL variant. I will focus on Q learning from a single agent
perspective, but also touch on RL in the multi-agent context. No prerequisite
knowledge will be assumed in the seminar.
Date Tuesday 6 May, 2003, 12:15, CS202J
Title: Modelling and Solving English Peg Solitaire
Ian Miguel
Department of Computer Science
University of York
Abstract: Peg Solitaire is a well known puzzle which can prove difficult despite its simple rules. Pegs are arranged on a board such that at least one `hole' remains. By making draughts-like moves, pegs are gradually removed until no further moves are possible or some goal configuration is achieved. In this paper, we consider the English variant, consisting of a board in a cross shape with 33 holes. Modelling Peg Solitaire via CP or OR techniques presents a considerable challenge and is examined in detail. The merits of the resulting models are discussed and they are compared empirically. Since the sequential nature of the puzzle naturally conforms to a planning problem, we also present an experimental comparison with several leading AI planning systems. Other variants of the puzzle, such as `fool's Solitaire' are also considered.
Date Friday 9 May, 2003, 12:15, CS202J
Title: Learning to coordinate using commitment sequences in cooperative multi-agent systems
Spiros Kapetanakis
Department of Computer Science
University of York
Abstract: I will report on an investigation of the
learning of coordination in cooperative multi-agent systems. Specifically, only
solutions that are applicable to independent agents i.e. agents that do not
observe one another's actions will be considered. In a previous seminar, I have
presented a reinforcement learning approach that converges to the optimal joint
action even in scenarios with high miscoordination costs. In this seminar, I
will present a novel approach based on reward estimation with a shared
action-selection protocol that is applicable in fully stochastic
environments where mutual observation of actions is not possible.
Computer Science Department Seminar Series
Date Wednesday 14 May, 2003, 14:00, Room 103
Title: Evolving Social Behaviour and Language in a Multi-Agent System
Dimitar Kazakov
Department of Computer Science
University of York
The talk will discuss kinship-driven altruism as a possible basis for the emergence of co-operation and linguistic communication in a society of simulated agents. The first part of the talk will focus on the role of a hypothetical inherited feature (gene) promoting altruism between relatives as a factor for survival. In the reported work, classical Darwinism and Neo-Darwinism are compared, and the principles of the latter implemented in the system. The experiments study the factors that influence the successful propagation of altruistic behaviour in the population. The results show that the natural phenomenon of kinship-driven altruism can be successfully replicated in a multi-agent system, which implements a model of natural selection different from the one commonly used in genetic algorithms and multi-agent systems, and closer to nature. The second part of the talk will present joint work with Mark Bartlett on an approach to simulating the evolution of language. Here language evolution is seen as a form of multi-agent learning which allows a population to improve performance as measured by its exploitation of resources. A model is presented in which a population of agents is able to evolve a shared grammatical language from a purely lexical one. Our approach is inspired by Bruce Chatwin's description of a form of spoken tradition among the Australian aboriginal nomads, in which the fixed migration route followed by each tribe is memorised and passed on in the form of a song (or songline) describing the route as a list of landmarks. From our point of view, sharing the knowledge of a songline within the tribe is clearly a form of kinship-driven altruism, whereas inter-tribal exchange of (parts of) songlines can be seen as reciprocal altruism increasing the chances of survival of both speakers.
Date Friday 16 May, 2003, 12:15, CS202J
Title: A constraint-programming approach to student project allocation
Martin Thorn
Department of Computer Science
University of York
The student-project allocation problem is the problem of finding an optimum assignment of student to projects within the computer science department in the University of York. The problem has been successfully modelled as a stable marriage problem since 1998. I will examine the possibility of encoding student-project allocation as a stable marriage problem in a constraint logic programming manner. I will show that it is computationally feasible to use such an encoding, and that the performance is competitive with the existing system. I will demonstrate that the constraint logic programming encoding provides the potential for greater program flexibility in order to provide alternate functionality to the problem. I will show that an alternate SMT (Stable Marriage with Ties) encoding could be implemented in a constraint logic manner, I will then show that this specific method of encoding SMT cannot as of yet solve the student-project allocation problem in a feasible manner.
Date Friday 23 May, 2003, 12:15, CS202J
Title: Beyond SAT: Exploiting Structure in Walksat
Peter Nightingale
Department of Computer Science
University of York
Many techniques are currently used for solving structured constraint
satisfaction problems (CSP), including variants of local search, and translation
into other problems. Walksat is a successful algorithm for the propositional
satisfiability problem (SAT), and is often used with translated CSPs. This
project considers building constraint expressions (such as all-different or
less-than) into Walksat, in place of their SAT encodings. Direct expression of
constraints is more compact than the encoding, and allows more focused repairs.
The potential benefits are time and space savings, and reduced run length.
Mark Minichiello
Department of Computer Science
University of York
Abstract: One way to solve a constraint satisfaction
problem is to transform it to SAT and then solve it with a solver for SAT. A
recent paper by Ian Gent
presents two ways to perform the transformation to SAT and compares on each
translation the performance of two solvers -- one based on the
Davis-Putnam procedure and one based on stochastic local search. I explore a new
way of solving a constraint satisfaction problem: to transform it to NB-SAT and
then solve it with a solver for NB-SAT. Many desirable properties of Gent's
transformations carry over to the NB-SAT generalisations. Just as arc
consistency in the original CSP can be established by unit propagation on the
"support" SAT encoding, the same is also true for the new
"NB-support" NB-SAT encoding, giving an optimal worst case time
algorithm for arc consistency. I consider the performance of the new
translations with two NB-SAT solvers: NB-WalkSAT (based on stochastic local
search) and NB-Satz (based on the DPLL procedure). I show that the stochastic
local search algorithm NB-WalkSAT on the NB-SAT transformations performs many
times better than WalkSAT on the SAT transformations. With DPLL based
procedures, none of the transformations give uniformly best performance.
Date Friday 30 May, 2003, 12:15, CS202J
Title: Simulating the Evolution of Language using Multi-Agent Systems
Mark Bartlett
Department of Computer Science
University of York
This talk presents an approach to simulating the evolution of
language in which communication is viewed as an emerging phenomenon with both
genetic and social
components. While much research has been carried out using multi-agent
systems into culturally based language, the underlying genetic nature of the
speakers is
usually completely overlooked. This leads to a situation in which language
is the central goal of the simulation and important questions, such as why
language use should be promoted by natural selection, are ignored. The
research presented centres on a specifically developed artificial life based
scenario with a real world analogue. Within this setting, the use of
language by agents is permitted, but not forced, and simulation is carried out
with a range of parameter settings in order to establish in what situations we
should expect language use to prosper.
Distinguished Lecturer Computer Science Department Seminar Series
Date Wednesday 4 June, 2003, 14:00, CS103
Title: Integrating Constraint Programming and Integer Programming
John Hooker
Graduate School of Industrial Administration
Carnegie Mellon University
Constraint programming (CP) and integer programming (IP) are two very successful technologies developed respectively in the computer science and operations research communities. The two methods tends to have complementary strengths. For example, CP is good at scheduling and IP at cost minimization. If a problem contains both elements, however, both methods may fail unless they are somehow combined and applied simultaneously. This can be done by observing that CP and IP are special cases of a single problem-solving strategy. This talk will review some recent work in this active area of research. The talk provides simple examples of how CP and IP solve problems and does not presuppose background in either area.
Date Friday 20 June, 2003, 12:15, CS202J
Title: Modelling the Emergence of Case
Joanna Moy
Department of Computer Science
University of York
A further investigation into the role of linguistic evolution
(as an alternative to biological evolution) in the emergence of syntax is
presented. This follows on from the idea that languages themselves are
evolving entities, which adapt to be easily acquired by the human learner.
It has already been shown that it is possible for the
rudimentary elements of syntax, i.e. compositionality and recursiveness, to
emerge in a population of language learning agents without any specific
linguistic knowledge and in the absence of selection for communicative ability.
Attempts are made here to extend this framework to cover another important
aspect of natural language: the use of a case system to make distinctions
between thematic roles.
Date Monday 14 July, 2003, 12:15, CS202J
Graph Mining: Performance and Scalability Issues Using Relational Database Techniques
Sharma Chakravarthy
Information Technology Laboratory and
Computer Science and Engineering Department
The University of Texas at Arlington, USA
Data mining aims at discovering useful and previously unknown patterns from the datasets. Database mining performs mining directly on data stored in Data Base Management Systems. Several SQL-based approaches for (association rule) mining have been studied in the literature.
The main focus of this presentation will be to indicate how other types of mining can be done directly on databases. We have chosen graph mining as an example as its representation as well as processing are challenging considering the abstractions and computations supported by a DBMS. Graph mining is about identifying repeating instances of a substructure in a graph and compressing the graph (using the minimum description length principle) to derive a smaller graph. This approach is useful for detecting trends, frauds, similarity of web structures, protein structures etc.
We will focus on the design and development of algorithms for graph mining (SUBDUE) using relational DBMS. We develop several approaches for discovering the repetitive substructures in a graph. Each approach is analyzed and optimized further to improve its performance. Three different approaches cursor-based, embedded SQL, and User Defined Functions (or UDFs) are studied. We compare the performance of database approaches with the performance of the main memory algorithm. We were able to improve upon the main memory algorithm both in run time and the size of the problem. The larger goal of this thesis is to achieve scalability.
Date Friday 12 September, 2003, 12:15, CS202J
Title: GA-based hybrid techniques for real-world scheduling problems
Keshav Dahal
MOSAIC Research Centre
School of Informatics
University of Bradford
Abstract:There is a significant requirement for the development and application of new optimisation techniques for industrial scheduling problems to achieve a better schedule with significant economic and operational impact. During the past decades the role of optimisation in scheduling problems has steadily increased in such diverse areas as, electrical utilities, chemical industries, computer science and telecommunications. This talk will focus on an investigation of how mathematical and heuristic optimisation approaches may be hybridised and implemented within a GA framework for solving short term and long term scheduling problems. Four case studies will be presented that exist in electric power utilities and process facilities: generator maintenance scheduling, generation scheduling, storage tanks scheduling of a water treatment facility, and schedule of operations of a bulk handling port system. The choice of these four problems is not only an attempt to exhibit variety but, also to convey a sense of the phenomena that accompany many complex optimisation problems. The results obtained are encouraging and in many cases yield an improvement over those obtained by alternative techniques. These applications demonstrate that the GA-based hybrid approach can form the basis of an effective optimisation tool for a variety of complex problems.
Date Friday 10 October, 2003, 13:45, CS202J
Title: Pushing log-based reconciliation.
Youseff Hamadi
Microsoft Research Cambridge
Abstract: When nomadic applications are sharing replicated objects incoherences can occur from the lack of global connectivity. Log-based reconciliation can then be used to get back to a globally consistent common state. It starts from the logs of actions performed by each applications and tries to minimises the loss (lost actions) while computing a common consistent state. [Fages 01] tried to solve this problem by using constraint programming and local search. One of his finding was that 1) complete search can find optimal solutions to problems involving up to 250 actions. 2) local search gives poor results due to the mix between boolean and integer variables. In this work we build on these results to explore a third path: incomplete Branch and Bound search. The idea is to distinguish critical actions from less critical ones. The algorithm starts with the computation of an optimal schedule for critical actions and propagate it to the remaining problem. First results show a speed-up of more than 100 with a quality loss of up to 7% over a complete search.
Date Friday 17 October, 2003, 12:15, CS202J
Title: Extending the CLP engine for reasoning under uncertainty
Nicos Angelopoulos.
AIG member
Abstract: The talk will consist of two parts. First twenty minutes will be a rehearsal for a conference talk. In this a general framework will be presented, which uses constraint logic programming ideas for integrating uncertainty reasoning in logic programming. In clp(pfd(Y)) the constraint store is used for storing probabilistic information and inference and finite domains as sets of basic elements over which distributions can be defined. An instantiation of the framework, clp(pfd(c)) and experimental results comparing a simple cryptographic example in clp(pfd(c)) and clp(fd) will also be covered. In the second part, I will describe a prototype implementation and the coding of another probabilistic puzzle (Monty Hall).
Date Friday 28th November, 2003, 12:15, CS202J
Title: Bayesian Nets for Beginners
James Cussens,
Dept of Computer Science, University of York .
Abstract:
This seminar will be comprehensible to those without previous
exposure to Bayesian nets. The aim is that you can go away knowing
what a Bayesian network is; and with a basic feel for how
probabilities are calcluated in Bayesian networks. The seminar will be
largely demo-driven using the Netica and WINBUGS systems. Netica
derives from the "probabilistic expert system" tradition and I will
use it to demonstrate exact inference of probabilities. WINBUGS is a
tool for statistical modelling which I will use to demonstrate
approximate inference using Gibbs sampling.
Date Friday 5th December, 2003, 12:15, CS202J
Title: Evolutionary Algorithms with Extended Fitness
Dimitar Kazakov,
Dept of Computer Science, University of York .
Abstract:
The notion of fitness has been assigned various meanings, of which
only the oldest, expressing individual reproductive success, has been
explicitly used in Evolutionary Algorithms (EAs) so far. This work
suggests that the use of other well-known definitions borrowed from
biology that are based on the success with which genes replicate and
propagate themselves in the gene pool could be beneficial to EAs by
replacing ad-hoc scaling techniques with means of maintaining genetic
diversity that draw clear analogies with nature. The resulting
improvement in performance is demonstrated on the problem of
continuous function optimisation.