Abstract

We propose a method called path and action planning with orientation (PAPO) that efficiently generates collision-free paths to satisfy environmental constraints, such as restricted path width and node size, for the multi-agent pickup and delivery in non-uniform environment (N-MAPD) problem. The MAPD problem, wherein multiple agents repeatedly pick up and carry materials without collisions, has attracted considerable attention; however, conventional MAPD algorithms assume a specially designed environment and thus use simple, uniform models with few environmental constraints. Such conventional algorithms cannot be applied to realistic applications where agents need to move in more complex and restricted environments. For example, the actions and orientations of agents are strictly restricted by the sizes of agents and carrying materials and the width of the passages at a construction site and a disaster area. In our N-MAPD formulation, which is an extension of the MAPD problem to apply to non-uniform environments with constraints, PAPO considers not only the path to the destination but also the agents’ direction, orientation, and timing of rotation. It is costly to consider all these factors, especially when the number of nodes is large. Our method can efficiently generate acceptable plans by exploring the search space via path planning, action planning, and conflict resolution in a phased manner. We experimentally evaluated the performance of PAPO by comparing it with our previous method, which is the preliminary version of PAPO, the baseline method in a centralized approach, and fundamental meta-heuristic algorithms. Finally, we demonstrate that PAPO can efficiently generate sub-optimal paths for N-MAPD instances.

The multi-agent pickup and delivery (MAPD) problem, in which multiple agents
iteratively carry materials without collisions, has received significant
attention. However, many conventional MAPD algorithms assume a specifically
designed grid-like environment, such as an automated warehouse. Therefore, they
have many pickup and delivery locations where agents can stay for a lengthy
period, as well as plentiful detours to avoid collisions owing to the freedom
of movement in a grid. By contrast, because a maze-like environment such as a
search-and-rescue or construction site has fewer pickup/delivery locations and
their numbers may be unbalanced, many agents concentrate on such locations
resulting in inefficient operations, often becoming stuck or deadlocked. Thus,
to improve the transportation efficiency even in a maze-like restricted
environment, we propose a deadlock avoidance method, called standby-based
deadlock avoidance (SBDA). SBDA uses standby nodes determined in real-time
using the articulation-point-finding algorithm, and the agent is guaranteed to
stay there for a finite amount of time. We demonstrated that our proposed
method outperforms a conventional approach. We also analyzed how the parameters
used for selecting standby nodes affect the performance.

We propose a coordinated control method of agents, which are self-driving ridesharing vehicles, by using multi-agent deep reinforcement learning (MADRL) so that they individually determine where they should wait for passengers to provide better services as well as to increase their profits in rideshare services. With the increasing demand for ridesharing services, many drivers and passengers have started to participate. However, many drivers spend most of their operating time with empty vehicles, which is not only inefficient but also causes problems such as wasted energy, increased traffic congestion in urban areas, and shortages of ridesharing vehicles in less demand areas. To address this issue, distributed service area adaptation method for ride sharing (dSAAMS), in which agents learn where they should wait using MADRL, was already proposed, but we found that it does not work well under certain environments. Therefore, we propose dSAAMS* with modified input and improved reward scheme for agents to generate coordinated behaviors to adapt to various environments. Then, we evaluated the performance and characteristics of the proposed method by using a simulation environment with varying passenger generation patterns and real data in Manhattan. Our results indicate that the dSAAMS* provides better quality service than the conventional methods and performs better in dynamically changing environments.

This paper proposes a method for dynamically forming teams and assigning appropriate tasks to their members to provide services accomplished by groups of agents of different types. Task or resource allocation in multi-agent systems has drawn attention and has been applied in many areas, such as robot rescue, UAV wireless networks, and distributed computer systems. The proposed method allows agents to belong to more than one team simultaneously for efficiency based on the reciprocal trust relationship, which reflects the past performance of cooperative work, and thus allows each agent to have a queue to undertake multiple tasks. In such a setting, in addition to the communication time, the tasks in the queue can even cause processing delays, leading to instability in the observed information from the leader who selects the team members. Our experimental evaluation shows that the proposed method can efficiently enable stable team formation even in this situation. We also analyze the reasons for this efficiency.

Although the multi-agent pickup and delivery (MAPD) problem, wherein multiple agents iteratively carry materials from some storage areas to the respective destinations without colliding, has received considerable attention, conventional MAPD algorithms use simplified, uniform models without considering constraints, by assuming specially designed environments. Thus, such conventional algorithms are not applicable to some realistic applications wherein agents have to move in a more complicated and restricted environment; for example, in a rescue or a construction site, their paths and orientations are strictly restricted owing to the path width, and the sizes of agents and materials they carry. Therefore, we first formulate an N-MAPD problem, which is an extension of the MAPD problem for a non-uniform environment. We then propose an N-MAPD algorithm, the path and action planning with orientation (PAPO), to effectively generate collision-free paths meeting the environmental constraints. The PAPO is an algorithm that considers not only the direction of movement but also the orientation of agents as well as the cost and timing of rotations in our N-MAPD formulation by considering the agent and material sizes, node sizes, and path widths. We experimentally evaluated the performance of the PAPO using our simulated environments and demonstrated that it could efficiently generate not optimal but acceptable paths for non-uniform environments.

<title>Abstract</title>Social networking services (SNSs) are constantly used by a large number of people with various motivations and intentions depending on their social relationships and purposes, and thus, resulting in diverse strategies of posting/consuming content on SNSs. Therefore, it is important to understand the differences of the individual strategies depending on their network locations and surroundings. For this purpose, by using a game-theoretical model of users called <italic>agents</italic> and proposing a co-evolutionary algorithm called <italic>multiple-world genetic algorithm</italic> to evolve diverse strategy for each user, we investigated the differences in individual strategies and compared the results in artificial networks and those of the Facebook ego network. From our experiments, we found that agents did not select the free rider strategy, which means that just reading the articles and comments posted by other users, in the Facebook network, although this strategy is usually cost-effective and usually appeared in the artificial networks. We also found that the agents who mainly comment on posted articles/comments and rarely post their own articles appear in the Facebook network but do not appear in the connecting nearest-neighbor networks, although we think that this kind of user actually exists in real-world SNSs. Our experimental simulation also revealed that the number of friends was a crucial factor to identify users’ strategies on SNSs through the analysis of the impact of the differences in the reward for a comment on various ego networks.

We propose a decentralized system to determine where ride-sharing vehicle agents should wait for passengers using multi-agent deep reinforcement learning. Although numerous drivers have begun participating in ride-sharing services as the demand for these services has increased, much of their time is idle. The result is not only inefficiency but also wasted energy and increased traffic congestion in metropolitan area, while also causing a shortage of ride-sharing vehicles in the surrounding areas. We therefore developed the distributed service area adaptation method for ride sharing (dSAAMS) to decide the areas where each agent should wait for passengers through deep reinforcement learning based on the networks of individual agents and the demand prediction data provided by an external system. We evaluated the performance and characteristics of our proposed method in a simulated environment with varied demand occurrence patterns and by using actual data obtained in the Manhattan area. We compare the performance of our method to that of other conventional methods and the centralized version of the dSAAMS. Our experiments indicate that by using the dSAAMS, agents individually wait and move more effectively around their service territory, provide better quality service, and exhibit better performance in dynamically changing environments than when using the comparison methods.

This study proposes a cooperative method for a multi-agent continuous cooperative patrolling problem by partitioning the environment into a number of subareas so that the workload is balanced among multiple agents by allocating subareas to individual agents. Owing to the advancement in robotics and information technology over the years, robots are being utilized in many applications. As environments are usually vast and complicated, a single robot (agent) cannot supervise the entire work. Thus, cooperative work by multiple agents, even though complicated, is indispensable. This study focuses on cooperation in a bottom-up manner by fairly partitioning the environment into subareas, and employing each agent to work on them as its responsibility. However, as the agents do not monitor the entire environment, the decentralized control may generate unreasonable shapes of subareas; the area are often unnecessarily divided into fragmented enclaves, resulting in inefficiency. Our proposed method reduced the number of small and isolated enclaves by negotiation. Our experimental results indicated that our method eliminated the minute/unnecessary fragmented enclaves and improved performance when compared with the results obtained by conventional methods.

Cooperation and coordination are major issues in studies on multi-agent systems because the entire performance of such systems is greatly affected by these activities. The issues are challenging however, because appropriate coordinated behaviors depend on not only environmental characteristics but also other agents’ strategies. On the other hand, advances in multi-agent deep reinforcement learning (MADRL) have recently attracted attention, because MADRL can considerably improve the entire performance of multi-agent systems in certain domains. The characteristics of learned coordination structures and agent’s resulting behaviors, however, have not been clarified sufficiently. Therefore, we focus here on MADRL in which agents have their own deep Q-networks (DQNs), and we analyze their coordinated behaviors and structures for the pickup and floor laying problem, which is an abstraction of our target application. In particular, we analyze the behaviors around scarce resources and long narrow passages in which conflicts such as collisions are likely to occur. We then indicated that different types of inputs to the networks exhibit similar performance but generate various coordination structures with associated behaviors, such as division of labor and a shared social norm, with no direct communication.

Retweeting is a featured mechanism of some social media platforms such as Twitter, Facebook, and Weibo. Users share articles with friends or followers by reposting a tweet. However, the ways in which retweeting affects the dominant behaviors of users is still unclear. Therefore, we investigate the influence of retweeting on the behaviors of social media users from a networked, game theoretic perspective; in other words, we attempt to clarify the ways in which the presence of a retweeting mechanism in social media promotes or diminishes the willingness of users toward posting articles and commenting. We propose a retweet reward game model that has been derived by adding a retweeting mechanism to a reward game, which is a simple social networking service model. Subsequently, we conduct some simulation-based experiments to understand the effects of retweeting on the behaviors of users. We observe that users are motivated to post new articles if there is a retweeting mechanism. Furthermore, agents in dense networks are motivated to comment on the articles posted by others because articles spread widely among users, and thus, users can be incentivized to post articles.

We compare the coordination structures of agents using different types of inputs for their deep Q-networks (DQNs) by having agents play a distributed task execution game. The efficiency and performance of many multi-agent systems can be significantly affected by the coordination structures formed by agents. One important factor that may affect these structures is the information provided to an agent’s DQN. In this study, we analyze the differences in coordination structures in an environment involving walls to obstruct visibility and movement. Additionally, we introduce a new DQN input, which performs better than past inputs in a dynamic setting. Experimental results show that agents with their absolute locations in their DQN input indicate a granular level of labor division in some settings, and that the consistency of the starting locations of agents significantly affects the coordination structures and performances of agents.

This paper discusses an adaptive distributed allocation method in which agents individually learn strategies for preferences to decide on the rank of tasks which they want to be allocated by a manager. In a distributed edge-computing environment, multiple managers that control the provision of a variety of services requested from different locations have to allocate the corresponding tasks to appropriate agents, which are usually programs developed by different companies. In our proposed method, each agent learns which manager will allocate tasks it performs well and how to declare its preferred tasks. We experimentally evaluated the proposed learning method and showed that agents using the proposed method could effectively execute requested tasks and could adapt to changes in patterns of the requested tasks.

Recently, multi-agent deep reinforcement learning (MADRL) has been studied to learn actions to achieve complicated tasks and generate their coordination structure. The reward assignment in MADRL is a crucial factor to guide and produce both their behaviors for their own tasks and coordinated behaviors by agents’ individual learning. However, it has not been sufficiently clarified the reward assignment in MADRL’s effect on learned coordinated behavior. To address this issue, using the sequential tasks, coordinated delivery and execution problem with expiration time, we analyze the effect of various ratios of the reward given for the task that agent is responsible for to the reward given for the whole task. Then, we propose a two-stage reward assignment with decay to learn the actions for tasks that the agent is responsible for and coordinated actions for facilitating other agents’ tasks. We experimentally showed that the proposed method enabled agents to learn both actions in a balanced manner, so they could realize effective coordination, by reducing the number of tasks that were ignored by other agents. We also analyzed the mechanism behind the emergence of different coordinated behaviors.

This paper proposes a method to improve the policies trained with multi-agent deep learning by adding a policy advisory module (PAM) in the testing phase to relax the exploration hindrance problem. Cooperation and coordination are central issues in the study of multi-agent systems, but agents’ policies learned in slightly different contexts may lead to ineffective behavior that reduces the quality of cooperation. For example, in a disaster rescue scenario, agents with different functions must work cooperatively as well as avoid collision. In the early stages, all agents work effectively, but when only a few tasks remain with the passage of time, agents are likely to focus more on avoiding negative rewards brought about by collision, but this avoidance behavior may hinder cooperative actions. For this problem, we propose a PAM that navigates agents in the testing phase to improve performance. Using an example problem of disaster rescue, we investigated whether the PAM could improve the entire performance by comparing cases with and without it. Our experimental results show that the PAM could break the exploration hindrance problem and improve the entire performance by navigating the trained agents.

This paper proposes a method for adaptively assigning service areas to self-driving taxi agents in ride-share services by using a centralized deep Q-network (DQN) and demand prediction data. A number of (taxi) companies have participated in ride-share services with the increase of passengers due to the mutual benefits for taxi companies and customers. However, an excessive number of participants has often resulted in many empty taxis in a city, leading to traffic jams and energy waste problems. Therefore, an effective strategy to appropriately decide the service areas where agents, which are self-driving programs, have to wait for passengers is crucial for easing such problems and achieving the quality service. Thus, we propose a service area adaptation method for ride share (SAAMS) to allocate service areas to agents for this purpose. We experimentally show that the SAAMS manager can effectively control the agents by allocating their service areas to cover passengers using demand prediction data with some errors. We also evaluated the SAAMS by comparing its performance with those of the conventional methods.

Reward shaping is a crucial method to speed up the process of reinforcement learning (RL). However, designing reward shaping functions usually requires many expert demonstrations and much hand-engineering. Moreover, by using the potential function to shape the training rewards, an RL agent can perform Q-learning well to converge the associated Q-table faster without using the expert data, but in deep reinforcement learning (DRL), which is RL using neural networks, Q-learning is sometimes slow to learn the parameters of networks, especially in a long horizon and sparse reward environment. In this paper, we propose a reward model to shape the training rewards for DRL in real time to learn the agent's motions with a discrete action space. This model and reward shaping method use a combination of agent self-demonstrations and a potential-based reward shaping method to make the neural networks converge faster in every task and can be used in both deep Q-learning and actor-critic methods. We experimentally showed that our proposed method could speed up the DRL in the classic control problems of an agent in various environments.

In this paper, we investigate how a large-scale system of independently learning agents can collectively form acceptable two-dimensional patterns (pattern formation) from any initial configuration. We propose a decentralized multi-agent deep reinforcement learning architecture MAPF-DQN (Multi-Agent Pattern Formation DQN) in which a set of independent and distributed agents capture their local visual field and learn how to act so as to collectively form target shapes. Agents exploit their individual networks with a central replay memory and target networks that are used to store and update the representation of the environment as well as learning the dynamics of the other agents. We then show that agents trained on random patterns using MAPF-DQN can organize themselves into very complex shapes in large-scale environments. Our results suggest that the proposed framework achieves zero-shot generalization on most of the environments independently of the depth of view of agents.

We investigated whether a group of agents could learn the strategic policy with different sizes of input by deep Q-learning in a simulated takeout platform environment. Agents are often required to cooperate and/or coordinate with each other to achieve their goals, but making appropriate sequential decisions for coordinated behaviors based on dynamic and complex states is one of the challenging issues for the study of multi-agent systems. Although it is already investigated that intelligent agents could learn the coordinated strategies using deep Q-learning to efficiently execute simple one-step tasks, they are also expected to generate a certain coordination regime for more complex tasks, such as multi-step coordinated ones, in dynamic environments. To solve this problem, we introduced the deep reinforcement learning framework with two kinds of distributions of the neural networks, centralized and decentralized deep Q-networks (DQNs). We examined and compared the performances using these two DQN network distributions with various sizes of the agents’ views. The experimental results showed that these networks could learn coordinated policies to manage agents by using local view inputs, and thus, could improve their entire performance. However, we also showed that their behaviors of multiple agents seemed quite different depending on the network distributions.

In this work, we focus on an environment where multiple agents with complementary capabilities cooperate to generate non-conflicting joint actions that achieve a specific target. The central problem addressed is how several agents can collectively learn to coordinate their actions such that they complete a given task together without conflicts. However, sequential decision-making under uncertainty is one of the most challenging issues for intelligent cooperative systems. To address this, we propose a multi-agent concurrent framework where agents learn coordinated behaviors in order to divide their areas of responsibility. The proposed framework is an extension of some recent deep reinforcement learning algorithms such as DQN, double DQN, and dueling network architectures. Then, we investigate how the learned behaviors change according to the dynamics of the environment, reward scheme, and network structures. Next, we show how agents behave and choose their actions such that the resulting joint actions are optimal. We finally show that our method can lead to stable solutions in our specific environment.

