Multi-objective reinforcement learning has been studied as an extension of conventional reinforcement learning approaches. In the primary problem settings of multi-objective reinforcement learning, the objectives represent a trade-off between different types of utilities and costs for a single agent. Here we address a case of multiagent settings where each objective corresponds to an agent to improve bottlenecks and fairness among agents. Our major interest is how learning captures the information about the fairness with a criterion. We employ leximin-based social welfare in a single-policy, multi-objective reinforcement learning method for the joint policy of multiple agents and experimentally evaluate the proposed approach with a pursuit-problem domain.

The Distributed Constraint Optimization Problem (DCOP) lies at the foundations of multiagent cooperation. With DCOPs, the optimization in distributed resource allocation problems is formalized using constraint optimization problems. The solvers for the problem are designed based on decentralized cooperative algorithms that are performed by multiple agents. In a conventional DCOP, a single objective is considered. The Multiple Objective Distributed Constraint Optimization Problem (MODCOP) is an extension of the DCOP framework, where agents cooperatively have to optimize simultaneously multiple objective functions. In the conventional MODCOPs, a few objectives are globally defined and agents cooperate to find the Pareto optimal solution. However, such models do not capture the interests of each agent. On the other hand, in several practical problems, the share of each agent is important. Such shares are modeled as preference values of agents. This class of problems can be defined using the MODCOP on the preferences of agents. In particular, we define optimization problems based on leximin ordering and Asymmetric DCOPs (Leximin AMODCOPs). The leximin defines an ordering among vectors of objective values. In addition, Asymmetric DCOPs capture the preferences of agents. Because the optimization based on the leximin ordering improves the equality among the satisfied preferences of the agents, this class of problems is important. We propose several solution methods for Leximin AMODCOPs generalizing traditional operators into the operators on sorted objective vectors and leximin. The solution methods applied to the Leximin AMODCOPs are based on pseudo trees. Also, the investigated search methods employ the concept of boundaries of the sorted vectors.

Distributed Constraint Optimization Problem (DCOP) has been studied as a fundamental component of multiagent systems. With DCOPs, various applications on multiagent systems are formalized as constraint optimization problems where variables and functions are distributed among agents. Leximin AMODCOP has been proposed as a class of Multiple Objective DCOPs, where multiple objectives for individual agents are optimized based on the leximin operator. This problem also relates to Asymmetric DCOPs based on its the criteria of fairness among agents. Previous studies explore only Leximin AMODCOPs on constraint graphs limited to functions with unary or binary scopes. We address the Leximin AMODCOPs on factor graphs that directly represent n-ary functions. A dynamic programming method on factor graphs is investigated as an exact solution method. In addition, for relatively dense problems, we also investigate several approximate/inexact algorithms.

Much of the Distributed Constraint Satisfaction Problem (DisCSP) solving research has addressed cooperating agents, and privacy was frequently mentioned as a significant motivation of the decentralization. While privacy may have a role for cooperating agents, it is easier understood in the context of self-interested utility-based agents, and this is the situation considered here. With utility-based agents, the DisCSP framework can be extended to model privacy and satisfaction under the concept of utility. We introduce Utilitarian Distributed Constraint Satisfaction Problems (UDisCSP), an extension of the DisCSP that exploits the rewards for finding a solution and the costs for losing privacy as guidance for the utility-based agents. A parallel can be drawn between Partially Observable Markov Decision Processes (POMDPs) and the problems solved by individual agents for UDisCSPs. Common DisCSP solvers are extended to take into account the utility function. In these extensions we assume that the planning problem is further restricting the set of communication actions to only the ones available in the corresponding solver protocols. The solvers obtained propose the action to be performed in each situation, defining thereby the policy of the agents.

Distributed Constraint Optimization Problems (DCOPs) have been studied as fundamental problems in multiagent systems. The Max-Sum algorithm has been proposed as a solution method for DCOPs. The algorithm is based on factor graphs that consist of two types of nodes for variables and functions. While the Max-Sum is an exact method for acyclic factor-graphs, in the case that the factor graph contains cycles, it is an inexact method that may not converge. In this study, we propose a method that decomposes the cycles based on crossedged pseudo-trees on factor-graphs. We also present a basic scheme of distributed search algorithms that generalizes complete search algorithms on the constraint graphs and Max-Sum algorithm.

