Robot Motion Planning: A Game-Theoretic Foundation

Analysis techniques and algorithms for basic path planning have become quite valuable in a variety of applications such as robotics, virtual prototyping, computer graphics, and computational biology. Yet, basic path planning represents a very restricted version of general motion planning problems often encountered in robotics. Many problems can involve complications such as sensing and model uncertainties, nonholonomy, dynamics, multiple robots and goals, optimality criteria, unpredictability, and nonstationarity, in addition to standard geometric workspace constraints. This paper proposes a unified, game-theoretic mathematical foundation upon which analysis and algorithms can be developed for this broader class of problems, and is inspired by the similar benefits that were obtained by using unified configuration-space concepts for basic path planning. By taking this approach, a general algorithm has been obtained for computing approximate optimal solutions to a broad class of motion planning problems, including those involving uncertainty in sensing and control, environment uncertainties, and the coordination of multiple robots. Received November 11, 1996; revised March 13, 1998.     

Legal reasoning with subjective logic

Judges and jurors must make decisions in an environment of ignoranceand uncertainty for example by hearing statements of possibly unreliable ordishonest witnesses, assessing possibly doubtful or irrelevantevidence, and enduring attempts by the opponents to manipulate thejudge's and the jurors' perceptions and feelings. Three importantaspects of decision making in this environment are the quantificationof sufficient proof, the weighing of pieces of evidence, and therelevancy of evidence. This paper proposes a mathematical frameworkfor dealing with the two first aspects, namely the quantification ofproof and weighing of evidence. Our approach is based on subjectivelogic, which is an extension of standard logic and probability theory,in which the notion of probability is extended by including degrees ofuncertainty. Subjective Logic is a framework for modelling humanreasoning and we show how it can be applied to legalreasoning.     

Representing short-term observations of moving objects by a simple visual language

In a variety of dynamical systems, formations of motion patterns occur. Observing colonies of animals, for instance, for the scientist it is not only of interest which kinds of formations these animals show, but also how they altogether move around. In order to analyse motion patterns for the purpose of making predictions, to describe the behaviour of systems, or to index databases of moving objects, methods are required for dealing with them. This becomes increasingly important since a number of technologies have been devised which allow objects precisely to get traced. However, the indeterminacy of spatial information in real world environments also requires techniques to approximate reasoning, for example, in order to compensate for small and unimportant distinctions which are due to noisy measurements. As a consequence, precise as well as coarse motion patterns have to be dealt with.A set of 16 atomic motion patterns is proposed. On the one hand, a relation algebra is defined on them. On the other hand, these 16 relations form the basis of a visual language using which motion patterns can easily be dealt with in a diagrammatic way. The relations are coarse but crisp and they allow imprecise knowledge about motion patterns to be dealt with, while their diagrammatic realisation also allow precise patterns to get handled. While almost all approaches consider motion patterns along arbitrary time intervals, this paper in particular focuses on short-term motion patterns as we permanently observe them in our everyday life.The bottom line of the current work, however, is yet more general. While it has been widely argued that it makes sense to use both sentential and diagrammatic representations in order to represent different things in the same system adequately (and hence differently), we argue that it makes even sense to represent the same things differently in order to grasp different aspects of one and the same object of interest from different viewpoints. We demonstrate this by providing both a sentential and a diagrammatic representation for the purpose of grasping different aspects of motion patterns. It shows that both representations complement each other.     

Coping with large design spaces: design problem solving in fluidic engineering

This paper is about tool support for knowledge-intensive engineering tasks. In particular, it introduces software technology to assist the design of complex technical systems. There is a long tradition in automated design problem solving in the field of artificial intelligence, where, especially in the early stages, the search paradigm dictated many approaches. Later, in the so-called modern period, a better problem understanding led to the development of more adequate problem solving techniques. However, search still constitutes an indispensable part in computer-based design problem solving—albeit many human problem solvers get by without (almost). We tried to learn lessons from this observation, and one is presented in this paper. We introduce design problem solving by functional abstraction which follows the motto: construct a poor solution with little search, which then must be repaired. For the domain of fluidic engineering we have operationalized the paradigm by the combination of several high-level techniques. The red thread of this paper is design automation, but the presented technology does also contribute in the following respects: (a) productivity enhancement by relieving experts from auxiliary and routine tasks; (b) formulation, exchange, and documentation of knowledge about design; (c) requirements engineering, feasibility analysis, and validation. This research was supported by DFG grants Schw 120/56-3, KL 529/10-3, KL 529/7-3, and KL 529/10-1.     

Bilattices and Reasoning in Artificial Intelligence: Concepts and Foundations

The past few decades have seen a resurgence ofreasoning techniques in artificial intelligenceinvolving both classical and non-classical logics. Inhis paper, ``Multi-valued Logics: A Uniform Approach toReasoning in Artificial Intelligence', Ginsberg hasshown that through the use of bilattices,several reasoning techniques can be unified under asingle framework. A bilattice is a structure that canbe viewed as a class of truth values that canaccommodate incomplete and inconsistent informationand in certain cases default information. Inbilattice theory, knowledge is ordered along twodimensions: truth/falsity and certainty/uncertainty. By defining the corresponding bilattices as truthspaces, Ginsberg has shown that the same theoremprover can be used to simulate reasoning in firstorder logic, default logic, prioritized default logicand assumption truth maintenance system. Although thisis a significant contribution, Ginsberg's paper waslengthy and involved. This paper summarizes some ofthe essential concepts and foundations of bilatticetheory. Furthermore, it discusses the connections ofbilattice theory and several other existingmulti-valued logics such as the various three-valuedlogics and Belnap's four-valued logic. It is notedthat the set of four truth values in Belnap's logicform a lattice structure that is isomorphic to thesimplest bilattice. Subsequently, Fitting proposed aconflation operation that can be used to selectsub-sets of truth values from this and otherbilattices. This method of selecting sub-sets oftruth values provides a means for identifyingsub-logic in a bilattice.     

