When building a Bayesian belief network, usually a large number of probabilities have to be assessed by experts in the domain of application. Experience shows that experts are often reluctant to assess all probabilities required, feeling that they are unable to give assessments with a high level of accuracy. We argue that the elicitation of probabilities from experts can be supported to a large extent by iteratively performing sensitivity analyses of the belief network in the making, starting with rough, initial assessments. Since it gives insight into which probabilities require a high level of accuracy and which do not, performing a sensitivity analysis allows for focusing further elicitation efforts. We propose an elicitation procedure in which, alternately, sensitivity analyses are performed and probability assessments refined, until satisfactory behaviour of the belief network is obtained, until the costs of further elicitation outweigh the benefits of higher accuracy or until higher accuracy can no longer be attained due to lack of knowledge.

Argumentation is concerned with reasoning in the presence of imperfect information by constructing and weighing up arguments. It is an approach for inconsistency management in which conflict is explored rather than eradicated. This form of reasoning has proved applicable to many problems in knowledge engineering that involve uncertain, incomplete or inconsistent knowledge. This paper concentrates on different issues that can be tackled by automated argumentation systems and highlights important directions in argument-oriented research in knowledge engineering.

Both the Artificial Intelligence (AI) and the Operations Research (OR) communities are interested in developing techniques for solving hard combinatorial problems, in particular in the domain of planning and scheduling. AI approaches encompass a rich collection of knowledge representation formalisms for dealing with a wide variety of real-world problems. Some examples are constraint programming representations, logical formalisms, declarative and functional programming languages such as Prolog and Lisp, Bayesian models, rule-based formalism, etc. The downside of such rich representations is that in general they lead to intractable problems, and we therefore often cannot use such formalisms for handling realistic size problems. OR, on the other hand, has focused on more tractable representations, such as linear programming formulations. OR-based techniques have demonstrated the ability to identify optimal and locally optimal solutions for well-defined problem spaces. In general, however, OR solutions are restricted to rigid models with limited expressive power. AI techniques, on the other hand, provide richer and more flexible representations of real-world problems, supporting efficient constraint-based reasoning mechanisms as well as mixed initiative frameworks, which allow the human expertise to be in the loop. The challenge lies in providing representations that are expressive enough to describe real-world problems and at the same time guaranteeing good and fast solutions.

Reasoning with inconsistency involves some compromise on classical logic. There is a range of proposals for logics (called paraconsistent logics) for reasoning with inconsistency each with pros and cons. Selecting an appropriate paraconsistent logic for an application depends upon the requirements of the application. Here we review paraconsistent logics for the potentially significant application area of technology for structured text. Structured text is a general concept that is implicit in a variety of approaches to handling information. Syntactically, an item of structured text is a number of grammatically simple phrases together with a semantic label for each phrase. Items of structured text may be nested within larger items of structured text. The semantic labels in a structured text are meant to parameterize a stereotypical situation, and so a particular item of structured text is an instance of that stereotypical situation. Much information is potentially available as structured text, including tagged text in XML, text in relational and object-oriented databases, and the output from information extraction systems in the form of instantiated templates. In this review paper, we formalize the concept of structured text, and then focus on how we can identify inconsistency in items of structured text, and reason with these inconsistencies. Then we review key approaches to paraconsistent reasoning, and discuss the application of them to reasoning with inconsistency in structured text.

This paper surveys the most representative approaches of knowledge-base revision. After a description of the revision characterization according to the AGM paradigm, the paper reviews different revision methods. In each case, the same example is used, as a reference example, to illustrate the different approaches. Closely connected with revision, some other non-monotonic approaches, like update, are briefly presented.

Optimization and constraint satisfaction methods are complementary to a large extent, and there has been much recent interest in combining them. Yet no generally accepted principle or scheme for their merger has evolved. We propose a scheme based on two fundamental dualities: the duality of search and inference, and the duality of strengthening and relaxation. Optimization as well as constraint satisfaction methods can be seen as exploiting these dualities in their respective ways. Our proposal is that rather than employ either type of method exclusively, one can focus on how these dualities can be exploited in a given problem class. The resulting algorithm is likely to contain elements from both optimization and constraint satisfaction, and perhaps new methods that belong to neither.

