RAE2001 logo

Submissions

 
 

RA5a: Structure,environment and staffing policy

Overview: 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.
Staffing: Since 1996 the Department has embarked on a successful programme of expansion. Eleven new academic staff have been appointed since 1998, 4 to senior positions. New staff have expertise which complements and develops existing strengths and are distributed as follows. Robotics and Intelligent Machines: 1 SL (1998) and 2 L (2000). Machine Learning and Pattern Recognition: 2 SL (2000) and 1 L (2000). Natural Language Engineering and Distributed Information Systems: 1 SL (2000) and 1 L (1998). All other groups appointed a lecturer each, Theoretical Computer Science and Formal Methods, and Agent-Based and Multi-Agent Systems in 1998, and Constraint Programming and Optimisation in 2000. Essex promotion criteria emphasise research output and since 1996, 3 lecturers have been promoted to senior lecturer, and one reader to a Chair.
Research Group Structure: We work in 6 research groups, each mixing new and established staff and researching a focused area. Our groups are flexible structures with overlapping interests and inter-group collaborations. The current teams evolved from the 4, broader groupings returned in 1996, reflecting international developments in the discipline, as well as staff changes and funding initiatives. The summary shows each group’s academic staff (FTE), RA posts, the number of research degrees awarded, current research students in December 2000 including those awaiting examination, and grants active between 1996 and 2000. For full details see http://cswww.essex.ac.uk/Research/.
· 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).
Key Research Achievements 1996-2000
References [1] to [4] 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 [1]. His work has focused on applications in archaeology, anthropology and environmental management [2] and on the clarification and resolution of key methodological problems [3]. Doran attracted international attention when he introduced the key concept of collective misbelief in multi-agent societies [4]. 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 [2] and as syntactic theories, and in the context of self-reference. Several new types of agents have been uncovered [3]. Notably, Fasli has shown that common knowledge plays a role, as important as self-reference, in her work on the Surprise Examination Paradox [1]. Steel has studied mentalistic predicates in connection with AI planning agents, provided agents with both operational and denotational semantics, and compared their suitability [4]. With Burgess (PhD 1998) he has explored how best to express quantification in partial-order causal link planning [2,3].

Constraint Programming & Optimisation
Tsang has made major contributions to constraint satisfication [Tsang 3,4, Ford 4]. He has developed a series of meta-heuristic search algorithms including GENET (a connectionist approach to constraint satisfaction), GLS (Guided Local Search, a meta-heuristic algorithm for constrained optimisation) [1,2], and GGA (Guided Genetic Algorithm, a genetic algorithm with GLS embedded). GENET and GLS have been adopted in research programmes worldwide and GLS has been used in the ILOG Dispatcher (commercial software for vehicle routing). In optimisation research, Ford’s invited ISCS'99 keynote address surveyed multi-step quasi-Newton methods. He has developed minimum curvature methods [3], alternating methods [2] and implicit methods. One of the implicit methods exhibits the best numerical performance of all multi-step methods studied so far, with typical gains of 35% to 40% over the "industry standard" (single-step) method. Salhi’s work on deterministic and stochastic global optimisation [1,2,4] has been applied to decision analysis, data mining, forecasting and optimal process design in chemical engineering (EPSRC 2000-3 with UCL & BP Amoco). Recently Salhi [3] designed and implemented the DOSAGE package which runs optimisation algorithms on heterogeneous distributed platforms. Zhang developed a systematic approach to implement genetic algorithms using orthogonal design and proposed a new population algorithm based on independent component analysis [1,4]. He proposed a unified model for principle and minor component analysis learning [2] and generalized the Oja algorithm to the complex case [3]. In the theory of genetic algorithms, Zhang has recently proved the global convergence of the population algorithm using estimation of distribution in some scenarios. Supported by the University’s Institute for Studies in Finance, Tsang, Salhi, Zhang and Markose (Economics Dept.) address the multi-disciplinary theme of computational finance. Genetic programming has been used for forecasting (Li PhD), modelling arbitrage (Er PhD) and volatility in the options market, thus challenging the efficient market hypothesis.

