International Journal on Artificial Intelligence Tools

Recently, efficient algorithms have been proposed to achieve arc- and path-consistencey in constraint networks. For example, for arc-consistency, there are linear time algorithms (in the size of the problem) which are efficient in practice (e.g. AC-6 and AC-7). The best path-consistency algorithm proposed is PC-{5|6} which is a natural generalization of AC-6 to path-consistency. While its theoretical complexity is the best, experimentations show clearly that it is not very efficient in practice. In this paper, we propose two algorithms, one for arc-consistency, AC-8, and the second for path-consistency, PC-8. These algorithms are based on the same principle: to exploit minimal supports as AC-6 and PC-{5|6} do, but without recording them. While for AC-8, this approach is of limited interest, we show that for path-consistency, this new approach allows to outperform significantly existing algorithms.

This paper describes an object-oriented lexical representation language based on Unification Categorial Grammar (UCG) that encodes linguistic and semantic information uniformly as classes and objects and an efficient bottom-up parsing method for UCG using selection sets technique. The lexical representation language, implemented in the logic and object-oriented programming language LIFE, introduces several new information sharing mechanisms to enable natural, declarative, modular and economial construction of large and complex computational lexicons. The selection sets are deduced from a transformation between UCG and Context-Free Grammar (CFG) and used to reduce search space for the table-driven algorithm. The experimental tests on a spoken English corpus show that the hierarchical lexicon achieves a dramatic reduction on redundant information and that selection sets significantly improve parsing UCG with a polynomial time complexity.

In this paper, some fundamental issues of modern multi-agent robot architectures are discussed. It is argued that the multi-agent approach provides the necessary flexibility and adaptivity for such architectures, and that the primary issue in designing a multi-agent robot architecture is the selection of the granularity level, i.e., the decision on decomposing the overall desired functionality physically or across tasks. It is explained why at the various system levels different decomposition grains are needed; physical components, tasks or hybrid. This granularity decision is made on the basis of specific criteria of control localization, knowledge decoupling and interaction minimization so as to identify the decision points of the overall functionality. The above criteria lead to a dual composition-decomposition relation, which provides a good basis for system scaling. The paper specializes the discussion to a proposed neuro-fuzzy multi-agent architecture, which is then applied to design the local path planning system of an indoor mobile robot.

We propose the share-confidence framework for knowledge discovery from databases which addresses the problem of mining characterized association rules from market basket data (i.e., itemsets). Our goal is to not only discover the buying patterns of customers, but also to discover customer profiles by partitioning customers into distinct classes. We present a new algorithm for classifying itemsets based upon characteristic attributes extracted from census or lifestyle data. Our algorithm combines the A priori algorithm for discovering association rules between items in large databases, and the A O G algorithm for attribute-oriented generalization in large databases. We show how characterized itemsets can be generalized according to concept hierarchies associated with the characteristic attributes. Finally, we present experimental results that demonstrate the utility of the share-confidence framework.

To facilitate the success of agent technology, we need suitable tools both to reduce the effort in the development of agent systems and to obtain efficient implementations of them. This paper presents an agent-oriented language for the development of multi-agent systems, called ALL (Agent Level Language), that should offer both the two features. In fact, on the one hand, ALL integrates object-oriented and rule based programming to simplify the definition of agent systems and the management of interactions between agents. On the other hand, ALL can be translated into C++, Common Lisp and Java code and can encapsulate objects written in these three languages allowing the reuse of a large amount of pre-existent software and the realization of efficient applications in a large set of (different) domains. ALL rules derive from YACC rules and can simplify the management of agents interaction because they are suitable for the parsing of messages and because they can be reused thanks to object-oriented inheritance.