We proposes the traffic congestion reducer agents and performed simulation to determine how well they mitigate congestion on multiple-lane highways. Traffic congestion has been a major problem in many countries for years, but as yet there is no effective method/control to mitigate the congestion due to the complex behaviors of cars on multiple-lane roads. We previously proposed traffic congestion reducer (TCR) agents, which are intelligent autonomous agents, to pursue the minimum extra functions required to mitigate or avoid congestion on a highway. Then, we found that, when more than two agents are arranged in succession, they can mitigate the initial (so, light) congestion on a single-lane highway. However, we did not analyze their effectiveness on multi-lane highways, which is more difficult because the dynamics of lane changes. Thus, we built an agent-based simulation for a multiple-lane highway to examine the effects of TCR agents and behaviors of nearby car agents. We also modified the definition of the TCR agents for behavior on a multi-lane highway. The simulation results revealed that while TCR agents can mitigate light congestion, its mitigation mechanism is quite different from that on a single-lane highway.

We propose a learning method that decides the period of activity according to environmental characteristics and the behavioral strategies in the multi-agent continuous cooperative patrol problem. With recent advances in computer and sensor technologies, agents, which are intelligent control programs running on computers and robots, obtain high autonomy so that they can operate in various fields without pre-defined knowledge. However, cooperation/coordination between agents is sophisticated and complicated to implement. We focus on the activity cycle length (ACL) which is the time length from when an agent starts a patrol to when the agent returns to a charging base in the context of a cooperative patrol where agents, like robots, have batteries with limited capacity. A long ACL will enable an agent to visit distant locations, but the agent will require a long rest time to recharge. The basic idea of our method is that if agents have long-life batteries, they can appropriately shorten the ACL, and thus can visit important locations with a short interval of time by recharging frequently. However, appropriate ACL must depend on many elements such as environmental size, number of agents, workload in an environment, and other agents’ behavior and ACLs. Therefore, we propose a method in which agents autonomously learn the appropriate ACL on the basis of the number of events detected per cycle. We experimentally indicate that our agents are able to learn appropriate ACL depending on established spatial divisional cooperation. We also report the details of the analysis of the experimental results to understand the behaviors of agents with different ACLs.

This paper investigates how opinions are polarized by simulating opinion formation with Q-learning in multiplex networks. People sometimes change their opinions to accommodate themselves to the surrounding people in communities, but opinions may still be polarized. To investigate the mechanism of opinion polarization, many studies including studies using agent-based simulations were conducted, but most of these simulations were performed by assuming that people belong to a single community. A number of studies assumed multiple communities, but they usually considered only simple opinion formation methods and more studies are needed. In this paper, we propose an opinion formation model on multiplex networks using Q-learning for agents to identify better individual opinions and analyze how opinions are polarized or agreed on various network structures. Our experiments indicate that opinions are more likely to lead to a consensus on multiplex networks than on single-layer networks. They also suggested that opinions are easily polarized when their cluster coefficient were high and the characteristic path length were longer.

How users of social networking services (SNSs) dynamically identify their own reasonable strategies was investigated by applying a co-evolutionary algorithm to an agent-based game theoretic model of SNSs. We often use SNSs such as Twitter, Facebook, and Instagram, but we can also freeride without providing any content because providing information incurs costs to us. Numerous studies on evolutionary network analysis have been conducted to investigate why people continue to post articles. In these studies, genetic algorithms (GAs) have often been used to find reasonable strategies for SNS users. Although the evolved strategies in these studies are usually common among all users, the appropriate strategies for them must be diverse because the strategies are used in various circumstances. In this paper, we present our analysis using a co-evolutionary algorithm, multiple-world GA (MWGA), the various strategies for individual agents involving co-evolution with their neighboring agents. We also present the fitness value we obtained, a value that was higher than those obtained using the conventional GA. Finally, we show that the MWGA enables us to observe dynamic processes of co-evolution, i.e., why agents reach their own strategies in different circumstances. This analysis is helpful to understand various users’ behaviors through mutual interactions with neighboring users.

We propose a method using several variants of deep Q-network for learning strategic formations in large-scale adversarial multi-agent systems. The goal is to learn how to maximize the probability of acting jointly as coordinated as possible. Our method is called the centralized training and decentralized testing (CTDT) framework that is based on the POMDP during training and dec-POMDP during testing. During the training phase, the centralized neural network's inputs are the collections of local observations of agents of the same team. Although agents only know their action, the centralized network decides the joint action and subsequently distributes these actions to the individual agents. During the test, however, each agent uses a copy of the centralized network and independently decides its action based on its policy and local view. We show that deep reinforcement learning techniques using the CTDT framework can converge and generate several strategic group formations in large-scale multi-agent systems. We also compare the results using the CTDT with those derived from a centralized shared DQN and then we investigate the characteristics of the learned behaviors.

Cooperation and coordination are sophisticated behaviors and are still major issues in studies on multi-agent systems because how to cooperate and coordinate depends on not only environmental characteristics but also the behaviors/strategies that closely affect each other. On the other hand, recently using the multi-agent deep reinforcement learning (MADRL) has received much attention because of the possibility of learning and facilitating their coordinated behaviors. However, the characteristics of socially learned coordination structures have been not sufficiently clarified. In this paper, by focusing on the MADRL in which each agent has its own deep Q-networks (DQNs), we show that the different types of input to the network lead to various coordination structures, using the pickup and floor laying problem, which is an abstract form related to our target problem. We also indicate that the generated coordination structures affect the entire performance of multi-agent systems.

This paper proposes a method of autonomous strategy learning for multiple cooperative agents integrated with a series of behavioral strategies aiming at reduction of energy cost on the premise of satisfying quality requirements in continuous patrolling problems. We improved our algorithm of requirement estimation to avoid concentration of agents since they are given the knowledge of the work environment in advance. The experimental results show that our proposal enables the agents to learn to select appropriate behavioral planning strategies according to performance efficiency and energy cost, and to individually estimate whether the given requirement is reached and modify their action plans to save energy. Furthermore, agents with the new requirement estimation method could achieve fair patrolling by introducing local observations.

We propose a novel method for evolutionary network analysis that uses the genetic algorithm (GA), called the multiple world genetic algorithm, to coevolve appropriate in-dividual behaviors of many agents on complex networks without sacrificing diversity. The GA is the powerful way, and thus, used in many domains, such as economics, biology, and social science as well as computer science, to find the interaction strategies on networks of agents. In evolutionary network analysis using GA, parents for reproduction of offspring are often selected among their neighbors under the assumption that neighbors' better strategies are useful. However, if they are on complex networks, agents exist in distinctive and diverse situations. Therefore, agents have their own appropriate interaction strategies that may be affected by a large number of neighboring agents. Here, we propose the evolutionary computation method that uses a GA on fixed networks to coevolve diverse strategies for individual agents. We conducted the experiments using simulated games of social networking services to evaluate the proposed method. The results indicate that it could effectively evolve the diverse strategy for each agent and the resulting fitness values were almost always larger than those derived through evolution using the conventional evolutionary network analysis using the GA.

Whereas research of the multi-agent patrolling problem has been widely conducted from different aspects, the issue of energy minimization has not been sufficiently studied. When considering real-world applications with a trade-off between energy efficiency and level of perfection, it is usually more desirable to minimize the energy cost and carry out the tasks to the required level of quality instead of fulfilling tasks perfectly by ignoring energy efficiency. This paper proposes a series of coordinated behavioral strategies and an autonomous learning method of target decision strategies to reduce of energy consumption on the premise of satisfying quality requirements in continuous patrolling problems by multiple cooperative agents. We extended our previous method of target decision strategy learning by incorporating a number of behavioral strategies, with which agents individually estimate whether the requirement is reached and then modify their action plans to reduce energy consumption. It is experimentally shown that agents with the proposed methods learn to decide the appropriate strategies based on energy cost and performance efficiency and are able to reduce energy consumption while cooperatively meeting the given requirements of quality.

We propose a control method for an elevator group control system to allocate elevator cars for all types of passengers, including general passengers and special passengers who are likely to be unfairly treated (e.g., with strollers, wheelchairs, or bulky luggage), in order to achieve fair waiting times as well as efficient transportation. Elevators are necessary for people to move vertically within high-rise buildings. Since the number of elevator cars is fixed, they have to be carefully controlled for effective dispatch. Furthermore, due to the limited capacities of elevator cars, some special passengers who require more space are often forced to wait much longer than general passengers for cars with sufficient empty space to arrive. These days, as cameras and other sensors that monitor the environment have become more common, and thanks to the recent advances in computer vision technologies, we can estimate the number of waiting passengers and the size of their belongings in elevator halls. By using such information gathered from muliple agents that monitor a specific elevator car or elevator hall, the proposed control enables effective dispatch for shorter and fairer waiting times. Experimental results using the simulated elevator control showed that our method could make waiting times fairer and achieved total efficiency to carry passengers. We discuss the reasons for the improvement as well as the limitation of our method.

We investigate the coordination structures generated by deep Q-network (DQN) with various types of input by using a distributed task execution game. Although cooperation and coordination are mandatory for efficiency in multi-agent systems (MAS), they require sophisticated structures or regimes for effective behaviors. Recently, deep Q-learning has been applied to multi-agent systems to facilitate their coordinated behavior. However, the characteristics of the learned results have not yet been fully clarified. We investigate how information input to DQNs affect the resultant coordination and cooperation structures. We examine the inputs generated from local observations with and without the estimated location in the environment. Experimental results show that they form two types of coordination structures—the division of labor and the targeting of near tasks while avoiding conflicts—and that the latter is more efficient in our game. We clarify the mechanism behind and the characteristics of the generated coordination behaviors.

We propose a novel method for evolutionary network analysis that uses the genetic algorithm (GA), called the multiple world genetic algorithm, to coevolve appropriate individual behaviors of many agents on complex networks without sacrificing diversity. We conducted the experiments using simulated games of social networking services to evaluate the proposed method. The results indicate that it could effectively evolve the diverse strategy for each agent and the resulting fitness values were almost always larger than those derived through evolution using the conventional evolutionary network analysis using the GA.

We investigate the coordination structures generated by deep Q-network (DQN) in a distributed task execution. Cooperation and coordination are the crucial issues in multi-agent systems, and very sophisticated design or learning is required in order to achieve effective structures or regimes of coordination. In this paper, we show the results that agents establish the division of labor in a bottom-up manner by determining their implicit responsible area when input structure for DQN is constituted by their own observation and absolute location.

We propose a learning method that decides the appropriate activity cycle length (ACL) according to environmental characteristics and other agents' behavior in the (multi-agent) continuous cooperative patrol problem. With recent advances in computer and sensor technologies, agents, which are intelligent control programs running on computers and robots, obtain high autonomy so that they can operate in various fields without pre-defined knowledge. However, cooperation/coordination between agents is sophisticated and complicated to implement. We focus on the ACL which is time length from starting patrol to returning to charging base for cooperative patrol when agents like robots have batteries with limited capacity. Long ACL enable agent to visit distant location, but it requires long rest. The basic idea of our method is that if agents have long-life batteries, they can appropriately shorten the ACL by frequently recharging. Appropriate ACL depends on many elements such as environmental size, the number of agents, and workload in an environment. Therefore, we propose a method in which agents autonomously learn the appropriate ACL on the basis of the number of events detected per cycle. We experimentally indicate that our agents are able to learn appropriate ACL depending on established spatial divisional cooperation.

We propose a learning and negotiation method to enhance divisional cooperation and demonstrate its flexibility for adapting to environmental changes in the context of the multi-agent cooperative problem. We now have access to a vast array of information, and everything has become more closely connected. However, this makes tasks/problems in these environments complicated. In particular, we often require fast decision-making and flexible responses to follow environmental changes. For these requirements, multi-agent systems have been attracting interest, but the manner in which multiple agents cooperate is a challenging issue because of the computational cost, environmental complexity, and sophisticated interaction between agents. In this work, we address the continuous cooperative patrol problem, which requires cooperation based on high autonomy, and propose an autonomous learning method with simple negotiation to enhance divisional cooperation for efficient work. We also investigate how this method can have high flexibility to adapt to change. We experimentally show that agents with our method generate several types of role sharing in a bottom-up manner for effective and flexible divisional cooperation. The results also show that agents using our method appropriately change their roles in different environmental change scenarios and enhance the overall efficiency and flexibility.

We examine whether a team of agents can learn geometric and strategic group formations by using deep reinforcement learning in adversarial multi-agent systems.This is a significant point underlying the control and coordination of multiple autonomous and intelligent agents. While there are many possible approaches to solve this problem, we are interested in fully end-to-end learning method where agents do not have any prior knowledge of the environment and its dynamics. We propose a scalable and distributed DQN framework to train adversarial multi-agent systems. We show that a large number of agents can learn to cooperatively move,attack and defend themselves in various geometric formations and battle tactics like encirclement, guerrilla warfare, frontal attack, flanking maneuver, and so on.We finally showed that by using only local views from the environment, agents create an emergent and collective flocking behaviors.<br />

We examine whether a team of agents can learn geometric and strategic group formations by using deep reinforcement learning in adversarial multi-agent systems. This is a significant point underlying the control and coordination of multiple autonomous and intelligent agents. While there are many possible approaches to solve this problem, we are interested in fully end-to-end learning method where agents do not have any prior knowledge of the environment and its dynamics. In this paper, we propose a scalable and distributed double DQN framework to train adversarial multi-agent systems. We show that a large number of agents can learn to cooperatively move, attack and defend themselves in various geometric formations and battle tactics like encirclement, guerrilla warfare, frontal attack, flanking maneuver, and so on. We finally show that agents create an emergent and collective flocking behaviors by using local views from the environment only.

近年の計算技術の発達は様々な情報と機能を組み合わせたサービスの提供を可能にしている．それらサービスの実行にはタスクを適切な計算資源（エージェント）に割当てる必要があるが，大量のタスクが継続的に発生する環境でそれらの要求に合ったエージェントを割当てるのは困難である．本研究ではシステム全体で追及する効用（タスクの価値や処理タスク数，処理時間などのシステムの共通的効用）に加え，個々のエージェントの特徴や能力に基づく個別選好も考慮できるタスク割当問題を提案する．その問題に対し，エージェントが動的に変化する環境において自身に適切なタスクの順位づけを行う希望順位決定戦略を学習しながら効率的にタスク割当を実現する手法とその情報に基づいて効率的に割当てるアルゴリズムを提案する．提案手法より動的に変化する環境においてエージェントが適切な希望順位決定戦略を学習することによって動的に変化する環境に適応し，システ

We propose a method for enabling agents to autonomously divide the given environment into the subareas for the individual responsibilities through negotiations between local agents in the environment where communication range is limited. Recent advance in robot and computer technologies expands the range of robot activities, but if we consider the requirement such as the size of environments and the required workload, and the limitation such as communication range and battery capacity, cooperation among robots becomes inevitable. Along this line, we formulated a continuous cooperative patrol problem by modeling robots as agents, and proposed the method by which agents can identify their responsible subareas of environments so that their workloads are fair and balanced. However, if the communication range is limited, their divided subareas contained so many redundant parts, and thereby, lowering the entire performance. In this paper, we propose a novel method in which agents not only reduce the redundant parts, but also use the redundant activities to help the busier neighboring agents. We experimentally show that our method can reduce the unnecessary redundancy and can improve the higher entire performance than that in the previous method that are assumed that communications are always available.

This paper proposes a method to efficiently form teams for tasks that can be executed by multiple agents with different capabilities in a distributed network environment. Recent growing information and networking technologies have been realizing new types of computerized services that have been achieved by appropriately combining data from networked sensing devices and actuators controlled by intelligent programs in decentralized environments. Because these types of services can be realized by a team of agents acting using their own capabilities, how such teams can be formed effectively and efficiently in a distributed environment in a bottom-up manner is a key issue for autonomic computing. Our proposed method can autonomously recognize the dependable agents based on past successful cooperative behaviors, and they generate a tight alliance structure to execute the given tasks. Such an alliance structure avoids some conflicts by preventing many tasks being allocated to a few capable agents. We experimentally show that the proposed method can stably exhibit good performance and can adapt to environmental changes where task structure varies.

This paper discusses the emergence of cooperative and coordinated behaviors between joint and concurrent learning agents using deep Q-learning. Multi-agent systems (MAS) arise in a variety of domains. The collective effort is one of the main building blocks of many fundamental systems that exist in the world, and thus, sequential decision making under uncertainty for collaborative work is one of the important and challenging issues for intelligent cooperative multiple agents. However, the decisions for cooperation are highly sophisticated and complicated because agents may have a certain shared goal or individual goals to achieve and their behavior is inevitably influenced by each other. Therefore, we attempt to explore whether agents using deep Q-networks (DQN) can learn cooperative behavior. We use doubles pong game as an example and we investigate how they learn to divide their works through iterated game executions. In our approach, agents jointly learn to divide their area of responsibility and each agent uses its own DQN to modify its behavior. We also investigate how learned behavior changes according to environmental characteristics including reward schemes and learning techniques. Our experiments indicate that effective cooperative behaviors with balanced division of workload emerge. These results help us to better understand how agents behave and interact with each other in complex environments and how they coherently choose their individual actions such that the resulting joint actions are optimal.

