Search

We consider the convergence problem of autonomous mobile robots with inaccurate sensors, which may return the erroneous location of other robots. In this paper, we newly introduce a uniform error model, which is a restricted variant of the original observation-error model proposed by Cohen and Peleg [4]. The degree of an observation error is characterized by distance errors and angle errors. While the original model (non-uniform model) allows that two or more points can have different error degrees, the uniform error model assumes that the same amount of error degree is incurred to all observed points in a single observation. The main focus of our study is to reveal how much such uniformity expands the feasibility of the convergence. In the non-uniform error model, it has been shown that no algorithm can achieve the convergence if the maximum error angle is more than or equal to Π/3. This paper shows that the convergence problem is solvable under the uniform error if the maximum error angle is less than Π/ 2. We also prove that there is no convergence algorithm for the maximum error angle more than or equal to Π/2 even in the uniform error model, which implies the optimality of our algorithm in the sense of angle errors. [ABSTRACT FROM AUTHOR]

Multi-relational data mining (MRDM) is to enumerate frequently appeared patterns in data, the patterns which are appeared not only in a relational table but over a collection of tables. Although a database usually consists of many relational tables, most of data mining approaches treat patterns only on a table. An approach based on ILP (inductive logic programming) is a promising approach and it treats patterns on many tables. Pattern miners based on the ILP approach produce expressive patterns and are wide-applicative but computationally expensive. MAPIX[2] has an advantage that it constructs patterns by combining atomic properties extracted from sampled examples. By restricting patterns into combinations of the atomic properties it gained efficiency compared with other algorithms. In order to scale MAPIX to treat large dataset on standard relational database systems, this paper studies implementation issues. [ABSTRACT FROM AUTHOR]

Multi-relational data mining (MRDM) is to enumerate frequently appeared patterns in data, the patterns which are appeared not only in a relational table but over a collection of tables. Although a database usually consists of many relational tables, most of data mining approaches treat patterns only on a table. An approach based on ILP (inductive logic programming) is a promising approach and it treats patterns on many tables. Pattern miners based on the ILP approach produce expressive patterns and are wide-applicative but computationally expensive because the miners search among large pattern space. We have been proposing a mining algorithm called MAPIX[3]. MAPIX has an advantage that it constructs patterns by combining atomic properties extracted from sampled examples. By restricting patterns into combinations of the atomic properties it gained efficiency compared with conventional algorithms including WARMR[1,2]. In order to scale MAPIX to treat large dataset on standard relational database systems, this paper studies implementation issues. [ABSTRACT FROM AUTHOR]

Systems of autonomous mobile robots have been attracted as distributed systems. Minimal setting for robots to solve some class of problems has been studied with theoretical concerns. This paper contributes discussion on relationship between inaccuracy of compasses which give axes of coordinate systems of robots and the possibility of gathering robots. The gathering problem is to make all robots meet at a single point which is not predefined. The problem has been shown to be solvable for two robots with dynamically variable compasses within the difference of Π/4 between two robots. This paper improves the limit of difference to Π/3. This is shown with the fully asynchronous robot model CORDA. Configurations and executions of robot systems for CORDA with dynamic compasses are formalised. In order to deal with behaviors of robots a concept of relative configurations is also introduced. [ABSTRACT FROM AUTHOR]

This paper extends the bottom-up relational miner Mapix[9] It takes a relational database consists of multiple relational tables including a target relation, and enumerates patterns with which a large part of instances in the target relation match. The patterns are given as logical formulae. Although a well-known system Warmr generates and tests possible patterns, it has limitation in its efficiency. Mapix took a bottom-up approach and gained efficiency at the cost of variety of patterns. It searches and propositionalizes features appeared in instances. Patterns produced is only simple combinations of attributed. The proposed algorithm EquivPix (an equivalent-class-based miner using property items extracted from examples) keeps the merits of bottom-up approach, i.e. time-efficiency and prohibition of duplicated patterns, and it widens pattern variation. EquivPix introduces equivalent classes on properties extracted and also two combination operators of them. [ABSTRACT FROM AUTHOR]