Machine Learning & Pattern Recognition
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 [1] 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 [1], 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 [1], robust word recognition in noisy text images [2] and handwriting [3]. 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 [4]. 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 [3]. Lucas' Algoval system [4] 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.
Natural Language Engineering & Distributed Information Systems
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 [1], 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 [1]. 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 [2]. 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 [4] 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 [4] 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 [4]. De Roeck [2] 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 [3]. 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 group pursues basic and applied research in the areas of Mobile Robotics, Soft Computing, Computer Vision and Distributed Robotic Systems. Hu played an important role in developing co-operative robots for industry [1,2,3], the domestic and service sector, and education. He leads a team of 16 research students addressing key issues in multi-robot co-operation and co-operative robotics. The team analyse co-operative behaviours; team formation; sensor integration [Hu 4]; and communication, learning and co-evolution. Robot football is a test bed for the investigation. The group has been selected by Sony as 1 of 12 teams world-wide (the only UK group) to collaborate in the development of new generation of quadruped robots. The Essex team was ranked 3rd in the RoboCup 1999 Simulation League and 3rd in the European RoboCup 2000 competition. Hu’s work on agent-based scheduling for multiple autonomous vehicles in dockyard operations involves the design of a multi-agent system for a team of autonomous vehicles to load and unload containers in dockyard. The group's expertise in soft computing has been applied to autonomous navigation and guidance of mobile robots. Standeven [2,3,4], Colley [2,3] and Callaghan have developed a simulator for underwater robots and investigated the use of HLA simulation technology. Hagras [1,2], Callaghan [3], Colley [1,4] and Standeven [1] have investigated the application of hierarchical fuzzy logic control to autonomous vehicles. They develop a new algorithm using a modified version of the Fuzzy Classifier System, where the fuzzy rule set can be modified online using a Genetic Algorithm. A provisional patent for the Genetic-Fuzzy Real-Time Controller has been obtained. The algorithm uses a long-term memory and sensor data allowing the GA to start at the most appropriate point in the current search space. Gu and Hu have developed a novel navigation system for autonomous mobile robots in manufacturing. Their system includes robot localisation by an extended Kalman filter (EKF) fusing multiple sensory information, a polynomial path planner, and a motion controller by PID or Generalised Predictive Control (GPC) [Gu 2,3,4]. In [Gu 1], a neural network is employed to model the dynamics of mobile robots for GPC and wavelet analysis is used to optimise the algorithm. Hu and his students have adopted an evolutionary approach to the problems in the implementation of multi-agent co-operation and learning, which aims to exploit tolerance for imprecision, uncertainty and partial truth to achieve robustness and real-time performance. Spacek has developed algorithms for computer vision in the areas of face recognition [3], motion detection [1,2] and visual robot navigation/guidance [4]. His methods can automatically transform facial images to standard size and orientation. Callaghan's work is concerned with visually guided navigation, motion detection, object recognition and tracking. Hu and his students have developed low-complexity, real-time visual tracking algorithms for recognising multiple moving objects in a dynamic environment.
Theoretical Computer Science & Formal Methods
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 [4], developed a constructive version of a set theoretic specification language [2] and established the equivalence of constructive type theories with and without separation types [3]. 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 [1]. Further work led to a simpler logic for Z and a detailed comparison with CD1.2 and its later (consistent) revisions [4]. 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 [4] characterising piecewise testable languages and Schützenberger’s Theorem [3] that does likewise for star-free languages. Cardell-Oliver [1,2] and Völker [4] 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 [1] 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 [3]. His PhD thesis on the modular verification of a function block based industrial control system was awarded the University prize. Cardell-Oliver [4] 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 [2] 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 [3], 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.

Users of this website should note that the information is not intended to be a complete record of all research centres in the UK

Copyright 2002 - HEFCE, SHEFC, ELWa, DEL

Last updated 17 October 2003

[ Home | About the RAE2001 | Results | Submissions | Overview reports | Panels | Guidance for panel members
| Guidance for institutions | Publications  ]