Multi-agent patrolling problem has received growing attention from many researchers due to its wide range of potential applications. In realistic environment, e.g., security patrolling, each location has different visitation requirement according to the required security level. Therefore, a patrolling system with non-uniform visiting frequency is preferable. The difference in visiting frequency generally causes imbalanced workload amongst agents leading to inefficiency. This paper, thus, aims at partitioning a given area to balance agents’ workload by considering that different visiting frequency and then generating route inside each sub-area. We formulate the problem of frequency-based multi-agent patrolling and propose its semi-optimal solution method, whose overall process consists of two steps – graph partitioning and sub-graph patrolling. Our work improve traditional k-means clustering algorithm by formulating a new objective function and combine it with simulated annealing – a useful tool for operations research. Experimental results illustrated the effectiveness and reasonable computational efficiency of our approach.

We propose a model of a social networking service (SNS) with diminishing marginal utility in the framework of evolutionary computing and present our investigation on the effect of diminishing marginal utility on the dominant structure of strategies in all agents. SNSs such as Twitter and Facebook have been growing rapidly, but why they are prospering is unknown. SNSs have the characteristics of a public goods game because they are maintained by users posting many articles that incur some cost and because users can also be free riders, who just read articles. Thus, a number of studies aimed at understanding the conditions or mechanisms that keep social media thriving theoretically by introducing the meta-rewards game, which is a variation of a public goods game. The meta-rewards games assume constant marginal utility, meaning that the rewards by receiving comments increase linearly according to the number of comments, but describing the psychological rewards of humans is often inappropriate. In this paper, we present our modification of the model using the diminishing marginal utility and our comparison of the experimental results with those of the original meta-rewards game. We dem

Multi-agent patrolling problem has received growing attention from many researchers due to its wide range of potential applications. In realistic environment, e.g., security patrolling, each location has different visitation requirement according to the required security level. Therefore, a patrolling system with non-uniform visiting frequency is preferable. The difference in visiting frequency generally causes imbalanced workload amongst agents leading to inefficiency. This paper, thus, aims at partitioning a given area to balance agents’ workload by considering that different visiting frequency and then generating route inside each sub-area. We formulate the problem of frequency-based multi-agent patrolling and propose its semi-optimal solution method, whose overall process consists of two steps – graph partitioning and sub-graph patrolling. Our work improve traditional k-means clustering algorithm by formulating a new objective function and combine it with simulated annealing – a useful tool for operations research. Experimental results illustrated the effectiveness and reasonable computational efficiency of our approach.

Background<br />
Social networking services (SNSs) are widely used as communicative tools for a variety of purposes. SNSs rely on the users’ individual activities associated with some cost and effort, and thus it is not known why users voluntarily continue to participate in SNSs. Because the structures of SNSs are similar to that of the public goods (PG) game, some studies have focused on why voluntary activities emerge as an optimal strategy by modifying the PG game. However, their models do not include direct reciprocity between users, even though reciprocity is a key mechanism that evolves and sustains cooperation in human society.<br />
Proposed methods<br />
We developed an abstract SNS model called the reciprocity rewards and meta-rewards games that include direct reciprocity by extending the existing models. Then, we investigated how direct reciprocity in an SNS facilitates cooperation that corresponds to participation in SNS by posting articles and comments and how the structure of the networks of users exerts an influence on the strategies of users using the reciprocity rewards game.<br />
Experimental results<br />
We run reciprocity rewards games on various complex networks and an instance network

This paper proposes an interaction strategy called the extended expectation-of-cooperation (EEoC) that is intended to spread cooperative activities in prisoner's dilemma situations over an entire agent network. Recently developed computer and communications applications run on the network and interact with each other as delegates of the owners, so they often encounter social dilemma situations. To improve social efficiency, they are required to cooperate, but one-sided cooperation is meaningless and loses some payoff due to a rip-off by defecting agents. The concept of EEoC is that when agents encounter mutual cooperation, they continue to cooperate a few times with the desire to see the emergence of cooperative behavior in their neighbors. EEoC is easy to implement in computer systems.We experimentally show that EEoC can effectively spread cooperative activities in dilemma situations in complete, Erdös-Rényi, and regular networks. We also clarify the robustness against defecting agents and the limitation of the EEoC strategy.

We describe a method for decentralized task/area partitioning for coordination in cleaning/sweeping domains with learning to identify the easy-to-dirty areas. Ongoing advances in computer science and robotics have led to applications for covering large areas that require coordinated tasks by multiple control programs including robots. Our study aims at coordination and cooperation by multiple agents, and we discuss it using an example of the cleaning tasks to be performed by multiple agents with potentially different performances and capabilities. We then developed a method for partitioning the target area on the basis of their performances in order to improve the overall efficiency through their balanced collective efforts. Agents, i.e., software for controlling devices and robots, autonomously decide in a cooperative manner how the task/area is partitioned by taking into account the characteristics of the environment and the differences in agents’ software capability and hardware performance. During this partitioning process, agents also learn the locations of obstacles and the probabilities of dirt accumulation that express what areas are easy to be dirty. Experimental evaluation showed that even if the agents use different algorithms or have the batteries with different capacities resulting in different performances, and even if the environment is not uniform such as different locations of easy-to-dirty areas and obstacles, the proposed method can adaptively partition the task/area among the agents with the learning of the probabilities of dirt accumulations. Thus, agents with the proposed method can keep the area clean effectively and evenly.

This paper investigates the effect of direct reciprocity on voluntary participation in social networking services (SNS) by modeling them as a type of public goods (PG) game. Because the fundamental structure of SNS is similar to the PG games, some studies have focused on why voluntary activities in SNS emerge by modifying the PG game. However, their models do not include direct reciprocity between users, even though it is known that reciprocity is a key mechanism to maintain and evolve cooperation in human society - one that is actually observed on SNS. To analyze the effect of reciprocity on SNS, we first developed an abstract model of SNS called reciprocal rewards and meta-rewards games that are extensions of the PG game. Then, we conducted experiments to understand how reciprocity facilitates cooperation by examining the proposed games using complete-graphs, WS networks, and a Facebook network. Finally, we analyze the findings derived from our experiments using the reciprocal rewards games and propose the concept of half free-riders to explain what maintains cooperation-dominant situations.

We describe a method for decentralized task/area partitioning for coordination in cleaning/sweeping domains with learning to identify the easy-to-dirty areas. Ongoing advances in computer science and robotics have led to applications for covering large areas that require coordinated tasks by multiple control programs including robots. Our study aims at coordination and cooperation by multiple agents, and we discuss it using an example of the cleaning tasks to be performed by multiple agents with potentially different performances and capabilities. We then developed a method for partitioning the target area on the basis of their performances in order to improve the overall efficiency through their balanced collective efforts. Agents, i.e., software for controlling devices and robots, autonomously decide in a cooperative manner how the task/area is partitioned by taking into account the characteristics of the environment and the differences in agents’ software capability and hardware performance. During this partitioning process, agents also learn the locations of obstacles and the probabilities of dirt accumulation that express what areas are easy to be dirty. Experimental evaluation showed that even if the agents use different algorithms or have the batteries with different capacities resulting in different performances, and even if the environment is not uniform such as different locations of easy-to-dirty areas and obstacles, the proposed method can adaptively partition the task/area among the agents with the learning of the probabilities of dirt accumulations. Thus, agents with the proposed method can keep the area clean effectively and evenly.

This paper proposes a control method for in agents by switching their behavioral strategy between rationality and reciprocity depending on their internal states to achieve efficient team formation. Advances in computer science, telecommunications, and electronic devices have led to proposals of a variety of services on the Internet that are achieved by teams of different agents. To provide these services efficiently, the tasks to achieve them must be allocated to appropriate agents that have the required capabilities, and the agents must not be overloaded. Furthermore, agents have to adapt to dynamic environments, especially to frequent changes in workload. Conventional decentralized allocation methods often lead to conflicts in large and busy environments because high-capability agents are likely to be identified as the best team member by many agents, resulting in the entire system becoming inefficient due to the concentration of task allocation when the workload becomes high. Our proposed agents switch their strategies in accordance with their local evaluation to avoid conflicts occurring in busy environments. They also establish an organization in which a number of groups are autonomously generated in a bottom-up manner on the basis of dependability to avoid conflicts in advance while ignoring tasks allocated by undependable/unreliable agents. We experimentally evaluated our method in static and dynamic environments where the number of tasks varied.

We propose a learning and negotiation method to enhance divisional cooperation and demonstrate its robustness to environmental changes in the context of the multi-agent cooperative problem. With the ongoing advances in information and communication technology, we now have access to a vast array of information, and everything has become more closely connected due to innovations such as the Internet of Things. However, this makes the tasks/problems in these environments complicated. In particular, we often require fast decision making and flexible responses to adapt to changes of environment. For these requirements, multi-agent systems have been attracting interest, but the manner in which multiple agents cooperate with each other is a challenging issue because of the computational cost, environmental complexity, and sophisticated interaction required between agents. In this work, we address a problem called the continuous cooperative patrol problem,which requires high autonomy, and propose an autonomous learning method with simple negotiation to enhance divisional cooperation for efficient work. We also investigate how this system can have high robustness, as this is one of the key elements in an autonomous distributed system. We experimentally show that agents with our method generate role sharing in a bottom-up manner for effective divisional cooperation. The results also show that two roles, specialist and generalist, emerged in a bottom-up manner, and these roles enhanced the overall efficiency and the robustness to environmental change.

Recent advances in computer and network technologies enable the provision of many services combining multiple types of information and different computational capabilities. The tasks for these services are executed by allocating them to appropriate collaborative agents, which are computational entities with specific functionality. However, the number of these tasks is huge, and these tasks appear simultaneously, and appropriate allocation strongly depends on the agent's capability and the resource patterns required to complete tasks. Thus, we first propose a task allocation method in which, although the social utility for the shared and required performance is attempted to be maximized, agents also give weight to individual preferences based on their own specifications and capabilities. We also propose a learning method in which collaborative agents autonomously decide the preference adaptively in the dynamic environment. We experimentally demonstrate that the appropriate strategy to decide the preference depends on the type of task and the features of the task reward. We then show that agents using the proposed learning method adaptively decided their preference and could maintain excellent performance in a changing environment.

We present an interaction strategy with reinforcement learning to promote mutual cooperation among agents in complex networks. Networked computerized systems consisting of many agents that are delegates of social entities, such as companies and organizations, are being implemented due to advances in networking and computer technologies. Because the relationships among agents reflect the interaction structures of the corresponding social entities in the real world, social dilemma situations like the prisoner’s dilemma are often encountered. Thus, agents have to learn appropriate behaviors from the long term viewpoint to be able to function properly in the virtual society. The proposed interaction strategy is called the enhanced expectation-of-cooperation (EEoC) strategy and is an extension of our previously proposed strategy for improving robustness against defecting agents and for preventing exploitation by them. Experiments demonstrated that agents using the EEoC strategy can effectively distinguish cooperative neighboring agents from all-defecting (AllD) agents and thus can spread cooperation among EEoC agents and avoid being exploited by AllD agents. Examination of robustness against probabilistically defecting (ProbD) agents demonstrated that EEoC agents can spread and maintain mutual cooperation if the number of ProbD agents is not large. The EEoC strategy is thus simple and useful in actual computerized systems.

This paper proposes a method to estimate malicious domain names from a large scale DNS query response dataset. The key idea of the work is to leverage the use of DNS graph that is a bipartite graph consisting of domain names and corresponding IP addresses. We apply a concept of Probabilistic Threat Propagation (PTP) on the graph with a set of predefined benign and malicious node to a DNS graph obtained from DNS queries at a backbone link. The performance of our proposed method (EPTP) outperformed that of an original PTP method (9% improved) and that of a traditional method using N-gram (40% improved) in an ROC analysis. We finally estimated 2,170 of new malicious domain names with EPTP.

This paper proposes a method to estimate malicious domain names from a large scale DNS query response dataset. The key idea of the work is to leverage the use of DNS graph that is a bipartite graph consisting of domain names and corresponding IP addresses. We apply a concept of Probabilistic Threat Propagation (PTP) on the graph with a set of predefined benign and malicious node to a DNS graph obtained from DNS queries at a backbone link. The performance of our proposed method (EPTP) outperformed that of an original PTP method (9% improved) and that of a traditional method using N-gram (40% improved) in an ROC analysis. We finally estimated 2,170 of new malicious domain names with EPTP.

We propose an SNS-norms game to model behavioral strategies in social networking services (SNSs) and investigate the conditions required for the evolution of cooperation-dominant situations. SNSs such as Facebook and Google+ are indispensable social media for a variety of social communications ranging from personal chats to business and political campaigns, but we do not yet fully understand why they thrive and whether these currently popular SNSs will remain in the future. A number of studies have attempted to understand the conditions or mechanisms that keep social media thriving by using a meta-rewards game that is the dual form of a public goods game or by analyzing user roles. However, the meta-rewards game does not take into account the unique characteristics of current SNSs. Hence, in this work we propose an SNS-norms game that is an extension of Axelrod's metanorms game, similar to meta-rewards games, but that considers the cost of commenting on an article and who is most likely to respond to it. We then experimentally investigated the conditions for a cooperation-dominant situation, by which we mean many users continuing to post articles on an SNS. Our results indicate that relatively large rewards compared to the cost of posting articles and comments are required to evolve cooperation-dominant situations, but optional responses with lower cost, such as "Like!" buttons, facilitate the evolution. This phenomenon is of interest because it is quite different from those shown in previous studies using meta-rewards games. We also confirmed the same phenomenon in an additional experiment using a network structure extracted from real-world SNS data.

We propose a fair and accurate peer assessment method for group work using a multi-agent trust network. Although group work is an effective educational method, accurately assessing individual students is not easy. Mutual evaluation is often used to assess group work because students can observe the contributions of other students. However, mutual evaluation presents some potential problems to discuss such as irresponsible evaluations and collusion. Our proposed method identifies and excludes such cheating and unfair ratings on the basis of trust networks that are often used to evaluate sellers in e-market places by using customers’ ratings. We assume a group-work course in a semester in which students mutually evaluate other group members a few (three to five) times since too many chances for evaluation burden students. We introduce the iterative method for alternately generating trust networks and calculating cluster-trust values, which represent similarity of evaluations in a cluster network. Using a multi-agent simulation, we experimentally show that our method can find the irresponsible students and collusive groups and considerably improve accuracy of final marks with only a few chances for mutual evaluations. Thus, our method can provide useful information for assessments to instructors and reduce free-riders’ incentives for cheating behaviors.

This paper proposes a behavioral strategy with which agents select rational or reciprocal behavior depending on the past cooperative activities. Rational behavioral strategy lets agents select actions to try to maximize the direct and immediate rewards, while agents with the reciprocal behavioral strategy try to work with cooperative partners for steady task execution. Although rational action is effective in team formation for group work in an unbusy environment, it may cause conflicts in busy and large-scale multi-agent systems due to the task concentration to a few high capable agents, resulting in the degradation of entire performance. This also affects the learning mechanism to identify which tasks and/or agents will provide more rewards, by destabilizing the cooperative relationship between agents. Our proposed method enables agents to change the behavioral strategy on the basis of the past members of successful group work. We experimentally show that it finally stabilizes the cooperative relationship between agents and improve the entire performance in busy environments. We also indicate that a certain ratios of rational and reciprocal agents in good performance.

We describe the reciprocal agents that build virtual associations in accordance with past cooperative work in a bottom-up manner and that allocate tasks or resources preferentially to agents in the same associations in busy large-scale distributed environments. Models of multi-agent systems (MAS) are often used to express tasks that are done by teams of cooperative agents, so how each subtask is allocated to appropriate agents is a central issue. Particularly in busy environments where multiple tasks are requested simultaneously and continuously, simple allocation methods in self-interested agents result in conflicts, meaning that these methods attempt to allocate multiple tasks to one or a few capable agents. Thus, the system’s performance degrades. To avoid such conflicts, we introduce reciprocal agents that cooperate with specific agents that have excellent mutual experience of cooperation. They then autonomously build associations in which they try to form teams for new incoming tasks. We introduce the N-agent team formation (TF) game, an abstract expression of allocating problems in MAS by eliminating unnecessary and complicated task and agent specifications, thereby identifying the fundamental mechanism to facilitate and maintain associations. We experimentally show that reciprocal agents can considerably improve performance by reducing the number of conflicts in N-agent TF games with different N values by establishing association structures. We also investigate how learning parameters to decide reciprocity affect association structures and which structure can achieve efficient allocations.