An appropriately designed architecture of a neural network is essential to many realistic pattern-recognition tasks. A choice of just the right number of neurons, and their interconnections, can cut learning costs by orders of magnitude, and still warrant high classification accuracy. Surprisingly, textbooks often neglect this issue. A specialist seeking systematic information will soon realize that relevant material is scattered over diverse sources, each with a different perspective, terminology and goals. This brief survey attempts to rectify the situation by explaining the involved aspects, and by describing some of the fundamental techniques.

We propose an approach to knowledge-based decision-model construction. The domain knowledge is represented in the form of multilevel influence diagrams. At each level, a regular influence diagram representing a decision model may be generated and the influence diagrams between the levels are related through a series of operations. We defined eight such operations and show that these are sufficient at the structural level to construct any target influence diagram in any practical situation. We provide a series of examples drawn from different domains on the use of multilevel influence diagrams for model construction. We also propose suggestions on providing users with guidance that can direct the model-construction procedure towards the best target model.

The retrieval of relevant cases plays a crucial role in case-based reasoning. There are three major methods for the retrieval of relevant cases: computational approaches (based upon measures of similarity), representational approaches (based upon indexing structures) and hybrid approaches. This paper looks at recent successful implementations of case retrieval with regard to this classification framework. Similarly it emphasises computational and representational models applied to feature-vector case representations.

The recent effort to integrate techniques from the fields of artificial intelligence and operations research has been motivated in part by the fact that scientists in each group are often unacquainted with recent (and not so recent) progress in the other field. Our goal in this paper is to introduce the artificial intelligence community to pseudo-Boolean representation and cutting plane proofs, and to introduce the operations research community to restricted learning methods such as relevance-bounded learning. Complete methods for solving satisfiability problems are necessarily bounded from below by the length of the shortest proof of unsatisfiability; the fact that cutting plane proofs of unsatisfiability can be exponentially shorter than the shortest resolution proof can thus in theory lead to substantial improvements in the performance of complete satisfiability engines. Relevance-bounded learning is a method for bounding the size of a learned constraint set. It is currently the best artificial intelligence strategy for deciding which learned constraints to retain and which to discard. We believe these two elements or some analogous form of them are necessary ingredients to improving the performance of satisfiability algorithms generally. We also present a new cutting plane proof of the pigeonhole principle that is of size n2, and show how to implement some intelligent backtracking techniques using pseudo-Boolean representation.

