RA5a: Structure,environment and staffing policyOverview: Since 1996, the Department of Computer Science has continued to produced high quality research in agent-based social simulation, constraint programming, optimisation, machine learning, theoretical computer science and formal methods. The Department has achieved considerable new successes in mobile robots, agents for intelligent buildings, and semi-structured data. RA2 shows a strong profile of publications across groups, for example in leading international journals in Constraint Programming & Optimisation (13 papers of 16) and in Theoretical Computer Science & Formal Methods (14 papers of 20). The Department's research student numbers have grown considerably, with the Robotics and Intelligent Machines group being particularly successful: 4 research students have graduated from this group since 1996, and 21 new students have joined during the same period. Between 1996 and 2000 the Department's staff were awarded research council grants of over £1.3 million, £0.4 million of industrial funding and £0.9 million from EC initiatives.
Research Support: We manage research through a consensual research management plan. The plan is associated with a prioritised agenda, listing actions to support and encourage staff and student research. Plan and agenda are revised annually and the Deputy Head for Research ensures their day-to-day management. She is a member of the Department’s committees for Resource Management, PhD Management, and Research Students' Progress. She liases with the University Research Office and external bodies. Key regular activities include a monthly grants group for internal review and encouragement of grant applications, and three separate weekly research seminar series: one with industrial focus, one run internally to foster communication and our main series with external speakers. We organise an annual 2-day PhD conference with the Department of Electronics. The research plan provides for Departmental PhD awards (currently 10 awards from £2k to £8k pa), and procedures for ensuring strong and responsible PhD recruitment and management. The department sustains the usual "well founded“ environment. Departmental budgets support traditional research activities such as conference fees and travel for staff and students presenting papers. In addition, we operate a specific research development policy. The Department’s Research Endowment Fund provides resources for substantial start-up projects and initiatives (£15k per annum). Probationary junior staff benefit from mentoring and reduced workloads. All new staff hold start-up funds, have priority access to travel budgets, and are encouraged to take up their study leave entitlement within their first 3 years. The research development policy aims to protect academics' research time: a generous budget for Graduate Teaching Assistants (£50k per annum) reduces teaching loads; block time-tabling counters fragmentation; teaching loads are capped; and 5 Teaching Fellows contribute by carrying substantially higher teaching and administration loads than research active staff. This structure operates against the backdrop of the University’s Research Strategy, which entitles staff to 1 term in 7 sabbatical leave, a system of individual research accounts for grant holders, bridging funding for RAs and a University Research Promotion Fund (RPF) for pump-priming funding and special research projects. Since 1996, we have secured over £60k from the RPF. The University’s Research Office provides advice and administrative support for grant applicants.
· Agent-Based and Multi-Agent Systems: Doran (Professor), Callaghan 0.75, Steel 0.75 (Senior Lecturers), Fasli (Lecturer), 1 RA. 4 PhDs awarded, 5 PhDs & 1 MSc current. Grants awarded by British Telecom (2) and Korea-DTI.
· Constraint Programming & Optimisation: Tsang (Professor), Ford (Senior Lecturer), Salhi, Zhang (Lecturers), 4 RAs. 5 PhDs & 3 Masters awarded, 4 PhDs & 1 Masters current. Grants awarded by EPSRC (3), British Telecom (studentship), Japan IRCF and Essex RPF.
· Machine Learning & Pattern Recognition: Lavington (Research Professor), Gan, Lucas, Reynolds, Scott (Senior Lecturers), Lakany (Lecturer), 9 RAs. 6 PhDs & 2 Masters awarded, 2 PhDs current. Grants awarded by EPSRC (4), BBSRC/EPSRC, Post Office UK, British Telecom, EKERNA (2), JISC and Essex RPF (3).
· Natural Language Engineering & Distributed Information Systems: De Roeck, Lowden, Poesio, Steel 0.25 (Senior Lecturers), Kruschwitz, Robinson (Lecturers), Musgrave (Deputy Director, Data Archive), 15.75 RAs. 2 PhDs & 1 Masters awarded, 8 current PhDs. Grants awarded by EPSRC, British Telecom, EC (5), JISC, ESRC and EPSRC Colloquium.
· Robotics & Intelligent Machines: Callaghan 0.25, Hu, Standeven (Senior Lecturers), Colley, Gu, Hagras, Spacek (Lecturers), 2 RAs. 3 PhDs & 1 MSc awarded. 12 PhDs and 9 Masters current. Grants awarded by EPSRC, Centre for Marine & Petroleum Technology, DERA, Royal Society, Guidance Control Systems (CASE studentship), and Essex RPF (4).
· Theoretical Computer Science & Formal Methods: Turner, Higgins (Professors), Cardell-Oliver, Henson (Senior Lecturers), Völker (Lecturer), 3 RAs. 6 PhDs & 1 MSc awarded, 6 PhDs current. Grants awarded by EPSRC (2), British Telecom (studentship), Royal Society (3), NZ FRST, EPSRC Workshop and Essex RPF (2).
References  to  in this section refer to individuals' papers in RA2.
Agent-Based & Multi-Agent Systems
The interests of the group are broad, ranging from mathematical foundations through to applications, and covering both individual agents and multi-agent systems. The group’s long-standing reputation in multi-agent systems has continued to develop, now also covering multi-embedded-agent systems. Doran has played an internationally prominent role in the development of agent-based social simulation as a new method for social investigation . His work has focused on applications in archaeology, anthropology and environmental management  and on the clarification and resolution of key methodological problems . Doran attracted international attention when he introduced the key concept of collective misbelief in multi-agent societies . With Hales (PhD 2000) he has developed computational models of meme dynamics and their social impact. Callaghan’s work on embedded agents and intelligent buildings [1,2,4] included a workable solution to the problem of non-intrusive learning and control that arises from non-deterministic multi-dimensional input vectors. He has developed methods for integrating interactive multicast virtual reality with the web (British Telecom with Electronics Dept). Fasli has developed an integrated logical foundation for developing theories of intelligent agents. She has studied the key notions of Truth, Knowledge, Belief, Desire and Intention both as modal  and as syntactic theories, and in the context of self-reference. Several new types of agents have been uncovered . Notably, Fasli has shown that common knowledge plays a role, as important as self-reference, in her work on the Surprise Examination Paradox . Steel has studied mentalistic predicates in connection with AI planning agents, provided agents with both operational and denotational semantics, and compared their suitability . With Burgess (PhD 1998) he has explored how best to express quantification in partial-order causal link planning [2,3].
Constraint Programming & Optimisation
The Department has a long-standing strength in foundations and applications of machine learning. This group has developed and tested new learning and recognition methods on problems in data mining, speech, video, optical character and face recognition, sensor fusion and human gait analysis. In the SNOUT project and its successors, Scott [2,3] developed novel machine learning techniques for discovering clusters of attributes in large data sets by maximising association with all other attributes. He has developed methods for generating data sets with specified characteristics  and new metrics for characterising the "degree of difficulty" of a data set in order to identify the most suitable data mining procedures for that set. Lavington [1,2,3] and Freitas (PhD 1997) developed generic primitives and new strategies for executing established data mining algorithms efficiently on (parallel) client/server DBMS platforms in a scaleable manner. This research drew on Lavington’s previous work on the Intelligent File Store and made use of large IBM and ICL parallel platforms at Southampton and at Newcastle. Significant improvements in speech recognition techniques have been achieved by Reynolds , using modular neural networks (MNNs) which deliver the performance of context-dependent acoustic modelling, previously unattainable using monolithic networks. Furthermore, Reynolds [2,3,4] has shown that MNNs can combine the complementary information provided by different feature extraction techniques, keeping within a probability density estimation framework. Pattern recognition systems developed by Lucas include novel face recognition , robust word recognition in noisy text images  and handwriting . His algorithms offer state of the art accuracy combined with high learning and recognition speeds. Lakany applies machine learning and pattern recognition methods [1,4] to characterise variations in human gait in pathological conditions such as cerebral palsy [2,3]. Her method extracts generic features that distinguish between normal and pathological cases and produce diagnostic features for specific pathologies. Gan has developed neuro-fuzzy systems for process modelling, system analysis, data fusion, state estimation and control, including linearization and state estimation for unknown discrete-time non-linear dynamic systems [1,2]. Gan's methods for statistically characterising model error make the linearisation models particularly suitable for intelligent state estimation and control . He also proves a theorem on functional equivalence for two key multi-sensor data fusion methods, and developed novel NN architectures and learning algorithms for signal and image processing and for pattern recognition . Lucas' Algoval system  performs automatic empirical evaluation of algorithms on data sets. This www system allows performance comparisons to be made between algorithms on data sets against a range of performance criteria. As competitions co-chair for the Congress on Evolutionary Computation, he uses Algoval to run competitions on draughts, pattern recognition and data mining.
This group focuses on enhancing the retrieval of data and information, through optimisation and intelligent, language-based interfaces. There is a strong emphasis on natural language as part of textual or semi-structured data, and on the novel but principled combination of established NLE and AI techniques to meet information needs. De Roeck’s work on computational semantics and pragmatics develops formal, inferential models of context-dependent phenomena such as presupposition , modals (Pechorro PhD 2000) and imperatives (PhD Perez Ramirez). Poesio uses formal tools whilst emphasising the crucial importance of empirical evidence on production and processes, derived from corpora and psychological experiments . His formal model of common ground, implemented as part of the EU Trindi project, integrates ideas from discourse representation theory and work on dialogue acts, intentions, and obligations, motivated by issues in agent interaction and dialogue management . His work on robust semantic interpretation has been used to improve speech recognition and led to the development of a leading algorithm for definite description interpretation. De Roeck’s expertise in natural language interfaces was used in the SNAP project  to interleave deep and shallow language processing techniques, so that both structured meta-information, and documents’ texts could be accessed and combined in a single natural language query. In the interface for the Yellow Pages Assistant (YPA) the group developed a strategy for robust query elicitation through dialogue where users are treated as an additional information source [Steel 1, DeRoeck 3]. The problem of configuring robust, practical interfaces aimed at broad user populations has been addressed by Musgrave [1,2,3] in a series of successful European initiatives to create open standards infrastructures for dissemination of social science data (NESSTAR 1996-7 and 1998-9). Musgrave has  also co-ordinated projects focusing on engineering interoperable query retrieval and analysis facilities for statistical information and meta-data, and on multi-lingual user interfaces for social science meta-data. De Roeck has conducted work on dynamic strategies for natural language generation (PhD Papagianopoulou). Poesio’s psychologically plausible models of anaphoric processing and NP realisation have been applied in various text generation systems, including GNOME (EPSRC Edinburgh), ILEX (Edinburgh) and ICONOCLAST (Brighton). The YPA project uses shallow and knowledge rich NLE techniques in an intelligent assistant for accessing semi-structured data. Kruschwitz extends YPA data extraction techniques [1,2,3] for other types of semi-structured data on the Web, demonstrating how intelligent search engines can be constructed from relatively simple building blocks . De Roeck  extends standard information retrieval stemming techniques with morphological knowledge, improving performance on morphologically complex languages. Lowden and Robinson have developed methods for the semantic optimisation of database queries. Lowden has developed an inductive approach to formal rule set generation, analysis, and selection [1,2,4] as well as non-exponential transformation techniques for producing near optimum queries . His results show that semantic optimisation for large scale retrieval is viable (Sayli PhD 1999). Robinson has addressed issues of rule analysis [3,4] and distribution of optimisation processes across networked environments [1,2]. Their experiments, using the Data Archive’s large data sets, have demonstrated significant performance improvements.
Robotics & Intelligent Machines
The research interests of this group cover both applications of formal methods and their underlying mathematical foundations. These themes have been the focus for two major EPSRC awards: Constructive Z and Test and Verification for Real-Time Systems. The group has obtained international recognition for research on the logical foundations of typed set theory and typed specification languages and types in formal semantics. Turner has proved the equivalence of typed and untyped set theoretic specification languages , developed a constructive version of a set theoretic specification language  and established the equivalence of constructive type theories with and without separation types . In the course of developing, with Reeves (Uni. Waikato, NZ), the first comprehensive logic for Z [2,3], Henson has shown that the previous (incomplete) work contained in the CD1.2 version of the Z standard was already inconsistent . Further work led to a simpler logic for Z and a detailed comparison with CD1.2 and its later (consistent) revisions . The group also contributed new logics for specification and program development. The Henson-Reeves Z logic formed the basis for a framework for specification and program development, first utilising a constructive Z logic, and then using classical logic without loss of expressivity. Higgins’ [1,2] work addressed fundamental aspects of algebraic automata and formal language theory, especially the relationship between automata and algebraic structures such as semigroups and monoids. This has led to new proofs of Simon’s Theorem  characterising piecewise testable languages and Schützenberger’s Theorem  that does likewise for star-free languages. Cardell-Oliver [1,2] and Völker  have developed several new formal methods for the analysis of real-time and reactive systems. A significant result is Cardell-Oliver's solution to the conformance test problem for real-time systems. Völker  has designed a highly dependable computer architecture for safety critical applications with Krämer (FernUniversität, Hagen) and applied has LOTOS to the formal specification of CORBA applications . His PhD thesis on the modular verification of a function block based industrial control system was awarded the University prize. Cardell-Oliver  and students have investigated the behaviour of real-time traffic over IP networks (Gerdsmeier MSc 1999, Sun PhD ORS award). The group’s interest in proof assistants covers both theorem proving systems and model checking. Völker  has extended the HOL system with disjoint sums over type classes providing a sound basis for modelling schema types of Z, work continued by Wilkins (RA). Cardell-Oliver , Peleska and Buth (Uni. Bremen, Germany) have developed mixed theorem proving and model-checking support for developing reactive systems using CSP. Cardell-Oliver and Glover (RA) have developed a Java tool for generating test cases for real-time systems. Henson and Jarvis (RA) have developed an implementation, using JAPE, of both the Henson-Reeves Z logic and the programming development logic based upon it.
Copyright 2002 - HEFCE, SHEFC, ELWa, DEL
Last updated 17 October 2003