We formulate an assignment problem-solving framework called single-object resource allocation with preferential order (SORA/PO) to incorporate values of resources and individual preferences into assignment problems. We then devise methods to find semi-optimal solutions for SORA/PO problems. The assignment, or resource allocation, problem is a fundamental problem-solving framework used in a variety of recent network and distributed applications. However, it is a combinatorial problem and has a high computational cost to find the optimal solution. Furthermore, SORA/PO problems require solutions in which participating agents express no or few dissatisfactions on the basis of the relationship between relative values and the agents' preference orders. The algorithms described herein can efficiently find a semi-optimal solution that is satisfactory to almost all agents even though its sum of values is close to that of the optimal solution. We experimentally evaluate our methods and the derived solutions by comparing them with tho optimal solutions calculated by CPLEX. We also compare the running times for the solution obtained by these methods.

This paper proposes a behavioral strategy called expectation of cooperation with which cooperation in the prisoner's dilemma game spreads over agent networks by incorporating Q-learning. Recent advances in computer and communication technologies enable intelligent agents to operate in small and handy computers such as mobile PCs, tablet computers, and smart phones as delegates of their owners. Because the interaction of these agents is associated with social links in the real world, social behavior is to some degree required to avoid conflicts, competition, and unfairness that may lead to further inefficiency in the agent society. The proposed strategy is simple and easy to implement but nevertheless can spread over and maintain cooperation in agent networks under certain conditions. We conducted a number of experiments to clarify these conditions, and the results indicate that cooperation spread and was maintained with the proposed strategy in a variety of networks.

The coalition structure generation problem is now a big issue in the field of multi-agent systems. with many agents working in the same environment, cooperation may become a key point to complete a mission efficiently. This problem can also be found in many areas such as sensor networks, multi-robot systems, and even e-commerce. However, it has been proved to be NP-complete to find an optimal solution. In the paper, a stochastic algorithm called double-layered ant colony optimization is proposed to deal with the task-oriented coalition structure problem. Then, we evaluate the solution quality by comparing it with the optimal solutions derived by CPLEX. The results indicate that even though this method cannot guarantee the optimal solution, it can find a coalition structure that is good enough within a reasonably short time.

We propose a fair and accurate peer assessment method for group work using a multi-agent trust network. Although group work is an effective educational method, accurately assessing individual students is not easy. Mutual evaluation is often used to assess group work because students can observe the contributions of other students. However, mutual evaluation presents some potential problems to discuss such as irresponsible evaluations and collusion. Our proposed method identifies and excludes such cheating and unfair ratings on the basis of trust networks that are often used to evaluate sellers in e-market places by using customers’ ratings. We assume a group-work course in a semester in which students mutually evaluate other group members a few (three to five) times since too many chances for evaluation burden students. We introduce the iterative method for alternately generating trust networks and calculating cluster-trust values, which represent similarity of evaluations in a cluster network. Using a multi-agent simulation, we experimentally show that our method can find the irresponsible students and collusive groups and considerably improve accuracy of final marks with only a few chances for mutual evaluations. Thus, our method can provide useful information for assessments to instructors and reduce free-riders’ incentives for cheating behaviors.

This paper proposes a behavioral strategy with which agents select rational or reciprocal behavior depending on the past cooperative activities. Rational behavioral strategy lets agents select actions to try to maximize the direct and immediate rewards, while agents with the reciprocal behavioral strategy try to work with cooperative partners for steady task execution. Although rational action is effective in team formation for group work in an unbusy environment, it may cause conflicts in busy and large-scale multi-agent systems due to the task concentration to a few high capable agents, resulting in the degradation of entire performance. This also affects the learning mechanism to identify which tasks and/or agents will provide more rewards, by destabilizing the cooperative relationship between agents. Our proposed method enables agents to change the behavioral strategy on the basis of the past members of successful group work. We experimentally show that it finally stabilizes the cooperative relationship between agents and improve the entire performance in busy environments. We also indicate that a certain ratios of rational and reciprocal agents in good performance.

This paper proposes an effective autonomous task allocation method that can achieve efficient cooperative work by divisional cooperation in multi-agent contexts. Computer and network technology has enabled agents/robots to behave autonomously and to be used in a variety of applications such as cleaning and security patrolling. However, to cover large environments, cooperation and collaboration among several agents are mandatory for efficiency and for the required task quality. However, how agents cooperate is a challenging issue because actual environments are usually complicated and because their own (very uncommon) characteristics. Thus, we first define the continuous cooperative patrolling problem, in which agents split up and move around the environments with the required frequencies that are defined for every location. Then, we extend the previous cooperation method to prompt autonomous and effective division of labor by introducing the negotiation for task (re) allocations. We experimentally show that agents with our method enable effective division and fair allocation by identifying their own responsible locations in a bottom-up manner and that they could achieve considerably improved results compared with those of the previous method. We also investigated the structure of the resulting regime for cooperation and analyzed why our method could achieve the effective task allocation.

This paper proposes a task allocation method in which, although social utility is attempted to be maximized, agents also give weight to individual preferences based on their own specifications and capabilities. Due to the recent advances in computer and network technologies, many services can be provided by appropriately combining multiple types of information and different computational capabilities. The tasks that are carried out to perform these services are executed by allocating them to appropriate agents, which are computational entities having specific functionalities. However, these tasks are huge and appear simultaneously, and task allocation is thus a challenging issue since it is a combinatorial problem. The proposed method, which is based on our previous work, allocates resources/tasks to the appropriate agents by taking into account both social utility and individual preferences. We experimentally demonstrate that the appropriate strategy to decide the preference depends on the type of task and the features of the reward function as well as the social utility.

We propose a method of autonomous learning of target decision strategies for coordination in the continuous cleaning domain. With ongoing advances in computer and sensor technologies, we can expect robot applications for covering large areas that often require coordinated/cooperative activities by multiple robots. We focus on the cleaning tasks by multiple robots or by agents which are programs to control the robots in this paper. We assumed situations where agents did not directly exchange deep and complicated internal information and reasoning results such as plans, strategies and long-term targets for their sophisticated coordinated activities, but rather exchanged superficial information such as the locations of other agents (using the equipment deployed) for their shallow coordination and individually learned appropriate strategies by observing how much dirt/dust had been vacuumed up in multi-agent system environments. We will first discuss the preliminary method of improving the coordinated activities by autonomously learning to select cleaning strategies to determine which targets to move to clear them. Although we could have improved the efficiency of cleaning, we observed a phenomenon where performance degraded if agents continued to learn strategies. This is because so many agents overly selected the same strategy (over-selection) by using autonomous learning. In addition, the preliminary method assumed information given about which regions in the environment easily became dirty. Thus, we propose a method that was extended by incorporating the preliminary method with (1) environmental learning to identify which places were likely to be dirty and (2) autonomous relearning through self-monitoring the amount of vacuumed dirt to avoid strategies from being over-selected. We experimentally evaluated the proposed method by comparing its performance with those obtained by the regimes of agents with a single strategy and obtained with the preliminary method. The experimental results revealed that the proposed method enabled agents to select target decision strategies and, if necessary, to abandon the current strategies from their own perspectives, resulting in appropriate combinations of multiple strategies. We also found that environmental learning on dirt accumulation was effectively learned.

We propose an SNS-norms game to model behavioral strategies in social networking services (SNSs) and in- vestigate the conditions required for the evolution of cooperation-dominant situations. SNSs such as Facebook and Google+ are indispensable social media for a variety of social communications ranging from personal chats to busi- ness and political campaigns, but we do not yet fully understand why they thrive and whether these currently popular SNSs will remain in the future. A number of studies have attempted to understand the conditions or mechanisms that keep social media thriving by using a meta-rewards game that is the dual form of a public goods game or by analyzing user roles. However, the meta-rewards game does not take into account the unique characteristics of current SNSs. Hence, in this work we propose an SNS-norms game that is an extension of Axelrod’s metanorms game, similar to meta-rewards games, but that considers the cost of commenting on an article and who is most likely to respond to it. We then experimentally investigated the conditions for a cooperation-dominant situation, by which we mean many users continuing to post articles on an SNS. Our results indicate that relatively large rewards compared to the cost of posting articles and comments are required to evolve cooperation-dominant situations, but optional responses with lower cost, such as “Like!” buttons, facilitate the evolution. This phenomenon is of interest because it is quite different from those shown in previous studies using meta-rewards games. We also confirmed the same phenomenon in an additional experiment using a network structure extracted from real-world SNS data.

We propose a method for fair and accurate assessment of group work based on trust networks generated by mutual evaluations. Group work is often used for educational activities in universities since it is an effective way to acquire useful knowledge in a number of practical subjects. One drawback is the difficulty of deciding on final marks. Some students may work quite hard whereas others may rarely participate in the group work, but it is almost impossible for professors/instructors to identify contributions of individual students in detail. In contrast, students in the same group are obvious choices for appropriate evaluators of other members since they have first-hand knowledge of the collaborative work. However, some students may be irresponsible for their ratings and submit disputable evaluations, resulting in inaccurate marks. We introduce a simple mutual evaluation method and generate trust networks expressing the distances between evaluations in this paper. After that, disputable evaluations are excluded and students are marked again. We also examine a grouping strategy to detect irresponsible students more accurately. We demonstrate the effectiveness and limitations of our method using multi-agent simulation. Results show that our method can help with the marking of individual students in a group work.

With the development of robot technology, we can expect self-propelled robots working in large areas where cooperative and coordinated behaviors by multiple (hardware and software) robots are necessary. However, it is not trivial for agents, which are control programs running on robots, to determine the actions for their cooperative behaviors, because such strategies depend on the characteristics of the environment and the capabilities of individual agents. Therefore, using the example of continuous cleaning tasks by multiple agents, we propose a method of meta-strategy that decide the appropriate planning strategies for cooperation and coordination through with the learning of the performance of individual strategies and the environmental data in a multi-agent systems context, but without complex reasoning for deep coordination due to the limited CPU capability and battery capacity. We experimentally evaluated our method by comparing it with a conventional method that assumes that agents have knowledge on where agents visit frequently (since they are easy to become dirty). We found that agents with the proposed method could operate as effectively as and, in complex areas, outperformed those with the conventional method. Finally, we describe that the reasons for such a counter-intuitive phenomenon is induced from splitting up in working by autonomous agents based on the local observations. We also discuss the limitation of the current method.

This paper proposes solutions to a problem called single-object resource allocation with preferential orders and efficient algorithms for semi-optimal allocations. Formalizations of resource allocation problems are widely used in many applications. Although many studies on allocation methods have focused on maximizing social welfare or total revenues, they have rarely taken into account agents' individual preferential orders that may have interfered with one another. Our proposed framework allocates one unit of resources to individual users but allows them to declare multiple resources with their own preferential orders. It then tries to allocate a resource to each agent by not only maximizing the total values but also considering the agent's preferences, at least, by ensuring that no or few dissatisfactions are reported. This is obviously a combinatorial problem to find optimal solutions. Thus, we propose efficient methods for semi-optimal solutions (allocations) that satisfy as many user preferences as possible. Finally, we analyze the quality of solutions and computation time by comparing them with the solutions obtained by CPLEX. Then, we experimentally demonstrate that the proposed methods are extremely efficient, while the reduced quality of their solutions is quite small.

In this paper, we introduce an extended performance-based partitioning method for the cooperative cleaning domain in the environment with obstacles. Due to ongoing advances in technology, robotic applications have been crucial for large and complicated areas that require cooperation and coordination in task operations by multiple robots. Therefore, our research has focused on methods for cooperation/coordination of multiple agents, which are the control programs of robots, using examples of cleaning tasks by multiple robots. Our proposed method partitions target area in a bottom-up manner, according to the characteristics of environments by identifying where are easy to be dirty, so that agents can clean their responsible areas effectively and evenly. Specifically, it also has included the learning to identify the shapes and the locations of obstacles in the environments via the steps of cleaning tasks because the shapes of obstacles affect the work performance. Our experiments showed that it could partition their responsible areas autonomously and effectively by taking into consideration the environmental characteristics. We also indicated that it could achieve efficient task operations in a more balanced manner by comparing these results with those by the conventional methods which assumed that the area is divided into equal-size subareas and/or the environmental characteristics are given in advance.

We propose reciprocal agents that self-organize associations based on cooperative relationships for efficient task/resource allocation problems in large-scale multi-agent systems (MASs). Computerized services are often provided by teams of networked intelligent agents by executing the corresponding tasks. However, performance in large-scale and busy MASs, may severely degrade due to conflicts because many task requests are excessively sent to a few agents with high capabilities. We introduce a game of N-agent team formation (TF game), which is an abstract form of the distributed allocation problem. We then introduce reciprocal agents that identifies dependable/trustworthy agents in TF games, shares the states between them, and preferentially works with them. Through this behavior with learning, they autonomously organize implicit associations that can considerably reduce conflicts and achieve fair reward distributions. We experimentally found that reciprocal agents could identify mutually dependable agents that formed independent associations, and efficiently team formed games. Finally, we investigated reasons for such efficient behaviors and found how their organizational structures emerged.

We propose a fair peer assessment method for group work using a multi-agent trust network. Although group work is an effective educational method, accurately assessing individual students is not easy. Mutual evaluation is often used for such assessment, but often presents some potential problems such as irresponsible evaluations and collusion. Our method identifies and excludes such cheating and unfair ratings on the basis of trust networks that are often used to evaluate sellers in e-market places by using customers' ratings. We assume a group-work course in a semester in which students mutually evaluate other group members a few (three to five) times. We introduce the iterative method for alternately generating trust networks using cluster-trust values, which represent similarity of evaluations in a cluster network. We experimentally show that our method can find the irresponsible students and collusive groups and considerably improve accuracy of final marks with only a few chances for mutual evaluations, and thereby, can provide useful information for assessments to instructors.

A balanced team formation method is described for tasks with deadlines in multi-agent systems. With the advances that have been made in computer and network technologies, tasks that are achieved by multiple software/hardware entities are often required in many real-world applications. In addition, these tasks are usually required to be done by specified deadlines to avoid a failure of services or to provide quality services in a timely manner. We designed a method for effective team formation for cooperative work of different entities, called agents, to execute tasks having deadlines. The feature of our method is that rational agents autonomously learn which team they should join and which agents they should work with in order to improve the received rewards. Agents using the method also tried to select teams consisting of agents comparable with themselves; this can help them avoid binding to their teams unnecessarily. Another feature is that they estimate the duration of task execution to avoid a failure of tasks due to a violation of time requirements. We experimentally show that these three functions mutually affect each other positively and can achieve quite good performance in real-time environments.

We propose an efficient team formation method for multi-agent systems consisting of self-interested agents in task-oriented domains where agents have no prior knowledge of the resources/abilities of the other agents. Internet services based on services computing and cloud computing, which have been rapidly increasing, are usually achieved by combining a number of service elements that are distributed over the Internet. We modelled the executions of these elements as teams of agents with the resources and abilities required in the corresponding service elements. This team formation method with the appropriate agents for the service elements makes the entire system efficient. Our proposed method is based on our previous parameter learning method that enables agents to identify their roles in forming a team but requires prior knowledge of all others' resources. This restricts the applicability to real systems. The contribution of this paper is twofold. First, we extended our original method by adding a resource estimation method. Second, we further improved the first extension for large scale multi-agent systems by introducing purviews, which are a relatively small set of agents that are potential members of the teams, for practical computational time and required memory size. We experimentally evaluated our first method by comparing it with the previous method and the task allocation using the contract net protocol (CNP). Then, after increasing the number of agents, we evaluated our second extended method and investigated how the number of agents and the size of the purview affected the overall performances. Results showed that the learning speed was faster in the proposed method so it outperformed other methods in a practical sense even though it did not require prior knowledge of resources in other agents in busy, large-scale, multi-agent systems. (C) 2014 Elsevier B.V. All rights reserved.

We investigate the conditions in which cooperation is dominant in social media using the models of evolutionary games of public goods games and try to clarify the mechanisms that social media thrive. Situation that cooperation is dominant corresponds to that in which posting articles and taking reactions by comment etc. result in some benefits than do nothing as free-riders. Thus, we can say that the social media thrive. It is, however, hard to foresee whether the current popular social media continue to thrive or whether new social media become to thrive in the future. A number of studies examined situations that cooperation is dominant by using the public goods game. However, they assume that users are connected with complete graph as the network structures, which are far from the actual network structures. Thus, we conducted the simulation experiments to identify the cooperation-dominant situations in two network models, WS and BA models, which are said to be close to real networks. We show the differences in the mechanisms for keeping social media thriving in these networks. Our results indicated that in the WS-model networks, the results were quite similar with those of comple