The current trends of research in information access as emerged from the 1999 Workshop on Logical and Uncertainty Models for Information Systems (LUMIS'99) are briefly reviewed in this paper. We believe that some of these issues will be central to future research on theory and applications of logical and uncertainty models for information access.

Bayesian networks (BNs) model problems that involve uncertainty. A BN is a directed graph, whose nodes are the uncertain variables and whose edges are the causal or influential links between the variables. Associated with each node is a set of conditional probability functions that model the uncertain relationship between the node and its parents. The benefits of using BNs to model uncertain domains are well known, especially since the recent breakthroughs in algorithms and tools to implement them. However, there have been serious problems for practitioners trying to use BNs to solve realistic problems. This is because, although the tools make it possible to execute large-scale BNs efficiently, there have been no guidelines on building BNs. Specifically, practitioners face two significant barriers. The first barrier is that of specifying the graph structure such that it is a sensible model of the types of reasoning being applied. The second barrier is that of eliciting the conditional probability values. In this paper we concentrate on this first problem. Our solution is based on the notion of generally applicable “building blocks”, called idioms, which serve solution patterns. These can then in turn be combined into larger BNs, using simple combination rules and by exploiting recent ideas on modular and object oriented BNs (OOBNs). This approach, which has been implemented in a BN tool, can be applied in many problem domains. We use examples to illustrate how it has been applied to build large-scale BNs for predicting software safety. In the paper we review related research from the knowledge and software engineering literature. This provides some context to the work and supports our argument that BN knowledge engineers require the same types of processes, methods and strategies enjoyed by systems and software engineers if they are to succeed in producing timely, quality and cost-effective BN decision support solutions.

Planning research in Artificial Intelligence (AI) has often focused on problems where there are cascading levels of action choice and complex interactions between actions. In contrast, scheduling research has focused on much larger problems where there is little action choice, but the resulting ordering problem is hard. In this paper, we give an overview of AI planning and scheduling techniques, focusing on their similarities, differences, and limitations. We also argue that many difficult practical problems lie somewhere between planning and scheduling, and that neither area has the right set of tools for solving these vexing problems.

In this study we present a review of the emerging field of meta-knowledge components as practised over the past decade among a variety of practitioners. We use the artificially defined term “meta-knowledge” to encompass all those different but overlapping notions used by the artificial intelligence and software engineering communities to represent reusable modelling frameworks: ontologies, problem-solving methods, patterns and experience factories and bases, to name but a few. We then elaborate on how meta-knowledge is deployed in the context of system's design to improve its reliability by consistency-checking, enhance its reuse potential and manage its knowledge-sharing. We speculate on its usefulness and explore technologies for supporting deployment of meta-knowledge. We argue that, despite the different approaches being followed in systems design by divergent communities, meta-knowledge is present in all cases, in a tacit or explicit form, and its utilisation depends on pragmatic aspects which we try to identify and critically review on criteria of effectiveness.

Continuing the series of workshops begun in 1996 (Luck, 1997; Doran et al., 1997; d'Inverno et al., 1997; Fisher et al., 1997) and held in each of the two years since (Luck et al., 1998; Aylett et al., 1998; Binmore et al., 1998; Decker et al., 1999; Beer et al., 1999), the 1999 workshop of the UK Special Interest Group on Multi-Agent Systems (UKMAS'99) took place in Bristol in December. Chaired and organised by Chris Preist of Hewlett Packard Laboratories, with support from both HP and BT Laboratories, the workshop brought together a diverse range of participants, from the agent community in both the UK and abroad, to discuss and present work spanning all areas of agent research. Although dominated by computer scientists, also present at the meeting were electronic engineers, computational biologists, philosophers, sociologists, statisticians, game-theorists, economists and behavioural scientists, with both academia and industry well represented. Indeed, numbers attending these workshops continue to grow, reflecting the continued and rising interest in agent-based systems. The meeting truly demonstrated the wider view of what the term “agency” implied to research in other disciplines and the questions raised at the end of presentations were a pertinent reminder of the diversity of the audience.

In the last few years, increasing numbers of members of the agent community have been adopting techniques from game theory and decision theory. Broadly speaking, decision theory (Raiffa, 1968) is a means of analysing which of a series of options should be taken when it is uncertain exactly what the result of taking the option will be. Decision theory concentrates on identifying the “best” decision option, where the notion of “best” is allowed to have a number of different meanings, of which the most common is that which maximises the expected utility of the decision maker. Game theory (Binmore, 1992) can be considered as a variant of decision theory in which the outcome of taking a particular decision is dependent upon the actions of another, frequently an opponent which is trying to maximise its own benefit at the cost of the decision maker. Alternatively, game theory can be considered a mechansim for analysing games between two players in which each gets to choose a move from some limited set of options and, depending on what both have chosen, each receives a payout. Since the payout one player receives depends upon the move made by the other then, to maximise its payout, each player needs to take into account the likely move taken by its opponent. From this perspective, decision theory can be considered to be the study of games played against nature, an opponent which does not look to gain the best payout, but rather acts randomly.

To an ever-growing degree, information technology is being based on interactive visual media, and visualisation techniques are emerging as the primary support to decision-making tasks. In this paper I briefly survey the most recent results in the field of advanced visual interfaces, focusing on visualisation techniques along with their design and their applications.

Despite the historical difference in focus between AI planning techniques and Integer Programming (IP) techniques, recent research has shown that IP techniques show significant promise in their ability to solve AI planning problems. This paper provides approaches to encode AI planning problems as IP problems, describes some of the more significant issues that arise in using IP for AI planning, and discusses promising directions for future research.

Knowledge-Based (KB) technology is being applied to complex problem solving and safety and business critical tasks in many application domains. Concerns have naturally arisen as to the dependability of Knowledge-Based Systems (KBS). As with any software, attention to quality and safety must be paid throughout development of a KBS, and rigorous Verification and Validation (V&V) techniques must be employed. Research in V&V of KBSs has emerged as a distinct field only in the last decade, and is intended to address issues associated with quality and safety aspects of KBSs, and to provide such applications with the same degree of dependability as conventional applications. In recent years, V&V of KBSs has been the topic of annual workshops associated with the main AI conferences, such as AAAI, IJCAI and ECAI.

The theory, principles and practice of multi-agent systems is typically characterised as a computational and engineering discipline, since it is through the medium of computational systems that artificial agent systems are most commonly expressed. However, most definitions of agency draw directly on non-computational disciplines for inspiration. During the 1999 UK workshop on multi-agent systems, UKMAS'99, we invited four speakers to address the conceptualisation of multi-agent systems from their perspective as non-computer scientists. This paper presents their arguments and summarises some of the key points of discussion during the panel.