DirectDemocracyP2P is an open source platform developed in JAVA and offering peer-to-peer and mobile ad hoc wireless communication capabilities. The platform offers an API supporting plugins, beside its main application: deliberative petition drives (aka citizens' initiatives with integrated argumentation) [1]. An authentication-by-reputation technique based on digital signatures and peer review [2], [3] is integrated into the platform via this main application. Each peer manages independently its database of items of interest. The items of interest are encapsulated as self-contained pieces of information and uniquely identifiable using a system of global identifiers (GIDs). Each GID consists of a combination of public keys with creation dates, or digest values. Communication is based on a combination of push and pull mechanisms. [1].

Forming effective coalitions is a major research challenge in AI and multi-agent systems (MAS). Coalition Structure generation (CSG) involves partitioning a set of agents into coalitions so that social surplus (the sum of the rewards of all coalitions) is maximized. A partition is called a Coalition Structure (CS). In traditional works, the value of a coalition is given by a black box function called a characteristic function. In this paper, we propose a novel formalization of CSG, i.e., we assume the value of a characteristic function is given by an optimal solution of a distributed constraint optimization problem (DCOP) among the agents of a coalition. A DCOP is a popular approach for modeling cooperative agents, since it is quite general and can formalize various application problems in MAS. At first glance, one might assume that the computational costs required in this approach would be too expensive, since we need to solve an NP-hard problem just to obtain the value of a single coalition. To optimally solve a CSG, we might need to solve n-th power of 2 DCOP problem instances, where n is the number of agents. However, quite surprisingly, we show that an approximation algorithm, whose computational cost is about the same as solving just one DCOP, can find a CS with quality guarantees. More specifically, we develop an algorithm with parameter k that can find a CS whose social surplus is at least max(k/(w*+1), 2k/n) of the optimal CS, where w* is the tree width of a constraint graph. When k=1, the complexity of this algorithm is about the same as solving just one DCOP. These results illustrate that the locality of interactions among agents, which is explicitly modeled in the DCOP formalization, is quite useful in developing an efficient CSG algorithm with quality guarantees.

In a real-time Linux system, the critical sections are known as the main factor delaying the execution of real-time tasks. Traditional approaches to overcoming this issue have given less consideration to both real-time and non-real-time tasks. In this paper, we propose a new lock management mechanism to improve the real-time performance with a small penalty for non-real-time tasks. Using this mechanism, we guarantee the deadlines of real-time tasks while keeping the penalties accruing for non-real-time tasks small. We implemented a prototype system in Linux 2.6.20. Experimental results showed that the worst-case OS latency of real-time task is reduced to 19% of the original one, while the penalty for a non-real-time task is 10.1% of the original. The results also showed that the lock management mechanism proposed in this paper is efficient and useful for a future real-time Linux system.

This paper describes a mobile robot for home service purpose together with ceiling attached ultrasonic locator and microphone array. User call can be detected by those ceiling devices and then mobile robot navigates toward given location. After reaching to the given location, the robot tries to find out user location by using stereo camera, laser and triconcentric microphone array. We implemented those system at our experimental house "Rokko Holone". System components and experimental results are shown

We propose a new execution time prediction method that combines measurement-based execution time analysis and simulation-based memory access analysis. In measurement-based execution time analysis, the target program is divided into basic blocks, to each of which a memory area accessed by the block is allocated, so that all the basic block execution times are measured on a real machine. Since the execution behavior of such a basic block is not a real case, simulation-based memory access analysis is introduced to calculate the memory access cost. The method has been implemented using the intermediate expressions (both TREE and RTL expressions) used in GCC (Gnu compiler collection). This paper demonstrates that the proposed method predicts the execution time safely in different architecture environments, i.e. Pentium-M and XScale

A humanoid robot is a real-time system controlled by a complex computer system that requires huge computing power for perception and planning, high energy efficiency for self-contained control, reduction of physical dimensions, and high reliability. This paper proposes a distributed architecture for the humanoid robot control substituting conventional centralized control architectures. In addition to the parallelism that provides scalable computing power at low clock namely at low energy, the distributed architecture contributes to reliable operations by replacing many fragile analog signal wires with a digital network with redundant routes. In order to accomplish a real-time control over the network, RMTP (responsive multi-threaded processor) for parallel and real-time computation has been newly designed. RMTP can synchronize more than thirty nodes distributed over a robot body in less than 5 micro second with a real time network called the responsive link (RL). Architectures of RMTP, RL and Linux-based real-time system software are presented.

In order to determine both location and orientation of a mobile robot, we use omni-directional view images from a camera mounted on top of the robot. Images are sampled circularly on rings at various radii. Correlation values between rings of different images are regarded as the similarity of the image, therefore the similarity of locations. Using real images taken at different times in navigation experiments, we computed correlation values normalized by brightness, and confirmed the robot can be localized in 50 cm to 100 cm range with 3-10 degree orientation accuracy. The idea of using aggregated sum of circular samples for representing landmarks at multiple levels is also presented.

We have been developing an autonomous robotic agent that helps people in a real world environment, such as in an office. When a robotic agent works by cooperating with a person in a real world environment, it must manage a lot of information and deal with the knowledge and languages that people usually use. Therefore it is important for the agent to recognize what people request as soon as possible. To realize common communication with people, the agent should provide robust communicative functions to obtain information from people. We discuss communicative functions of our robotic agent called Jijo-2. Especially we focus on the problem of detecting human faces, and discuss how a method of detecting a human face can be robustly archived.

This paper proposes a multi-agent software architecture for controlling higher level behaviors of a mobile office-conversant robot. In order to keep the whole system comprehensive and extensible, a group structure is introduced into multi-agent architecture. In the architecture, the whole system is divided into several behavior-manager agents and the behavior-manager manages multiple behavior agents, which are dynamically created and destroyed on demands. Several behaviors and behavior-managers are implemented as classes of an object-oriented Lisp. Dialog-based map learning and teleoperation experiments with real mobile robot Jijo-2 are shown for evaluating the architecture.

This paper reports on our work on the spoken dialogue interface to Jijo-2, an autonomous mobile office robot. We propose an attentional state model for office robot dialogue based on the centering model [2]. We give details of the implementation of Jijo-2's language components and give our algorithm for reducing the ambiguity of dialogues by identifying pronoun referents.

We have been developing prototypes of teleoperation systems via a standard protocol with a standard human interface, where VRML2.0 is employed as the protocol and a Web browser as the human interface. Using a Web browser, an operator can plan motions of objects interactively on a manipulation simulator with a world model which was sent from a remote site via VRML. The employment of a standard protocol and human interface enables our teleoperation system to be used by non-specialists from any Internet site, or by anyone from anywhere, without installing any specific software on the client side a priori.

In order for our office conversant robot to take robust actions according to events rising from different kind of sensors, a layered process network architecture based on an event-driven control model is presented. In this architecture, high level modules are freed from time consuming checking of sensors, and are able to follow multiple scenario-driven consistent behaviors, allowing interruption from human and environment. Programs are written as series of event-action pairs, which are also effective to keep reactiveness and modularity high.

We have been developing a prototype of teleoperation systems via a standard protocol with a standard human interface, where an enhanced VRML is employed as the protocol and a Web browser as the human interface. We clarify what are missing from VRML2.0 to realize teleoperation systems and show how to enhance it. We believe that the employment of a standard communication protocol and a standard human interface can realize teleoperation systems that are able to be used by nonspecialists from any Internet site, or by any people from anywhere.

We propose a functionally distributed responsive (reactive in real-time) microcontroller for distributed real-time processing, which can control personal robots, home automation, office automation, etc. A responsive controller is composed of a mother module and an I/O card customizable for its specific application. A common mother module is composed of a processor, a memory system, an I/O card bus interface for its daughter card, and high-speed real-time links called responsive links. In order to realize hard real-time communication needed for robot control, sensing, etc., a responsive link consists of a pair of full-duplex data lines and two-way event lines. Many kinds of systems can be flexibly composed by connecting any number of the responsive controllers using the responsive links.

A design of mobile robot for robust life-long navigation in office environment is proposed and evaluated. The key idea is combining probabilistic map and dialog with humans for reducing the location uncertainty. Bayesian inference with the map represented by probabilistic automata is used in order to reduce the number of queries and to evaluate the success rate of planned paths. We experimentally implemented the design using a simple Bayesian network with continuous nodes and demonstrated its effectiveness in a real environment.

Motion of objects in contact plays an important role in the mechanical assembly by manipulators. This paper presents a motion planning algorithm for the case that a convex polyhedron translates and rotates in contact with another one. The rotation of the moving one is parameterized by a special unitary 2/spl times/2 matrix to have the algebraic representation of the contact conditions between the polyhedra. We present an algorithm to determine a sequence of the topological contact states whose asymptotic time complexity is optimal. We also present an algorithm to obtain a 'roadmap' by solving the algebraic equations. The principle idea is 'astute geometric formulations make the algebraic problem easier to solve'. The algorithms are implemented and examples are shown.>

Investigates motions of a polyhedron in contact with a fixed polyhedron under the frictionless assumption. The authors propose a complete algorithm for determining possible velocity of the moving polyhedron and force applicable from the moving one to the fixed one automatically from their geometric models. The algorithm consists of two parts. The first part derives the constraints for the velocity of the moving polyhedron from their shape descriptions. The constraints are represented by linear inequalities of the velocity. The algorithm is complete in the sense that it can be applied to any case in which polyhedra with arbitrary shapes are in contact with arbitrary state. It includes the degenerate case in which a vertex contacts another vertex or edge. The second part solves the inequalities and obtains the set of possible velocity vectors of the moving polyhedron. The authors prove that this part is equivalent to the algorithm for enumerating all vertices of a compact polytope in higher dimensional space. The solution is the direct sum of a nonnegative linear combination of the vectors that break the contact state and a linear combination of the vectors that maintain the state. The minimum set of force vectors that are applicable from the moving polyhedron to the fixed one can be obtained from the set of possible velocity vectors of the moving one. The algorithm is fully implemented in an object-oriented lisp with a solid modeler and in C. The possible applications of the algorithm are also presented.

A multi-fingered robot is an artificial organ with many sensors and actuators which require both real-time control and higherlevel motion coordination. A two-layered task architecture for the control of a multi-fingered robot is presented. A control unit, called an agent, is split into two tasks, lower and upper. While a lower task is performing real-time computation, the upper task takes care of communication with other agents. The system is implemented with VxWorks on multi processors and an agent network for the description of a pick-up grasping task is shown.

The problem of partitioning an assembly into two subassemblies that can be separated arises in assembly planning. We consider assemblies of rigid parts whose contacts are equivalent, in terms of motion constraints, to finite sets of point-plane contact constraints. This type of contact includes all stable contacts between polyhedra as well as the large majority of contacts seen in industrial assemblies. For such assemblies, we describe a general algorithm to And a subassembly that is free to rotate and translate a small distance from the rest of the assembly. For assemblies with m contacts described as k point-plane constraints, the algorithm has a worst-case time bound of 0(~k5).

This paper presents a general algorithm for derivation and analysis of motion constraints of objects in contact. The constraints can be derived as linear inequalities for a general case, even when a vertex contacts another vertex or an edge. The solution of the inequalities is a direct sum of a nonnegative linear combination of motions which change the contact state and a linear combination of them which maintain it. From the singular value decomposition of the coefficient matrix of the inequalities it is possible to find the solution in the minimal dimensional space, where the complexity of the algorithm is also minimal. An algorithm is proposed which is not optimal as asymptotic complexity, but is fast in the practical cases and uniform for the dimension of the cone. The algorithm presented can be applied not only to the sensing and control of motion in contact, but also to the planning of it.>