We propose a team formation method that integrates the estimating of the resources of neighboring agents in a tree-structured agent network in order to allocate tasks to the agents that have sufficient capabilities for doing tasks. A task for providing the required service in a distributed environment is often achieved by a number of subtasks that are dynamically constructed on demand in a bottom-up manner and then done by the team of appropriate agents. A number of studies were conducted on efficient team formation for quality services. However, most of them assume that resources in other agents are known, and this assumption is not adequate in real world applications. The contribution of this paper is threefold. First, we extend the conventional method by combining the learning of task allocation and the reorganization of agent networks. In particular, we introduce the elimination of links as well as the generation of links in the reorganization. Second, we revise the learning method so as to use only information available locally. Finally, we omitt the assumption that all resource information in other agents is given in advance. Instead, we extend the task allocation method by combining it with the resource estimation of neighboring agents. We experimentally show that this extension can considerably improve the efficiency of team formation compared with the conventional method even though it does not require knowledge of resources in other agents. We also show that it can make the agent network adaptive to environmental changes. © 2014 Information Processing Society of Japan.

We propose an influence-based aggregative learning framework that facilitates the emergence of social norms in complex networks and investigate how a norm converges by learning through iterated local interactions in a coordination game. In society, humans decide to coordinate their behavior not only by exchanging information but also on the basis of norms that are often individually derived from interactions without a centralized authority. Coordination using norms has received much attention in studies of multi-agent systems. In addition, because agents often work as delegates of humans, they should have "mental" models about how to interact with others and incorporate differences of opinion. Because norms make sense only when all or most agents have the same one and they can expect that others will follow, it is important to investigate the mechanism of norm emergence through learning with local and individual interactions in agent society. Our method of norm learning borrows from the opinion aggregation process while taking into account the influence of local opinions in tightly coordinated human communities. We conducted experiments showing how our learning framework facilitates propagation of norms in a number of complex agent networks.

We propose a method for fair and accurate assessment of group work based on trust networks generated by mutual evaluations. Group work is often used for educational activities in universities since it is an effective way to acquire useful knowledge in a number of practical subjects. One drawback is the difficulty of deciding on final marks. Some students may work quite hard whereas others may rarely participate in the group work, but it is almost impossible for professors/instructors to identify contributions of individual students in detail. In contrast, students in the same group are obvious choices for appropriate evaluators of other members since they have first-hand knowledge of the collaborative work. However, some students may be irresponsible for their ratings and submit disputable evaluations, resulting in inaccurate marks. We introduce a simple mutual evaluation method and generate trust networks expressing the distances between evaluations in this paper. After that, disputable evaluations are excluded and students are marked again. We also examine a grouping strategy to detect irresponsible students more accurately. We demonstrate the effectiveness and limitations of our method using multi-agent simulation. Results show that our method can help with the marking of individual students in a group work.

Social networking services (SNSs) such as Facebook and Google+ are indispensable social media for a variety of social communications, but we do not yet fully understand whether these currently popular social media will remain in the future. A number of studies have attempted to understand the mechanisms that keep social media thriving by using ameta-rewards game that is the dual form of a public goods game. However, the meta-rewards game does not take into account the unique characteristics of current SNSs. Hence, in this work we propose an SNS-norms game that is an extension of Axelrod's metanorms game, similar to meta-rewards games, but that considers the cost of commenting on an article and who is most likely to respond to it. We then experimentally investigated the conditions for a cooperation-dominant situation in which many users continuing to post articles. Our results indicate that relatively large rewards compared to the cost of posting articles and comments are required, but optional responses with lower cost, such as "Like!" buttons, play an important role in cooperation dominance. This phenomenon is of interest because it is quite different from those shown in previous studies using meta-rewards games.

With the development of robot technology, we can expect self-propelled robots working in large areas where coordinated and collaborative behaviors by multiple robots are necessary. Thus, the learning appropriate strategy for coordination and cooperation in multiple autonomous agents is an important issue. However, conventional methods assumed that agents was given knowledge about the environment. This paper proposes a method of autonomous strategy learning for multiple agents coordination integrated with learning where are easy to become dirty in the environments using examples of continuous cleaning tasks. We found that agents with the proposed method could operate as effectively as those with the conventional method and we found that the proposed method often outperformed it in complex areas by splitting up in their works.

Network anomaly detection using dimensionality reduction has recently been well studied in order to overcome the weakness of signature-based detection. Previous works have proposed a method for detecting particular anomalous IP-flows by using random projection (sketch) and a Principal Component Analysis (PCA). It yields promising high detection capability results without needing a pre-defined anomaly database. However, the detection method cannot be applied to the traffic flows at a single measurement point, and the appropriate parameter settings (e.g., the relationship between the sketch size and the number of IP addresses) have not yet been sufficiently studied. We propose in this paper a PCA-based anomaly detection algorithm called ADMIRE to supplement and expand the previous works. The key idea of ADMIRE is the use of three-step sketches and an adaptive parameter setting to improve the detection performance and ease its use in practice. We evaluate the effectiveness of ADMIRE using the longitudinal traffic traces captured from a transpacific link. The main findings of this paper are as follows: (1) We reveal the correlation between the number of IP addresses in the measured traffic and the appropriate sketch size. We take advantage of this relation to set the sketch size parameter. (2) ADMIRE outperforms traditional PCA-based detector and other detectors based on different theoretical backgrounds. (3) The types of anomalies reported by ADMIRE depend on the traffic features that are selected as input. Moreover, we found that a simple aggregation of several traffic features degrades the detection performance. (C) 2012 Elsevier B.V. All rights reserved.

We propose an efficient team formation method for multi-agent systems consisting of self-interested agents in task-oriented domains. Services computing on computer networks have been rapidly increasing. Efficient team formation for service tasks is considered to be a way to improve performance. Our method is based on our previous parameter learning method enabling agents to efficiently form teams but requiring prior knowledge about all others' resources. We extended that method by adding a resource estimation method so as to increase its applicability to actual application systems. We experimentally evaluated our method by comparing it with the previous method and the task allocation using contract net protocol (CNP). The results demonstrated that the proposed method outperformed other methods even though it did not require prior knowledge about resources in other agents. We discuss the reason for this improvement.

We discuss a method of learning to determine appropriate roles for self-interested agents to efficiently form teams in task-oriented domains. A number of distributed applications are often expressed by task/resource allocation problems that can be modeled with a team formation problem in the multi-agent systems context so that tasks/resources are allocated to members of the team. Therefore, issues with efficient team formation have attracted our interest. The main feature of the proposed method is learning from two-sided viewpoints: team leaders who have the initiative to form teams or team members who work in one of the teams that are solicited. We introduce three parameters to agents for this purpose so that they can autonomously select their roles of being a leader or a member. Our experiments demonstrated that the amount of utility earned was considerably larger than that with conventional methods. We also conducted a number of experiments to investigate the characteristics of the proposed method. The results revealed that the proposed method could avoid excessive allocations to specific agents that had a large number of resources and disregarded agents that only had a few resources. Thus, teams could efficiently be formed. © 2013-IOS Press and the authors. All rights reserved.

We propose a team formation method that integrates the estimating of the resources of neighboring agents in a hierarchically structured agent network in order to allocate tasks to the agents that have sufficient capabilities for doing tasks. A task for providing the required service in a distributed environment is often achieved by a number of subtasks that are dynamically constructed on demand in a bottom-up manner and then done by the team of appropriate agents. A number of studies were conducted for efficient team formation for quality services. However, most of them assume that resources in other agents are known, and this assumption is not adequate in real world applications. We omitted this assumption and instead extended the conventional team formation method in which learning a team formation is combined with the resource estimation of neighboring agents as well as the reorganization method of the agent network. We experimentally show that this extended method exhibited performance comparable to the conventional methods even though it does not require knowledge of resources in other agents. © 2013 IEEE.

We propose a decentralized task allocation strategy by estimating the states of task loads in market-like negotiations based on an announcement-bid-award mechanism, such as contract net protocol (CNP), for an environment of large-scale multi-agent systems (LSMAS). CNP and their extensions are widely used in actual systems, but their characteristics in busy LSMAS are not well understood and thus we cannot use them lightly in larger application systems. We propose an award strategy in this paper that allows multiple bids by contractors but reduces the chances of simultaneous multiple awards to low-performance agents because this significantly degrades performance. We experimentally found that it could considerably improve overall efficiency.

We analyze domain name system (DNS) errors (i.e., Serv- Fail, Refused and NX Domain errors) in DNS traffic cap- tured at an external connection link of an academic network in Japan and attempt to understand the causes of such er- rors. Because DNS errors that are responses to erroneous queries have a large impact on DNS traffic, we should reduce as many of them as possible. First, we show that ServFail and Refused errors are generated by queries from a small number of local resolvers and authoritative nameservers that do not relate to ordinary users. Second, we demonstrate that NX Domain errors have several query patterns due to mostly anti-virus/anti-spam systems as well as meaningless queries (i.e., mis-configuration). By analyzing erroneous queries leading to NX Domain errors with the proposed heuristic rules to identify the main causes of such errors, we suc- cessfully classify them into nine groups that cover approxi- mately 90% of NX Domain errors with a low false positive rate. Furthermore, we find malicious domain names similar to Japanese SNS sites from the results. We discuss the main causes of these DNS errors and how to reduce them from the results of our analysis. Copyright © 2013 ACM.

We investigated the required conditions in which cooperation is dominant in social media using the model of a meta-rewards game, which is a dual part of Axelrod's metanorms game. Social media such as Twitter and Facebook have rapidly been growing in recent years. However, we do not know whether or not the currently popular social media will remain in the future. A number of studies have been conducted to try to understand the conditions or mechanisms that create and keep social media thriving using a public goods game and/or meta-rewards games, in which situations where many users post articles and respond to them as reactions in social media correspond to situations where cooperation is dominant in these games. However, they assume that agent networks in social media are complete graphs that are known to be dissimilar to actual social networks. We examined the conditions required to keep agent networks thriving based on Watts and Strogatz (WS) and Barabasi-Albert (BA) models, which are more similar to actual social networks. We experimentally found similarities and differences in the conditions for cooperation-dominant situations between networks based on complete graphs and those based on WS and BA models. Our results indicated that it was easier to maintain cooperation-dominant situations in BA-model networks than in other networks. © 2013 IEEE.

We propose a method for the autonomous learning of target decision strategies for coordination in the continuous cleaning domain. With ongoing advances in computer and sensor technologies, we can expect robot applications for covering large areas that often require coordinated/cooperative activities by multiple robots. In this paper, we focus the cleaning tasks by multiple robots or by agents, software to control the robots. We assume that agents cannot directly exchange internal information such as plans and targets for coordination, but rather individually learn their target decision strategies by observing how much trash/dirt has been vacuumed up in the multi-agent system environments. We experimentally evaluated the proposed method by comparing its performance with those obtained by the regimes of agents with a single strategy. Results showed that the proposed method enables agents to select target decision strategies from their own perspectives, resulting in the appropriate combinations of multiple strategies.

We describe a method for decentralized task/area partitioning for coordination in cleaning domains. Ongoing advances in computer science and robotics lead to robot applications for large areas that require coordinated tasks by multiple robots. We focused on a cleaning task to be performed by multiple robots with potentially different performances and developed a method for partitioning the target area to improve the overall efficiency through their balanced collective efforts. Agents autonomously decide how the task/area is to be partitioned by taking into account the characteristics of the environments. Experiments showed that the proposed method can adaptively partition the area among the agents so that they can keep it clean effectively and evenly. © 2013 Springer-Verlag.

We propose the technique to determine whether or not a set of keywords expresses the event that actually happened. In recent years studies to extract hot topics and the concerning keywords from chronologically ordered data have been increased. However, it is usually determined manually whether whether or not they express the events that actually happened. However such a human-intensive method is costly and often unfair. Hence we try to propose the suggest technique to automatically determine whether the keywords express the event. Finally we show that the proposed method can accurately determine them approximately 70%.

This paper presents a distributed task allocation method whose strategies are alternatively selected based on the estimated workloads of the local agents. Recent Internet. sensor-network, and cloud computing applications are large-scale and fully-distributed, and thus, require sophisticated multi-agent system technologies to enable a large number of programs and computing resources to be effectively used. To elicit the capabilities of all the agents in a large-scale multi-agent system (LSMAS) in which thousands of agents work concurrently requires a new negotiation strategy for appropriately allocating tasks in a distributed manner. We start by focusing on the contract net protocol (CNP) in LSMAS and then examine the effects of the awardee selection strategies, that is. the task allocation strategies. We will show that probabilistic awardee selections improve the overall performance in specific situations. Next, the mixed strategy in which a number of awardee selections are alternatively used based on the analysis of the bid from the local agents is proposed. Finally, we show that the proposed strategy does not only avoid task concentrations but also reduces the wasted efforts, thus it can considerably improve the performance.

This paper presents a distributed task allocation method whose strategies are alternatively selected based on the estimated workloads of the local agents. Recent Internet. sensor-network, and cloud computing applications are large-scale and fully-distributed, and thus, require sophisticated multi-agent system technologies to enable a large number of programs and computing resources to be effectively used. To elicit the capabilities of all the agents in a large-scale multi-agent system (LSMAS) in which thousands of agents work concurrently requires a new negotiation strategy for appropriately allocating tasks in a distributed manner. We start by focusing on the contract net protocol (CNP) in LSMAS and then examine the effects of the awardee selection strategies, that is. the task allocation strategies. We will show that probabilistic awardee selections improve the overall performance in specific situations. Next, the mixed strategy in which a number of awardee selections are alternatively used based on the analysis of the bid from the local agents is proposed. Finally, we show that the proposed strategy does not only avoid task concentrations but also reduces the wasted efforts, thus it can considerably improve the performance.

We propose a learning method for efficient team formation by self-interested agents in task oriented domains. Service requests on computer networks have recently been rapidly increasing. To improve the performance of such systems, issues with effective team formation to do tasks has attracted our interest. The main feature of the proposed method is learning from two-sided viewpoints, i.e., team leaders who have the initiative to form teams or team members who work in one of the teams that are solicited. For this purpose, we introduce three parameters to agents so that they can select their roles of being a leader or a member, then an agent can anticipate which other agents should be selected as team members and which team it should join. Our experiments demonstrated that the numbers of tasks executed by successfully generated teams increased by approximately 17% compared with a conventional method. © 2012 Springer-Verlag.

We propose a method of learning to determine appropriate roles for forming efficiently teams by self-interested agents in task-oriented domains. Service requests on computer networks have recently been rapidly increasing. To improve the performance of such systems, issues with efficient team formation to do tasks have attracted our interest. The main feature of the proposed method is learning from two-sided viewpoints, i.e., team leaders who have the initiative to form teams or team members who work in one of the teams that are solicited. For this purpose, we introduce three parameters to agents so that they can select their roles of being a leader or a member. Then, an agent can anticipate what other agents should be selected as team members and what team it should join. Our experiments demonstrated that the amount of utility earned as the result of successful team formation was considerably larger than that with a conventional method. We also conducted a number of experiments to investigate the characteristics of the proposed method. The results revealed that the divisional cooperation between agents was developed, which could reduce the chance of conflicts in decisions to play roles and this achieved efficient team formation. © Springer-Verlag Berlin Heidelberg 2012.

We propose the team formation method for task allocations in agent networks by reinforcement learning based on communication delay and by reorganization of agent networks. A task in a distributed environment like an Internet application, such as grid computing and service-oriented computing, is usually achieved by doing a number of subtasks. These subtasks are constructed on demand in a bottom-up manner and must be done with appropriate agents that have capabilities and computational resources required in each subtask. Therefore, the efficient and effective allocation of tasks to appropriate agents is a key issue in this kind of system. In our model, this allocation problem is formulated as the team formation of agents in the task-oriented domain. From this perspective, a number of studies were conducted in which learning and reorganization were incorporated. The aim of this paper is to extend the conventional method from two viewpoints. First, our proposed method uses only information available locally for learning, so as to make this method applicable to real systems. Second, we introduce the elimination of links as well as the generation of links in the agent network to improve learning efficiency. We experimentally show that this extension can considerably improve the efficiency of team formation compared with the conventional method. We also show that it can make the agent network adaptive to environmental changes. © 2012 IEEE.

In this paper, we show the possibility of predicting the anomalous packets&#039; behaviors to the near active addresses from small observation address space (Darknet) in Internet. We have proposed the distributed cooperative monitoring architecture (DCMA) which probes the anomalous packets that arrive at the distributed unused address segments and detects and defenses anomalous packets&#039; behaviors to the near active addresses. To realize DCMA, it is necessary to investigate the time-series correlation between anomalous packets arriving at small observation address segments and those of near addresses. Thus, we calculated the correlation strength of anomalous packets that scan address segments from the pairs of the sub-observation address segments divided from the Darknet addresses. Furthermore, we observed the correlation strength when changing the sub-observation&#039;s size and investigated the size dependency of the correlation strength. As a result, we could indicate the possibility of predicting the anomalous packets&#039; behaviors to the near address segments from small sub-observation addresses. We could also find that the base observation fixed to the specific sub-observation space contri