This paper gives a method to treat Web usage mining as requent sequence mining. It provides a unified representation of three different types of source for Web usage mining. The source include an access log recorded in a Web server, the hypertext documents, and the hype-text structure or the graph of linkage. All of these information are represented as sequences. An efficient sequence mining PrefixSpan is inspected to mine with the unified information and an extension of PrefixSpan is proposed for our purpose. A preliminary experiment is also explained. [ABSTRACT FROM AUTHOR]

This paper proposes a mining algorithm for relational frequent patterns based on a bottom-up property extraction from examples. The extracted properties, called property items, are used to construct patterns by a level-wise way like Apriori. The property items are assumed to have a special form, which is defined in terms of mode declaration of predicates. The algorithm produces frequent itemsets as patterns without duplication in the sense of logical equivalence. It is implemented as a system called Mapix and is evaluated with four different datasets with comparison to Warmr. Mapix had large advantage in runtime. [ABSTRACT FROM AUTHOR]

Let consider n autonomous mobile robots that can move in a two dimensional plane. The gathering problem is one of the most fundamental tasks of autonomous mobile robots. In short, given a set of robots with arbitrary initial locations, gathering must make all robots meet in finite time at a point that is not predefined. In this paper, we study about the feasibility of gathering by mobile robots that have φ-absolute error dynamic compasses. While the direction of each local coordinate system is fixed in usual systems, the dynamic compass model allows the angle difference between a local coordinate system and the global coordinate system to vary with time in the range of [0, φ]. This paper proposes a semi-synchronous gathering algorithm for n robots with (π/2 − ε)-absolute error dynamic compasses, where ε is an arbitrary small constant larger than zero. To the best of our knowledge, the proposed algorithm is the first one that considers both inaccurate compass models and more than two robots. We also show the optimality of our algorithm. It is proved that for any φ ≥ π/2, there is no algorithm to gather two robots with φ-absolute error dynamic compasses. [ABSTRACT FROM AUTHOR]

Restricting the form of rules is an important issue of relational association rule mining. The proposing method PIX extracts properties from given examples and to use them to form rules. An property of an instance consists of an addressing part which specifies objects related to the instance and description part which says something among the objects. Extracted properties are used like as an item in market basket database and an APRIORI-like algorithm calculates frequent item sets. The paper describes also an experiment in a sample application. Keywords: relational data mining, association rules, saturation, property extraction. [ABSTRACT FROM AUTHOR]

A purpose of text-mining is to summarise a large collection of documents. This paper proposes a new method to view a summary of large document set. It consists of two techniques, one of which constructs classification trees using a split test called the standard-example (standard-document) split test, and the other is a method to display features in each class of documents classified in the trees. The standard-example split test is a test which divides examples by their distance (or similarity) from a standard-example which is selected by a criterion. This is the first method which applies this test to text mining. The display method exhibits representative words of document classes which emphasise their feature. [ABSTRACT FROM AUTHOR]

A gene expression system ra-BDD (n-output Binary Decision Diagram) was proposed in order to investigate co-evolution [5]. Although the system is suitable for behavior models of agents, it does not include crossover. This paper proposes a crossover operation using Bryant's Apply operation [2]. The operation makes an n-BDD probabilistically inherit two functions expressed by two n-BDDs. In an experiment the proposed method had more than 40% high fitness than the conventional method. Moreover, in another environment where carnivores and herbivores are co-evolved, we have seen a food chain relation. [ABSTRACT FROM AUTHOR]

Recently the control of multi-agent behavior using two-player non-zero sum games, such as prisoner's dilemma, has been studied. In this paper we propose a two player game that includes a dilemmatic structure and extend it to the study of two teams consisting of many players. Iterative versions of dilemma games have been investigated extensively and many strategies for the games have been proposed. For multi-agent applications we extend our dilemma game to a multi-player version. Several decision strategies are studied with this model. The multi-player model is used to decide actions of agents in the burden carriage problem, which includes a typical situation of agents in competition. We show that the behavior of agents in the problem matches the results of team contests of the dilemma game. [ABSTRACT FROM AUTHOR]