Architectural Methodology Based on Intentional Configuration of Behaviors

Intelligence has been an object of study for a long time. Different architectures try to capture and reproduce these aspects into artificial systems (or agents), but there is still no agreement on how to integrate them into a general framework. With this objective in mind, we propose an architectural methodology based on the idea of intentional configuration of behaviors. Behavior‐producing modules are used as basic control components that are selected and modified dynamically according to the intentions of the agent. These intentions are influenced by the situation perceived, knowledge about the world, and internal variables that monitor the state of the agent. The architectural methodology preserves the emergence of functionality associated with the behavior‐based paradigm in the more abstract levels involved in configuring the behaviors. Validation of this architecture is done using a simulated world for mobile robots, in which the agent must deal with various goals such as managing its energy and its well‐being, finding targets, and acquiring knowledge about its environment. Fuzzy logic, a topologic map learning algorithm, and activation variables with a propagation mechanism are used to implement the architecture for this agent.     

Maintaining Case-Based Reasoners: Dimensions and Directions

Experience with the growing number of large-scale and long-term case-based reasoning (CBR) applications has led to increasing recognition of the importance of maintaining existing CBR systems. Recent research has focused on case-base maintenance (CBM), addressing such issues as maintaining consistency, preserving competence, and controlling case-base growth. A set of dimensions for case-base maintenance, proposed by Leake and Wilson, provides a framework for understanding and expanding CBM research. However, it also has been recognized that other knowledge containers can be equally important maintenance targets. Multiple researchers have addressed pieces of this more general maintenance problem, considering such issues as how to refine similarity criteria and adaptation knowledge. As with case-base maintenance, a framework of dimensions for characterizing more general maintenance activity, within and across knowledge containers, is desirable to unify and understand the state of the art, as well as to suggest new avenues of exploration by identifying points along the dimensions that have not yet been studied. This article presents such a framework by (1) refining and updating the earlier framework of dimensions for case-base maintenance, (2) applying the refined dimensions to the entire range of knowledge containers, and (3) extending the theory to include coordinated cross-container maintenance. The result is a framework for understanding the general problem of case-based reasoner maintenance (CBRM). Taking the new framework as a starting point, the article explores key issues for future CBRM research.     

一种基于主特征的几何空间模糊推理方法

在几何空间中关于几何体之间不确定关系的推理是空间推理技术的主要研究方向,首先,提出了空间几何体的特征与主特征的概念,并证明了几何体特征之间的关系与几何体之间的基本关系的等价性;其次,引入了相邻、平行、从属、同线、线性等空间关系来描述空间几何体主特征之间的关系,并且将这几种空间关系通过隶属度函数模糊化;最后,基于主特征之间的空间关系,提出了一种进行空间模糊推理的方法,并给出了相应的应用实例,表明了所提出的方法是有效的、可行的。     

Discovering the events expert practitioners extract from dynamic data streams: the modified unit marking technique

One of the cornerstones of expert performance in complex domains is the ability to perceive problem situations in terms of their task-relevant semantic properties. One such class of properties consists of phenomena that are defined in terms of patterns of change over time, i.e., events. A basic pre-requisite for working towards tools to support event recognition is a method for understanding the events that expert practitioners find meaningful in a given field of practice. In this article we present the modified unit marking procedure (mUMP), a technique adapted from work on social perception to facilitate identification of the meaningful phenomena which observers attend to in a dynamic data array. The mUMP and associated data analysis techniques are presented with examples from a first of a kind study where they were used to elicit and understand the events practitioners found meaningful in a scenario from an actual complex work domain.

Handling distributed authorization with delegation through answer set programming

Distributed authorization is an essential issue in computer security. Recent research shows that trust management is a promising approach for the authorization in distributed environments. There are two key issues for a trust management system: how to design an expressive high-level policy language and how to solve the compliance-checking problem (Blaze et al. in Proceedings of the Symposium on Security and Privacy, pp. 164–173, 1996; Proceedings of 2nd International Conference on Financial Cryptography (FC’98). LNCS, vol.1465, pp. 254–274, 1998), where ordinary logic programming has been used to formalize various distributed authorization policies (Li et al. in Proceedings of the 2002 IEEE Symposium on Security and Privacy, pp. 114–130, 2002; ACM Trans. Inf. Syst. Secur. (TISSEC) 6(1):128–171, 2003). In this paper, we employ Answer Set Programming to deal with many complex issues associated with the distributed authorization along the trust management approach. In particular, we propose a formal authorization language providing its semantics through Answer Set Programming. Using language , we cannot only express nonmonotonic delegation policies which have not been considered in previous approaches, but also represent the delegation with depth, separation of duty, and positive and negative authorizations. We also investigate basic computational properties related to our approach. Through two case studies. we further illustrate the application of our approach in distributed environments.