The network of bloggers interconnected by the comment exchange relationship obviously represents an aspect of human relationships. The paper reveals that interrelationships among items (such as products and works of art) can also be inferred based on structural characteristics of the network as follows. First, for each of two items in question, a set of bloggers writing about the item is respectively built. By &quot;plotting&quot; members of each blogger set on the network described above, distributions of the blogger sets are obtained. Then, selecting an appropreate index for measuring proximity of the distributions brings in a correlation between the proximity and the relevance of the items.

We propose an effective method of dynamic reorganization using reinforcement learning for the team formation in multi-agent systems (MAS). A task in MAS usually consists of a number of subtasks that require their own resources, and it has to be processed in the appropriate team whose agents have the sufficient resources. The resources required for tasks are often unknown \textit{a priori} and it is also unknown whether their organization is appropriate to form teams for the given tasks or not. Therefore, their organization should be adopted according to the environment where agents are deployed. In this paper, we investigated how the structures of network and the number of tasks affect team formations of the agents. We will show that the utility and the success of the team formation is deeply affected by depth of the tree structure and number of tasks.

In this paper, we propose a method for the dynamic migration of the IP routing points using binary particle swarm optimization (PSO) in distributed Virtual LAN environments. Virtual LAN (VLAN) is a virtualization technique of datalink layer and can construct arbitrary logical networks on top of a physical network. However, VLAN often causes much redundant traffic due to mismatch between the topology of the logical network and that of the underlying physical network. We will show that the proposed method can adaptively select the routing points dynamically according to the observed traffic patterns and thus reduce the redundant traffic. Finally, we will evaluate the proposed method using the simulation environment.

We propose an effective method of dynamic reorganization using reinforcement learning for the team formation in multi-agent systems (MAS). A task in MAS usually consists of a number of subtasks that require their own resources, and it has to be processed in the appropriate team whose agents have the sufficient resources. The resources required for tasks are often unknown \textit{a priori} and it is also unknown whether their organization is appropriate to form teams for the given tasks or not. Therefore, their organization should be adopted according to the environment where agents are deployed. In this paper, we investigated how the structures of network and the number of tasks affect team formations of the agents. We will show that the utility and the success of the team formation is deeply affected by depth of the tree structure and number of tasks.

Internet services are often exposed to many kinds of threats such as the distributed denial of service (DDoS), viruses, and worms. Since these threats cause an adverse effect on the social and economical activities on the Internet, the technologies for protecting Internet services from the threats are strongly required. Many researchers have analyzed network traffic to detect anomalous one using many packet features (e.g., TCP/IP headers). In this paper, we focus on the Time To Live (TTL) and Identification fields (IPID) of the IP header to understand the anomalous traffic behavior, since source IP addresses are often spoofed. We propose a method to distinguish a plausible spoofed IP address from others based on a sequence of TTL and IPID fields. We show that our method can extract a number of plausible spoofing packets from real dark net traces in which all of the packets were not normal. © 2011 IEEE.

We investigate the emergence and stability of social conventions for efficiently resolving conflicts through reinforcement learning. Facilitation of coordination and conflict resolution is an important issue in multi-agent systems. However, exhibiting coordinated and negotiation activities is computationally expensive. In this paper, we first describe a conflict situation using a Markov game which is iterated if the agents fail to resolve their conflicts, where the repeated failures result in an inefficient society. Using this game, we show that social conventions for resolving conflicts emerge, but their stability and social efficiency depend on the payoff matrices that characterize the agents. We also examine how unbalanced populations and small heterogeneous agents affect efficiency and stability of the resulting conventions. Our results show that (a) a type of indecisive agent that is generous for adverse results leads to unstable societies, and (b) selfish agents that have an explicit order of benefits make societies stable and efficient.

We propose a method of distributed team formation that uses reinforcement learning and dynamic reorganization by taking into account communication delay in multiagent systems (MAS). A task in a distributed environment is usually achieved by doing a number of subtasks that require different functions and resources. These subtasks have to be processed cooperatively in the appropriate team of agents that have the required functions with sufficient resources, but it is difficult to anticipate what kinds of tasks will be requested in the dynamic and open environment during the design stage of the system. It is also unknown whether or not their inter-agent network (that is, the organization of agents) is appropriate to form teams for the given tasks. In addition, communication delay between the agents always occurs in the actual systems, and this often causes a failure or delay of tasks. Therefore, both appropriate team formation and (re)organization suitable for the request patterns of incoming tasks and the environment where agents are deployed are required. The proposed method combines the learning for team formation and reorganization in a way that is adaptive to the environment. This includes task generation patterns and communication delay that may change dynamically. We show that it can improve the overall performance and increase the success rate of team formation in a dynamic environment. © 2011 IEEE.

This paper describes methods for controlling routing points of VLAN domains using binary particle swarm optimization (BPSO) and angle modulated particle swarm optimization (AMPSO). Virtual LAN (VLAN) is a technique for virtualizing datalink layer (or L2) and can construct arbitrary logical networks on top of a physical network. However, VLAN often causes much redundant traffic due to inappropriate deployments of network- layer (L3) routing capabilities in VLAN networks. We propose two methods using BPSO and AMPSO, and show that they can adaptively select the routing points dynamically in accordance with the observed traffic patterns and thus reduce the redundant traffic. The convergence features are compared with those of the conventional method on the basis of a statistical method. Then we also show that the scalability of the algorithm using AMPOS is high and thus we can expect that it is applicable to practical large VLAN environments.

Although analyzing anomalous network traffic behavior is a popular research topic, few studies have been undertaken on the analysis of communication pattern per host based on their flows to characterize the anomalous Internet traffic. This paper discusses the possibility of using a flow-based communication pattern per host as a metric to identify anomalies. The key idea underlining our method is that scanning worm-infected hosts reveal the intrinsic characteristics of host's communication pattern and such patterns are distinguishable from those of other hosts. In particular, we found that scanning of worm-infected hosts that generated a lot of flows revealed the intrinsic communication pattern and the pattern could be classified from those of other hosts by k-means clustering.We also found that our flow-based metric could isolate the anomalies that have little influence upon the volumetric information of traffic and flow as "lines", which is remarkable in that the hosts that caused the hidden anomalies were mined out. ©2010 IEEE.

We propose a probabilistic award selection strategy for a contract net protocol (CNP) in massively multi-agent systems (MMASs) for effective task allocations. Recent Internet and sensor network applications require sophisticated multi-agent system technologies to enable the large amounts of software and computing resources to be effectively used. Improving the overall performance of MMASs in which thousands of agents work concurrently requires a new negotiation strategy for appropriately allocating tasks to agents. Our proposed method probabilistically selects the awardee in CNP based on the statistical difference between bid values for subtasks that have different costs. We explain how our proposed method can significantly improve the overall performance of MMASs.

This paper proposes an autonomous energy saving method that works on wireless sensor networks. Wireless sensor nodes are equipment for gathering information about the user's surrounding environment. An energy-efficient data gathering system is required because each node is battery powered. Our method autonomously reduces the sampling frequency for monitoring environments whose condition may vary rapidly or slowly. Its simple lightweight computation scheme also helps to reduce battery consumption. We conducted experiments using real sensor data and found that our method performed well in terms of both power consumption and quality of sampled data.

This paper investigates the macroscopic behavior of unwanted traffic (e.g., virus, worm, backscatter of (D)DoS or misconfiguration) passing through the Internet. The data set we used are unwanted packets measured at /18 darknet in Japan from Oct. 2006 to Apr. 2009 that included the recent Conficker outbreak. The traffic behavior is quantified by the entropy of ten packet features (e.g., 5-tuple). Then, we apply PCA (principal component analysis) to a ten dimensional entropy time series matrix to obtain a suitable representation of unwanted traffic. PCA is a well-known and studied method for finding out normal and anomalous behaviors in Internet backbone traffic, however, few studies applied it to darknet traffic. We first demonstrate the high variability nature of the entropy time series for ten packet features. Next, we show that the top four principal components are sufficiently enough to describe the original traffic behavior. In particular, the first component can be interpreted as the type of unwanted traffic (i.e., worm/virus or scanning), and the second one as the difference in communication patterns (e.g., one-to-many or many-to-one). Those two components account for 63.8% of the original data set in terms of the total variance. On the other hand, the outliers in the higher components indicate the presence of specific anomalies although most of mapped data to the components have less variability. Furthermore, we show that the scatter plot of the first and second principal component scores provides us with a better view of the macroscopic unwanted traffic behavior.

Although analyzing anomalous network traffic behavior is a popular research topic, few studies have been undertaken on the analysis of communication pattern per host based on their flows to characterize the anomalous Internet traffic. This paper discusses the possibility of using a flow-based communication pattern per host as a metric to identify anomalies. The key idea underlining our method is that scanning worm-infected hosts reveal the intrinsic characteristics of host's communication pattern and such patterns are distinguishable from those of other hosts. In particular, we found that scanning of worm-infected hosts that generated a lot of flows revealed the intrinsic communication pattern and the pattern could be classified from those of other hosts by k-means clustering. We also found that our flow-based metric could isolate the anomalies that have little influence upon the volumetric information of traffic and flow as "lines", which is remarkable in that the hosts that caused the hidden anomalies were mined out.

In this paper, we introduce the probabilistic awardee selection strategy, under which awardee is selected with a fixed probability, into the award phase of contract net protocol. We then point out that, by changing the probabilities in this strategy according the local workload, the overall performance can be considerably improved.

This paper describes how, in large-scale multi-agent systems, each agent's adaptive selection of peer agents for collaborative tasks affects the overall performance and how this performance varies with the workload of the system and with fluctuations in the agents' peer selection policies (PSP). An intelligent agent in a multi-agent system (MAS) often has to select appropriate agents to assign tasks that cannot be executed locally. These collaborating agents are usually chosen according to their skills. However, if multiple candidate peer agents still remain a more efficient agent is preferable. Of course, its efficiency is affected by the agent' workload and CPU performance and the available communication bandwidth. Unfortunately, as no agent in an open environment such as the Internet can obtain such data from any other agent, this selection must be done according to the available local information about the other known agents. However, this information is limited, usually uncertain and often obsolete. Agents' states may also change over time, so the PSP must be adaptive to some extent. We investigated how the overall performance of MAS would change under adaptive policies in which agents selects peer agents using statistical/reinforcement learning. We particularly focused on mutual interference for selection under different workloads, that is, underloaded, near-critical, and overloaded situations. This paper presents simulation results and shows that the overall performance of MAS highly depends on the workload. It is shown that when agents' workloads are near the limit of theoretical total capability, a greedy PSP degrades the overall performance, even after a sufficient learning time, but that a PSP with a little fluctuation, called fluctuated PSP, can considerably improve it. © 2010 - IOS Press and the authors. All rights reserved.

Advanced Layer-3 (L3) switches achieve high-speed IP packet forwarding by storing parts of the header information from transmitted packets into the flow cache in the switch fabric when relaying the IP packets between subnets. When IP traffic is overloaded on an L3 switch, the flow cache is easily exhausted, decreasing the IP packet forwarding performance. Virtual LAN (VLAN), a virtualization technology at the data-link layer, is widely used for the internal networks of many organizations because it allows network configurations to be changed easily and provides design flexibility. In a VLAN-based local area network with multiple L3 switches, the relaying point for each VLAN can be placed on any of the L3 switches. We developed a new network control scheme called distributed virtual routing, which dynamically controls the packet exchange points for each VLAN to suppress the consumption of flow caches. We describe the basic concept and then evaluate the reduction of the relaying flows through the simulation using the real network data.

We describe a method for accurately estimating the topology of sensor networks from time-series data collected from infrared proximity sensors. Our method is a hybrid combining two different methodologies: ant colony optimization (ACO), which is an evolutionary computation algorithm; and an adjacency score, which is a novel statistical measure based on heuristic knowledge. We show that, using actual data gathered from a real-world environment, our method can estimate a sensor network topology whose accuracy is approximately 95% in our environment. This is an acceptable result for real-world sensor-network applications.

Using traffic random projections (sketches) and Principal Component Analysis (PCA) for Internet traffic anomaly detection has become popular topics in the anomaly detection fields, but few studies have been undertaken on the subjective and quantitative comparison of multiple methods using the data traces open to the community. In this paper, we propose a new method that combines sketches and PCA to detect and identify the source IP addresses associated with the traffic anomalies in the backbone traces measured at a single link. We compare the results with those of a method incorporating sketches and multi-resolution gamma modeling using the trans-Pacific link traces. The comparison indicates that each method has its own advantages and disadvantages. Our method is good at detecting worm activities with many packets, whereas the gamma method is good at detecting scan activities for peer hosts with only a few packets, but it reports many false positives for traces of worm outbreaks. Therefore, their use in combination would be effective. We also examined the impact of adaptive decision making on a parameter (the number of normal subspaces in PCA) on the basis of the cumulative proportion of each sketched traffic and conclude that it performs at a higher level than the previous method deciding only on one specific value of the parameter for every divided traffics.

The Internet consists of several thousand interconnected autonomous systems (ASes). For enabling the autonomous network management that ensures stable access at the inter-AS level and flexible inter-domain routing control, it is important to know how the routing information originated from an AS spreads throughout the Internet and to control inter-AS routing information using feedback actions based on observed network status at multiple ASes. Because each AS is controlled by a single administrative authority based on that AS's own policy, a cooperative distributed problem solving is desirable. To cope with these requirements, we have proposed a multi-agent-based inter-AS diagnostic system called ENCORE and inter-AS routing adjustment system called AISLE / VR. They consist of a collection of intelligent agents that are located in multiple ASes and perform collective observation, analysis, and control. These systems are constructed on the agent platform that provides utility functions on distributed environments. For the purpose of flexibility for incremental design and modification through the development and application phases, we adopted Lisp as the base language and have constructed stable systems that can demonstrate the effectiveness of our basic design for autonomous inter-AS network management. Copyright 2009 ACM.

We propose a method for estimating sensor network topology using only time-series sensor data without prior knowledge of the locations of sensors. Along with the advances in computer equipment and sensor devices, various sensor network applications have been proposed. Topology information is often mandatory for predicting and assisting human activities in these systems. However, it is not easy to configure and maintain this information for applications in which many sensors are used. The proposed method estimates the topology accurately and efficiently using ant colony optimization (ACO). Our basic premise is to integrate ACO with the reliability of acquired sensor data for the adjacency to construct the accurate topology. We evaluated our method using actual sensor data and showed that it is superior to previous methods.

An organizational information management system for multi-agent systems (MASs) on the Internet, called ARTISTE, is proposed. For an MAS to solve problems effectively, it is important to organize agents appropriately. Organizing agents adaptively on the Internet, however, is riot easy, because the status of the Internet changes dynamically in a short time and no one can have a complete view of the whole network. The aims of ARTISTE are to form an agent organization in accordance with the current Internet and its problem-solving context and to provide organizational information for target MASs. ARTISTE operates as an independent system with respect to any MAS. To organize agents, ARTISTE collects information about agents' abilities and statuses, network information such as topologies, and a problem-dependent requirement from a target MAS. ARTISTE is designed as an MAS, and it can collect the information about the network and the target MAS from multiple observation points. Furthermore, ARTISTE agents exchange their own local information in order to create a more global view of the network and the distribution of the agents. A prototype implementation of ARTISTE achieved sufficient performance to support deployment in the actual Internet environment.

We describe a new method to estimate the relevance of two items (such as products and works of art) on the basis of the relationship between the corresponding user (blogger) groups on a blogspace, where a user group refers to a collection of users interested in an item. We estimated the strength of the relationship between user groups on the basis of their proximity on the blogspace. We validated our approach through experimental studies using actual data.
In developing the method for estimating relevance among items, we introduced a new technique for measuring the proximity of two groups of vertices on a network, which can be thought of as an extension of conventional co-occurrence analysis.

Diagnosing the anomalies of inter-AS (autonomous system) routing and flexibly controlling its behavior to adapt to environmental changes are difficult, because this information changes spatially and temporally over different administrative domains. Multi-agent-based systems that coincide with this control architecture have been applied to these domains, bill; the number of deployed agents is small and more accurate analysis taking into consideration the actual Internet structure is desirable. To enable better analysis, cooperation among tens of thousands of agents is needed. This paper proposes a cooperative routing management system, called NetManager-M, which enables detailed analysis by using massively deployed agents on the Internet. NetManager-M call diagnose the routing flows around suspicious areas through cooperation among dynamically organized agents. This cooperation, which is conducted based oil the current and previous routing topology, enables monitoring of routing update messages at neighboring observation points and the identification of the causes of problems in more detail. This system is thus all effective means of detailed analysis for typical scenarios of inter-AS routing failures.

This paper proposes a situation-based conflict estimation method that efficiently generates quality plans for multi-agent systems (MAS) by appropriately selecting abstract plans in hierarchical planning (HP). In HP, selecting a plan at an abstract level affects planning performance because an abstract plan restricts the scope of concrete-level (or primitive) plans and thus can reduce the planning cost. However, if all primitive plans under the selected abstract plan have serious and difficult-to-resolve conflicts with the plans of other agents, the final plan after conflict resolution will be inefficient or of low quality. This issue originates in the uncertainty of MAS, where other agents also have individual plans for their own goals and it is difficult to clearly anticipate which abstract plan will cause fewer conflicts with other agents' plans. In the proposed method, by introducing conflict patterns that express the situations of conflicts among agents' plans, agents learn and estimate which abstract plans are less likely to cause conflicts or which conflicts will be easy to resolve; thus, after conflict resolution, they can induce probabilistically higher-utility primitive plans. This paper also describes an experiment to evaluate our method. The results indicate that our method can improve the efficiency of plan execution.

Diagnosing the anomalies of inter-AS (autonomous system) routing and flexibly controlling its behavior to adapt to environmental changes are difficult, because this information changes spatially and temporally over different administrative domains. Multi-agent-based systems that coincide with this control architecture have been applied to these domains, bill; the number of deployed agents is small and more accurate analysis taking into consideration the actual Internet structure is desirable. To enable better analysis, cooperation among tens of thousands of agents is needed. This paper proposes a cooperative routing management system, called NetManager-M, which enables detailed analysis by using massively deployed agents on the Internet. NetManager-M call diagnose the routing flows around suspicious areas through cooperation among dynamically organized agents. This cooperation, which is conducted based oil the current and previous routing topology, enables monitoring of routing update messages at neighboring observation points and the identification of the causes of problems in more detail. This system is thus all effective means of detailed analysis for typical scenarios of inter-AS routing failures.

We propose a method for estimating sensor network topology from only with time-series sensor data and without prior knowledge about the locations of sensors. The proposed method is based on ant colony optimization (ACO) but is further improved, compared with previous work[s], to construct a more accurate topology through an examination of the reliability of the acquired sensor data for the adjacency estimation. This reliability value is used to control the amount of pheromones deposited. We evaluate our method using actual sensor data and show that it can estimate adjacencies, in which the error rate is approximately 87% less than that of the previous method.

We describe a new adaptive manager-side control policy for the contract net protocol that uses the capabilities of all agents in a massively multi-agent system (MMAS). Recent advances in Internet services, pervasive computing, and grid computing require sophisticated MAS technologies to effectively use the large amount of invested computing resources. To improve overall performance, tasks must be allocated to appropriate agents, and from this viewpoint, a number of negotiation protocols were proposed in the MAS context. Most assume small-scale, unbusy environment, however. We previously reported the possibility that, using, contract net protocol (CNP), the overall efficiency improved by an adequate control of degree of fluctuation in the awarding phase, when the MMAS is in specific states. In this paper, we propose the method to estimate these specific states from the bid values, which have hitherto not been used effectively. Then the new manager-side policy flexibly and autonomously introduces some degree of fluctuation responsive to the estimated states. We also demonstrate that our proposed CNP policy provides considerably better performance than naive CNP and CNP with inflexible policies, even though our policy does not use global information.

In this paper, we investigate temporal and spatial correlations of time series of unwanted traffic (i.e., darknet or network telescope traffic) in order to estimate statistical behavior of unwanted activities from a small size of darknet address block. First, from the analysis of long-range dependency, we point out that TCP time series has a weak temporal correlation though UDP time series without huge flooding is well-modeled using a Poisson process. Next, we analyze the spatial correlation between two traffic time series divided by different sized darknet address blocks. We confirm that a TCP SYN traffic time series (e. g, virus or worm) has a clear spatial correlation in the arrival of packets between two neighboring address blocks. Indeed, this spatial correlation remains in traffic time series 1,000 addresses far from the target time series, even if a darknet address block is small (e.g., /26). On the other hand, TCP SYNACK traffic (e.g., backscatter) and UDP traffic (e.g., virus or worm) have less spatial correlation between two adjacent large address blocks. Finally, we estimate the average propagation delay of global unwanted activities appearing in TCP SYN traffic by using the generalized inter-correlation coefficient.

We studied the problem of finding a subspace of Web pages that is contextually consistent for co-occurrence analysis. We looked at blogs and proposed blogger-based co-occurrence analysis, which assumes that two items are relevant to each other if they appear in any of the blog entries posted by the same blogger. We show that (1) bloggerbased analysis outperforms page-based analysis in solving context-sensitive problems and that (2) analysis focused on bloggers forming a community yields better performance compared with that focused on isolated bloggers. © 2008 IEEE.

分散システムに関する諸問題の1つである,サーバ配置およびサーバ選択問題におけるネットワーク構造の統計的情報の利用可能性について議論する.従来のサーバ配置,サーバ選択問題においては,使用可能帯域遅延等に代表される動的なQoSを用いて系の安定性および効率性を追求してきた.しかしながら,既存の枠組みではネットワークの構造自身が提供する情報(静的QoS)を十分に生かしていない.本稿では,ASレベルインターネットトポロジを用いたシミュレーションを通じて,ネットワーク構造の統計的パラメータの一つである次数情報が,サーバ配置・選択問題の性能を改善する際に有用であることを示す.

文書に現れる語をノードとし,出現位置が近接しているものどうしをリンクで結び付けることにより得られる共起ネットワークでは,意味的関連性を有する語どうしがクラスタ構造と呼ばれる稠密な相互のつながりを形成している.本論文では,時間経過にともない文書が生成されていく,いわゆる文書ストリームから共起ネットワークを構成し,そこでクラスタ構造が生成される様子を調べた.その結果,共起ネットワークを(相対的に)古い語彙からなる部分と新しい語彙からなる部分に分けたとき,後者において,クラスタの出現という構造上の変化が,実社会の出来事などに起因する語の出現頻度の増大(バースト)に関連していることが明らかになった.

An agent organization system for multi-agent based network management, called ARTISTE, is proposed. For a multi-agent system (MAS) to solve problems effectively, it is important to organize agents appropriately. Organizing agents adaptively on the Internet, however, is not easy, because the status of the Internet changes dynamically in a short time and no one can have a complete view of the whole network. The aims of ARTISTE are to form an agent organization in accordance with the current Internet and its problem-solving context and to provide organizational information for target MASs. ART...

An agent organization system for multi-agent based network management, called ARTISTE, is proposed. For a multi-agent system (MAS) to solve problems effectively, it is important to organize agents appropriately. Organizing agents adaptively on the Internet, however, is not easy, because the status of the Internet changes dynamically in a short time and no one can have a complete view of the whole network. The aims of ARTISTE are to form an agent organization in accordance with the current Internet and its problem-solving context and to provide organizational information for target MASs. ARTISTE operates as an independent system with respect to any MAS. To organize agents, ARTISTE collects information about agents' abilities and statuses, network information such as topologies, and a problem-dependent requirement from a target MAS. ARTISTE is designed as an MAS, and it can collect the information about the network and the target MAS from multiple observation points. Furthermore, ARTISTE agents exchange their own local information in order to create a. more global view of the network and the distribution of the agents. Our performance evaluation showed that ARTISTE works with sufficient performance for use in the actual Internet environment.

We discuss the applicability of the degree of an agent-the number of links among neighboring agents- to load-balancing for the agent selection and deployment problem. We first introduce agent deployment algorithm that is useful in the design of MAS for loadbalancing. Then we propose an agent selection algorithm, which suggests the strategy for selecting appropriate agents to collaborate with. This algorithm only requires the degree of a server agent and the degrees of the node neighboring the server agent, without global information about network structure. Through simulation of several topologies reproduced by the theoretical network models, we show that the use of the local topological information significantly improves the fairness of the servers. © Springer-Verlag Berlin Heidelberg 2007.

An intelligent agent in a multi-agent system (MAS) often has to select appropriate agents to assign tasks that cannot be executed locally. These collaborating agents are usually determined based on their skills, abilities, and specialties. However, a more efficient agent is preferable if multiple candidate agents still remain. This efficiency is affected by agents' workloads and CPU performance as well as the available communication bandwidth. Unfortunately, as no agent in an open environment such as the Internet can obtain these data from any of the other agents, this selection must be done according to the available local information about the other known agents. However, this information is limited and usually uncertain. Agents' states may also change over time, so the selection strategy must be adaptive to some extent. We investigated how the overall performance of MAS would change under adaptive strategies. We particularly focused on mutual interference by selection in different workloads, that is, underloaded, near-critial and overloaded stituations. This paper presents the simulation results and shows the overall performance of MAS highly depends on the workloads. Then we explain how adaptive strategies degrade overall performance when agents' workloads are near the limit of theoretical total capabilities.

We discuss the applicability of the degree of an agent-the number of links among neighboring agents- to load-balancing for the agent selection and deployment problem. We first introduce agent deployment algorithm that is useful in the design of MAS for loadbalancing. Then we propose an agent selection algorithm, which suggests the strategy for selecting appropriate agents to collaborate with. This algorithm only requires the degree of a server agent and the degrees of the node neighboring the server agent, without global information about network structure. Through simulation of several topologies reproduced by the theoretical network models, we show that the use of the local topological information significantly improves the fairness of the servers.

An intelligent agent in a multi-agent system (MAS) often has to select appropriate agents to assign tasks that cannot be executed locally. These collaborating agents are usually determined based on their skills, abilities, and specialties. However, a more efficient agent is preferable if multiple candidate agents still remain. This efficiency is affected by agents' workloads and CPU performance as well as the available communication bandwidth. Unfortunately, as no agent in an open environment such as the Internet can obtain these data from any of the other agents, this selection must be done according to the available local information about the other known agents. However, this information is limited and usually uncertain. Agents' states may also change over time, so the selection strategy must be adaptive to some extent. We investigated how the overall performance of MAS would change under adaptive strategies. We particularly focused on mutual interference by selection in different workloads, that is, underloaded, near-critial and overloaded stituations. This paper presents the simulation results and shows the overall performance of MAS highly depends on the workloads. Then we explain how adaptive strategies degrade overall performance when agents' workloads are near the limit of theoretical total capabilities.

In this paper, we discuss about massively multi-agent coordination mechanisms, which must be necessary for upcoming applications in ubiquitous computing environment. In this situation, each agent cannot have a macroscopic view, so, the agents cannot obtain the global information of the agents as a whole. But, each agent behavior indirectly influences the other agents behaviors and their behaviors influence its behavior cyclically. Therefore a certain information about the relative position of each agent among all the agents may be able to be extracted from both each agent behavior and relativity of behaviors between agents. We verified this possibility by using the competitive multi-agent simulation environment, and firstly succeeded in extracting the information for the relative position from each agent behavior. Then we succeeded to extract the relativity of behaviors between agents as the "agent coordination network", which had the characteristics of both scale free network and small world network. © 2007 IEEE.

In hierarchical planning, selecting a plan at an abstract level affects planning performance because an abstract plan restricts the scope of primitive plans. However, if all primitive plans under the selected abstract plan have difficult-to-resolve conflicts with the plans of other agents, the final plan after conflict resolution will be inefficient or of low quality. In this paper, we propose a conflict estimation method to generate quality plans efficiently for multiagent systems by appropriately selecting abstract plans in hierarchical planning. This method enables agents to learn which abstract plans are less likely to cause conflicts or which conflicts will be easy to resolve. © 2007 IFAAMAS.

The performance features of a massively multiagent system (MMAS) when applying the contract net protocol (CNP) are examined. The recent growth in the volume of e-commerce on the Internet is increasing the opportunities for coordinated transactions by agents, concurrently occurring everywhere. Because of limited CPU and network resources, running many interactive tasks among agents can lower the quality or efficiency of MMASs. Although CNP is a widely used negotiation protocol that can allocate tasks and resources to appropriate agents, it is unclear how effectively CNP works in an MMAS where thousands of agents work together and interfere with each other. The performance of CNP in such an MMAS, especially the overall efficiency and the reliability of promised completion times, is investigated by using an MAS simulation environment. The results show that only manager-side control of CNP can improve performance in an MMAS.

Diagnosis of anomalous routing states is essential for stable inter-AS (autonomous system) routing management, but it is difficult to perform such actions because inter-AS routing information changes spatially and temporally in different administrative domains. In particular, the route hijack problem, which is one of the major routing-management issues, remains difficult to analyze because of its diverse distribution dynamism. Although a multi-agent-based diagnostic system that can diagnose a set of routing anomalies by integrating the observed routing statuses among distributed agents has been successfully applied to real Internet service providers, the diagnostic accuracy depends on where those agents are located on the BGP topology map. This paper focuses on the AS adjacency topology of an actual network structure and analyzes hijacked-route behavior from the viewpoint of the connectivity of each AS. Simulation results using an actual Internet topology show the effectiveness of an agent-deployment strategy based on connectivity information.

We present GEO (Generating an Extensional definition from an Ostensive definition), a method to exhaustively gather items falling under an ostensively defined concept from the Web. By utilizing structural information about HTML documents, GEO automatically and efficiently gathers thousands of items from Web pages taking only 2 or 3 items as input. GEO also yields high precision (0.99 at maximum, 0.97 in average over a set of inputs). We also introduce a new style of searching information, called Item Search, in which GEO plays an essential role. Item Search can look for items in a targeted category that are the best matches against a given query. Some examples of Item Search are presented as the proof-of-concept of the idea.

In this paper we analyze a simple adaptive model of competition called the Minority Game, which is used in analyzing competitive phenomena such as the operation of the market economy. The Minority Game is played by many simple autonomous agents, which develop collective self-organization as a result of simple behavioral rules. Many algorithms that produce the desired behavior in the game have been proposed. In all work to date, however, the focus has been on the macroscopic behavior of the agents as a whole. We focus on the behavior of individual agents, paying particular attention to the original form of the Minority Game. We suggest that the core elements responsible for the development of self-organization are (i) rules that place a good constraint on the behaviors of individual agents and (ii) the existence of rules that lead to effective indirect coordination. We also show that when efficient organization is formed, a power-law can be seen among behavior of individual agents. © 2006 Springer-Verlag Berlin Heidelberg.

In order to achieve efficient progress in activities such as e-commerce and e-transactions in an open environment like the Internet, an agent must choose appropriate partner agents for collaboration. However, agents have no global information about the whole multi-agent system (MAS) and the state of the Internet
therefore, they must select the appropriate partners based on local knowledge and local observations. In this paper, using a multi-agent simulation, we discuss how total MAS performances are affected by local decisions when agents select partners to collaborate with. We also investigate how MAS performances change and how network structures between agents shift according to the progress of agents' local learning and observations. We then discuss the relationship between task load and agent network structure. This relates to estabilishing the optimum time when agents should learn about appropriate partners in an actual environment. Copyright 2006 ACM.

In the multi-agent systems, even if each agent behaves selfish or cooperative, its behavior influences the other agents' behaviors and their behaviors influence its behavior cyclically. Thereore a certain information about the relative position of each agent among all the agents may be able to be extracted only from its behavior. If this information can be extracted, each agent has the possibility to improve its efficiency only by seeing its own behavior without knowing about the information of the other agents. In this paper, we verified this hypothesis by using the competitive multi-agent simulation environment named Minority Game, and confirmed that each agent's performance gain was actually possible. This analytical technique may be especially useful for massively multi-agent systems. Copyright 2006 ACM.

An agent in a multi-agent system (MAS) has to select appropriate agents to assign tasks. Unfortunately no agent in an open environment can identify the states of all agents, so this selection must be done according to local information about the other known agents; however this information is limited and may contain uncertainty. In this paper we investigate how overall performance of MAS is affected by learning parameters for adaptive strategies to select partner agent for collaboration. We show experimental results using simulation and discuss why overall performance of MAS varies.

Unexpected temporal and spatial changes of inter-AS routing behavior often lead to the necessity of on-demand inter-domain routingadjustment. For resolving this problem, we apply the AISLE framework, which is a multi-agent-based model, to a policy-based routingadjustment system for transit ISPs and their customer ASs. This paper describes the BGP-control architecture called VR (Virtual Router) that can dynamically change forwarding paths considering alternative paths, which are inferred from historical data and confirmed when they are actually applied. VR can control conventional multiple border routers in an AS without any protocol extensions. The policy description, which is interpreted by an agent, enables network operators to define autonomous actions for analyzing network status and adjusting inter-AS routing based on these observed results by issuing requests to VR. Some evaluation results indicate that VR can effectively change routing over BGP data on the actual Internet and some control scenarios based on policy descriptions demonstrate the validity of our basic design framework. Copyright 2006 ACM.

This paper shows that the statistical properties of the network topology are indispensable information for improving performance of multi-agent systems (MASs), though they have not received much attention in previous MAS research. In particular we focus on the applicability of the degree of an agent-the number of links among neighboring agents to load-balancing for the agent selection and deployment problem. The proposed selection algorithm does not need global information about the network structure and only requires the degree of a server agent and the degrees of the nodes neighboring the server agent. Through simulation of several topologies reproduced by the theoretical network models, we show that the use of the local topological information significantly improves the fairness of the servers even for a large-scale network. We also find that the key mechanisms for load-balancing in a given network topology are highly asymmetric degree characteristics (scale-free) and the negative degree correlation.

インターネットの普及やブロードバンド化により, インターネットの利用がe-Learning等の教育の分野にも広がりつつある.また, 講義や講演等をビデオ録画し, 後からいつでも見られるシステムが実用化され, 実際に使われている.しかし, それらのシステムでの動画に対する操作は, 再生・早送り・巻き戻し等の従来のVCRの機能や, スライドバーにより任意の位置から再生する等の機能しかない.今後, 動画像の利用が増加することを考えると, 動画像をより短時間で, しかも意味ある情報をなるべく欠落させずに見る機能が必要になる.我々は, 映像中の音情報と画像情報を用いて, 重要と思われるシーンを抜き出し映像を短縮する方法について研究を進めている.我々は作成したプロトタイプシステムを教育用映像に利用し, 短縮化した画像を初期教育用, さらには復習等の目的に適用することを考えている.本稿では, 教育用映像を本システムを用いて短縮した場合の内容の理解度に与える影響につい

動画内の対象や領域にURLを対応させ, その情報を映像と同時に配信し, 再生時に対象物をクリックすることで, 動画から他のURLの情報を取得できるメディアがいくつか提案されている.しかし, 動画の一部に選択可能(クリック可能)なエリアを指定することは容易ではない.リンクを貼り付ける対象はフレームごとに位置が変わり, フレームごとに領域を指定する作業が必要となる.本論文では, 実体をデジタルカメラもしくはデジタルビデオカメラで撮影するときに, クリック可能としたい対象が写っている領域とそのリンク先URLや撮影時刻などの関連情報も同時に取得し記録すること, およびその一実現方式として赤外線の波長差分を使う方式について提案する.さらに, その実験システムを作成したので評価結果を述べる.この実験結果から, 蓄積型の映像配信だけでなく, 実時間での動画像のライブ中継も可能であることが分かった.また, 複数対象物のモーションキャプチャにも利用可能と考えら

We discuss how humans interact with the environment like mental and physical harmonization. Keyword is "resonance". Each human has his own natural frequency, which is a metaphor for personality or daily habitual behaviors. In the proposed framework, each human behavior reacts the environment and the environment performs sensor-data mining and extracts each human's natural frequency. The environment constructed from a multi-agent system is always watching humans, and when there is information to give one particular human, the environment interacts with him by using his natural frequency, so he can spontaneously and efficiently get the information from the environment. To achieve this, we set up several interaction devices between humans and the environment as well as various kinds of many sensors.

To quantify the statistical dynamics of the BGP, we analyze the temporal and spatial correlation of macroscopic BGP message flows obtained by passive measurement. We show that the time series for the number of announcement and withdrawal messages has little correlation in time, unlike the statistical behavior of traffic volumes. This indicates that there is little possibility of a cascading failure, in which a failure causes following failures, and that the occurrence of burst of BGP messages has a Poisson nature. We also point out that there is space correlation with the delay between the flows for the different measurement points. Namely, even from macroscopic and passive measurement, we show that the propagation delay of routing information from one measurement point to another point can be statistically estimated.

In this paper we focus on the effectiveness of using the power-law relationship that appears in actual network topology for solving server selection and allocation problems in multi-agent systems (MAS). We introduce the reverse weighted degree (RWD) server selection algorithm, which selects the nearest server with a lower load average, and the concept of the scope, which spreads the range of the topological information about neighbors. Furthermore, we evaluate the efficiency and fairness of the algorithm when server deployment is performed by using the degree-oriented server allocation, which places the server agent on more convenient nodes from the viewpoint of network topology, and by random server allocation. From simulation results using the real Internet topology, we find that awareness of the network structure can improve the total performance of agents significantly, though previous approaches in MAS did not consider the topology of the network.

Verifying whether the routing information originating from an AS is being correctly distributed throughout the Internet is important for stable inter-AS routing operation. However, the global behavior of routing information is difficult to understand because it changes spatially and temporally. Thus, rapid detection of inter-AS routing failures and diagnosis of their causes are also difficult. We have developed a multi-agent-based diagnostic system, ENCORE, to cope with these problems, and improved its functions (ENCORE-2) through our experience in applying the system to commercial ISPs. Cooperative actions among ENCORE-2 agents provide efficient methods for collecting, integrating, and analyzing routing information observed in multiple ASes to detect and diagnose anomalies that human operators have difficulty in handling. ENCORF-2 is also applied to the hijacked route problem, which is one of recent major inter-AS issues.

Generally, in multi-agent systems, there are close relations between behavior of each individual agent and the group of agents as a whole, so a certain information about the relative state of each agent in the group may be hided in each agent behavior. If this information cart be extracted, each agent has the possibility to improve its state by seeing only its own behavior without seeing other agents' behaviors. In this paper, we focus on "power-law" which is interesting character seen in the behavior of each node of various kinds of networks as one of such information. Up to now, we have already found that power-law can be seen in the efficiently behaving agents in Minority Came which is the competitive multi-agent simulation environment. So, in this paper we have verified whether it is possible for each agent in the game to improve its state by seeing only its own behavior, and confirmed that the performance gain was actually possible.

ユーザのアクセス履歴を利用して,互いに類似するコンテンツを保持する可能性が高いWebサイト集合を効率的に検出する手法を提案する.ユーザがWebサイトに埋め込まれているリンクをクリックした際の,リンクの「URL情報」と「ラベル文字情報」のみを手掛りとして使用する.今回はその基本的有効性の検証を行った.

ユーザが自由にVPNを使うようになり, 1つのホストで複数のネットワークを同時に扱う状況が増えてきている. しかしながら, 従来のOSは複数のネットワークを排他的に利用する機構を提供していないため, IPアドレスが衝突するネットワークを同時に扱えず, VPN内部の機密情報を他のネットワークに漏らしてしまう危険性もある. そこで我々は複数のVPNを扱うホストの実行環境をVPN毎に分離しその実行環境とVPNを統合したパーソナルネットワークを提案する. ポートスペースと呼ばれるこの分離された実行環境は, プロセスを実行する時のネットワークやファイルシステムの環境であり, プロセスとVPNを密接に関係づけることにより独立したパーソナルネットワークの構築を可能にする.

In this paper we analyze a simple adaptive model of competition called the Minority Game, which is used in analyzing competitive phenomena in markets. The Minority Game consists of many simple autonomous agents, and self-organization occurs as a result of simple behavior rules. Up to now, the dynamics of this game have been studied from various angles, but so far the focus has been on the macroscopic behavior of all the agents as a whole. We are interested in the mechanisms involved in collaborative behavior among multiple agents, so we focused our attention on the behavior of individual agents. In this paper, we suggest that the core elements responsible for forming self-organization are: (i) the rules place a good constraint each agent's behavior, and (ii) there is a rule that leads to indirect coordination. Moreover, we tried to solve the El Farol's bar problem based our suggestions.

In this paper, we propose a new time-reduction method for video skimming in which the focus is on the overall playback time. While fast-forwarding is a natural way to check whether or not items are of interest, the sound is not synchronized with the images and the lack of comprehensible audio data means that we must work from the images alone. The focus in video summarization has been solely on video segmentation, i.e. building a structure that represents the parts and flow of meaning in the video. In our system, the user simply specifies the running time required for the summarized video. We describe the current state of our prototype system and its results in testing, which show how well it works.

This paper discusses a method for identifying clickable objects/regions in still and moving images when they are being captured. A number of methods and languages have recently been proposed for adding point-and-click interactivity to objects in moving pictures as well as still images. When these pictures are displayed in Internet environments or broadcast on digital TV channels, users can follow links specified by URLs (e.g., for buying items online or getting detailed information about a particular item) by clicking on these objects. However, it is not easy to specify clickable areas of objects in a video because their position is liable to change from one frame to the next. To cope with this problem, our method allows content creators to capture moving (and still) images with information related to objects that appear in these images including the coordinates of the clickable areas of these objects in the captured images. This is achieved by capturing the images at various infrared wavelengths simultaneously. This is also applicable to multi-target motion capture.

本論文では仮想ネットワークアーキテクチャによる保護機構(VNAP)を提案する.VNAPでは仮想LANの技術を用いて目的や用途に応じた複数の通信クラスをイントラネット内に実現する.この各々の通信クラスがOS内の資源やアプリケーションの実行環境と連係することで,イントラネット全域にわたる多層の保護階層が実現される.この通信クラスはネットワーク上の保護ポリシを具現化したものであり,その情報をネットワーク管理者・プログラマ・ユーザで共有することにより,相互の協調によるイントラネット環境の安全性の向上を実現する.本論文では,VNAPの概念や構成とあわせて,プロトタイプシステムの実装と評価についても述べる.

Inter-AS routing is difficult to control since advertised inter-AS routing information changes as it spreads through ASs that are managed based on each own policy. For operating the Internet reliably as we intend, we propose flexible and autonomous policy control environment AISLE. AISLE uses cooperative actions among distributed agents to know and control inter-AS routing behavior This paper describes AISLE model and architecture that enable policy control at the inter-AS level.

This paper presents personal networks, which integrate a VPN and the per-VPN execution environments of the hosts included in the VPN. The key point is that each execution environment called a portspace is bound to only one VPN, i.e., single-homed. Using this feature of portspaces, personal networks address several problems at multi-homed hosts that use multiple VPNs. Information flow is separated by personal networks so that it is not mixed at multihomed hosts. IP addressing in a personal network is independent of the other personal networks, even the base network, and therefore does not conflict with those of other networks at multi-homed hosts. In addition, personal networks provide facilities for easy bootstrapping so that the end-users can construct such isolated networks easily. Inheritance of portspaces supports the creation of new portspaces based on existing portspaces. Self-construction of personal networks enables end-users to construct personal networks without help from the base network.

Emerging ubiquitous and pervasive computing applications often need to know where things are physically located. To meet this need, many location-sensing systems have been developed, but none of the systems for the indoor environment have been widely adopted. In this paper we propose Proximity Mining, a new approach to build location information by mining sensor data. The Proximity Mining does not use geometric views for location modeling, but automatically discovers symbolic views by mining time series data from sensors which are placed in surroundings. We deal with trend curves representing time series sensor data, and use their topological characteristics to classify locations where the sensors are placed.

This paper discusses the storage and analysis of past hierarchical-planning results in order to identify implicit costs and resource relationships between activities in multi-agent contexts. We have previously proposed a plan-reuse framework in which plans are stored as templates after use and then reused to speed up planning activity in multi-agent systems. In this paper, we propose the mechanizm for learning, from templates that consist of used plans and data recorded during planning and execution, implicit relationships concerning resource usage by multiple agents. Here, implicit indicates that the relationships exist in the environments where agents are deployed but are not described in the domain models the agents have. The plan-reuse framework also provides guidance on which data the planner and executor should record and on when the learned rules should be applied. Finally, some examples show how this learning enables the creation of more appropriate solutions by agents.

This paper proposes Clea, a framework for the coordination of applications and networks. Clea conveys requests from applications to networks and enables information on network characteristics, status, and functions to be used by applications. This makes it possible for an application to adapt flexibly to dynamic changes in network status and to utilize network resources effectively. Clea also enables coordination of applications and networks to be described in a uniform and concise manner.

当初テキストや静止画の交換が主体であったWWWも, 最近では音や動画像, 三次元データ等, 様々なメディアデータの交換の道具として利用されている.しかし, WWWによる情報交換ではサーバに蓄積したデータの読み出しが中心で, 本に対する書き込みのような情報の付加はあまり行われていない.本稿では, 様々な種類のメディアデータに対して, アノテーション(Annotation: 注釈)の形での情報の付加を可能にするシステムCmew/Uの設計と実装について述べる.本システムはメディアごとに異なるアノテーション埋め込みの機能をモジュールとして実現することで, 高い拡張性を提供している.また, 性能評価の結果, インターネットの転送遅延に対して十分に小さいオーバヘッドでアノテーション埋め込みの機能が実現できることを示す.

インターネットの安定運用を実現するためには, 自律システム (AS) がインターネットに広報した経路情報の振舞いを理解し, 自 AS の意図が正しく反映されて伝わっていることを検証することは重要である. この機能を実現するため, 他の AS 内の環境において要求元 AS に関する観測を行い, その結果を解析して返送するための協調動作の枠組みを示すリフレクタモデルを定義し, それを基本動作として自らの持つ診断知識に基づいて自律的に動作する, マルチエージェントによる AS 間障害診断システム ENCORE を提案する. 本システムは, 各 AS に観測機能を持ったエージェントを配置し, エージェントが自らの持つ診断知識に基づいて他の AS 中のエージェントと協調することにより, ネットワークの障害を解析する.

We describe the design and implementation of a multimedia Web annotation system that enables users to add information to multimedia contents obtained through the World Wide Web. We have developed a highly modular annotation server that stores users' annotations and embeds them into multiple types of contents including plain text, HTML documents and MPEG video. This system also provides a mechanism for sharing the annotations among multiple users using the same server.

This paper proposes and evaluates MarLee, a multi-agent reinforcement learning system that integrates both exploitation- and exploration-oriented learning. Compared with conventional reinforcement learnings, MarLee is more robust in the face of a dynamically changing environment and is able to perform exploration-oriented learning efficiently even in a large-scale environment. Thus, MarLee is well suited for autonomous systems, for example, software agents and mobile robots, that operate in dynamic, large-scale environments, like the real-world and the Internet. Spreading activation, based on the behavior-based approach, is used to explore the environment, so by manipulating the parameters of the spreading activation, it is easy to tune the learning characteristics. The fundamental effectiveness of MarLee was demonstrated by simulation.

This paper introduces the learning mechanism by which agents can identify, through experience, important messages in the context of inference in a specific situation. At first, agents may not be able to immediately read and process important messages because of inappropriate ratings, incomplete non-local information, or insufficient knowledge for coordinated actions. By analyzing the history of past inferences with other agents, however, they can identify which messages were really used. Agents then generate situation-specific rules for understanding important messages when a similar problem-solving context appears. This paper also gives an example for explaining how agents can generate the control rule.

This paper considers cooperative and distributed problem-solving in an environment where similar problems are repeatedly posed, and discusses methods for plan reuse. In distributed planning including multiple agents, the agents generate the plan cooperatively from various viewpoints which results in a plan with high cost. The reuse of the plan realizes efficient planning by utilizing the plan for similar previous problems. The first feature to note in applying plan reuse to a multi-agent system is the problem similarity. Even if an agent decides that two problems are the same, another agent may consider a totally different goal or viewpoint. In this paper, it is shown that under certain conditions, the reuse of a plan is effective independently of the goals of other agents. A planning method including reuse is presented. Finally, it is shown experimentally that efficient planning can be realized. © 1997 Scripta Technica, Inc.

本論文では, ある程度類似した問題が繰り返される環境での分散協調問題解決に対し, プランの再利用を適用する方法について述べる. 複数のエージェントによる分散プランニングでは, 協調を実現するために各エージェントがそれぞれの観点から協力してプランを生成する. このため, コストの高いタスクとなる. プランの再利用は, 過去の類似した問題に対するプランを使って, 効率的なプランニングを実現するものである. プランの再利用をマルチエージェントに適用するときの第1の論点は問題の類似性である. つまり, あるエージェントが同一の問題と判断しても, 他のエージェントは全く異なるゴールや観点をもっているかもしれない. ここでは, ある条件のもとで, 他のエージェントのゴールにかかわらずプランの再利用が有効であることを議論し, 再利用を含めたプランニングの方法について述べる. 最後に, 実験的に効率的なプランニングが可能であることを示す.

With the expanding use of the computer networks based on LAN, there is a rapid increase of fault generation. A tremendous amount of time and effort is required in the dissolution of those faults since the origins of those faults are physically distant and the data are difficult to obtain due to the distributed management. In addition, the prevention, as well as the early detection and remedy of faults, are required since a failure may affect a broad range. The authors have constructed a diagnosis/observation expert system LODES for LAN, by constructing a knowledgebase of the experiences in dissolving the failure. LODES discovers the violation of protocol by referring to the TCP/IP‐related protocols, automatic detection of fault (or its indication) by observing packets, and points out the abnormality/missetting of network‐related information of the host. In the diagnosis, it has the feature that the distributed cooperative problem‐solving is executed by communicating among LODES (large internetwork observation and diagnosis expert system) attached to each of the network segments. LODES is actually operated, and it is shown that the phenomena and failures which have not been detected can now be detected. Copyright © 1992 Wiley Periodicals, Inc., A Wiley Company