<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

<p>People often belong to multiple communities and accommodate themselves to majority opinion in each community. Thus, they sometimes express different and occasionally inconsistent opinions in the individual communities. When the inconsistency in opinion is uncovered, she/he may be criticized, and then, quit expressing opinions. Recently inconsistency in opinion is easily uncovered because of the growth of communication tools, e.g. SNS. Therefore, we investigate the mechanism of quitting expressing opinion because of the criticism of the inconsistency in opinions in social media. We modeled multiple communities as multiplex networks and investigate how opinions are formed and why users quit expressing opinions due to uncovered inconsistency. For this purpose, we first extended a conventional model whose opinion formation mechanism is based on the bounded confidence model. Then we also considered different opinion formation mechanisms and examined opinion formation in different types of multiplex complex networks, in order to adjust more realistic situations.</p>

本研究では連続活動時間に制限のある自律エージェントによる継続巡回問題を扱う．我々はこれまでに，単一エージェントの自律的な戦略学習と単純な交渉によって主に担当する場所や範囲が分離する分業体制をボトムアップに構築できることを示唆した．本論文では，全エージェントが環境全体に責任をもつ場合よりも提案手法による分業体制がエージェントの活動停止に対するロバスト性を向上させることを示し，その要因を分析した．

Traffic jam in a big cities is a serious problem which may cause environmental pollution and time loss of driver. The current traffic signals are controlled using the static parameter values. However, such static control cannot adapt to sudden changes of traffic patterns, resulting heavy traffic jams. Therefore, a number of studies for real-time signal controls based on multi-agent models have been conducted. However, most of these studies do not consider right-turn and time-difference signals, thus this control patterns are limited. So, we propose the method in which appropriate signal duration of right-turn and time-difference signals should be controlled according to traffic volume at individual traffic light.

We propose a charge-discharge method of home battery by estimating electricity consumption profile and market price. We assume that some homes have solar panels and home battery, and they can exchange electric power at the local market. Agents running on smart meters calculate their charge-discharge schedules by taking into account buying and selling their surplus and necessary electricity via market in order to minimize their expenditure. Then, we introduce the norm for stabilization of electricity demand to ease erratic fluctuation by limiting the market exchange. Finally, we experimentally show that total demand was flattened with the proposed method, and thus, home profits increased.

We have studied the strategy learning in multi-agent continuous cleaning task in which we assumed that agents knew the probability of dust accumulation in environment, since we paid attention to autonomous strategy learning for coordination. However, in actual environments, agent cannot necessarily get the environmental information in advance. Therefore, we extended the previous method for the environment where agents do not know where are easy to get dirty, which is a part of environment information. The experimented results showed that agents could learn the probability of dust accumulation as well as the appropriate strategies, and in some cases, the performance with the proposed method outperformed the previous method even though some information is missing.

This paper defines the selective resource allocation problem that maximizes the sum of their values in individual agents with taking into account the agents&#039; preference orders and proposes the auction-based method to find semi-optimal allocations. This problem is one goods to be allocated, but granted to the desire rank goods, allocation takes priority to it. However, the calculation is increased explosively with the number of goods. In the propose method, we aim to improve the social surplus by taking into account the desired order of the consumer by the successful bidder decision algorithm and bidding phase. Finally, we demonstrate the utility of the proposed method by compare and evaluate the solution and computation time of high speed linear solver CPLEX.

We aim at achieving autonomous team formation for efficient task assignment by limiting the group that formed through past experience of reward distribution and the successful ratios of task processing in multi-agent systems. Supposing team formation in large-scale multi-agent systems, the costs for any agent&#039;s selecting member and for processing messages among agents considerably increase and thus agents are being exposed to increase contention for selecting members. We focus on the fact that the process for team formation to use agent&#039;s resource in the past studies is quite similar with the feature of iterative Ultimatum game. We try to formulate the resource allocation problem using iterative multi-person ultimatum game and investigate the effects of rationality and fairness of agents on the stability of autonomous team formation.

We propose a method for decentralized task/area partitioning for coordination in cleaning domains. We focused on a cleaning task to be performed by multiple robots with potentially different performances and already developed a method for partitioning the target area to improve the overall efficiency through their balanced collective efforts by taking into account the characteristics of environments. We extended this method in which agents autonomously decide how the task/area is to be partitioned by taking into account the capability of themselves as well as 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.

We propose an efficient team formation method for multi-agent system in a large-scale environment. We previously proposed the parameter learning method that enables agents to identify their roles through team formation without assumption that agents have information about resources of other agents. However, this method assumes that each agent have to maintain the learning parameters for all other agents. Thus, it required consider- able computational time and large memory when the number of agents increased. To overcome this problem, we introduce the concept &quot;purviews,&quot; which are the small set of agents that are the potential members of the future teams. They also used to restrict the agents to learn their resources and their parameters for role decision, their parameters for role Agents also revise the purviews according to the contribution in the team formation. The result shows that the proposed method increase the received utilities in comparison with our previous method in large-scale, busy multi-agent systems.

We have studied the strategy learning in multi-agent continuous cleaning task in which we assumed that agents knew the probability of dust accumulation in environment, since we paid attention to autonomous strategy learning for coordination. However, in actual environments, agent cannot necessarily get the environmental information in advance. Therefore, we extended the previous method for the environment where agents do not know where are easy to get dirty, which is a part of environment information. The experimented results showed that agents could learn the probability of dust accumulation as well as the appropriate strategies, and in some cases, the performance with the proposed method outperformed the previous method even though some information is missing.

In this research, we proposed Charge-and-discharge planning method of home battery working on Smart Meter in the electric power market model of the neighboring homes in the same area. This method is planned to charge when the demand is lower, discharge when it is higher, this is because electricity charge is in proportion to demand. We evaluated this methods by Multi Agent Simulation. As a result, it is suggested that the optimal parameter exists according to the environment of the area. And the welfare of each home is increased, if home battery or solar panel is established.

We propose a method for efficient task allocation by changing the network structure among agents to adapt to the environmental changes. As services in a distributed environment like the Internet often consist of a number of service elements, the task for the service can be modeled as a set of subtasks and can be achieved by executing all the subtasks. So they are executed in appropriate agents that have required resources and/or functionalities to In order to realize the corresponding services, this type of problem is formulated as a team formation problem in which all (sub)tasks are allocated to a number of agents (team). A number of studies addressed this issue; proposed a method by adding links between agents based on the amount of unused resources in a task-oriented domain. However, this kind of methods have the drawback that the reorganization stops in an earlier stage of learning. It also retains the generated links, but when the types of the requested tasks change, it could not adapt quickly to the new distribution of incoming tasks. The method proposed in this paper generates a new link that can allocate tasks to unbusy agents and eliminates the link that is hardly used based on the numbers of the processed tasks in each agent. We experimentally show that the proposed method can exhibit higher performance and adapt to the changes of requested task patterns.

本稿では、Ant Colony Optimization (ACO) を用いた VLAN 環境下における動的中継点制御のスケーラビリティの向上を報告する．今までに，VLAN 環境下における中継点を動的に制御することで，冗長パケットを削減する手法を提案されてきた．しかし，既存手法 AMPSO では VLAN 数やルータ数の増加によって探索性能が低下することがわかった．そこで，本稿ではスケーラビリティの向上を目的として新たな手法として ACO を VLAN 環境に適用させた手法を提案する．最後に，実トラフィックに基づいて作成したシミュレーション環境を用いて既存手法と比較・評価することにより，スケーラビリティの向上を示す．This paper represents a scalable method for the dynamic migration of the IP routing point in Virtual LAN environments using Ant Colony Optimization (ACO). We previously proposed the method using particle swarm optimization that can adaptively select the routing points dynamically based on the observed traffic patterns and thus reduce the redundant traffic in a VLAN environment. However, we found that method does not converge to the appropriate routing point deployment in a large-scale network environment.In this paper, we propose a novel ACO-based method to compare the scalability. We also experimentdly evaluate the proposed method using the simulation environment that can generate the traffic based on the packet flows observed in the real-world environment.

社会における人の幼児期の学習特性を模し、語彙を学習する幼児エージェントの集団での学習モデルを提案する。これまで親から子へ伝える世代学習をモデル化し、語彙の学習の過程をモデル化する研究がなされてきた。しかし、家族や周囲のコミュニティの中で影響を受けながら言語や語彙の獲得は行われる。本研究では、親から子へ伝える世代学習を基礎としながら、子同士に空間的な距離に応じた学習を行わせ、社会的な条件を加味した状況をモデル化し、その中でエージェントの語彙学習の特徴を調べる。実験の結果、単一系の世代学習に比べて言語が構造化されるまでの期間が短いことが分かった。また、直系の親や近隣の親からの影響のみで子同士の影響がないと、言語の構造化に時間がかかることも分かった。We propose a model of infant agents with the ability of generational learning in a polyphyletic group and investigate its characteristics using simulation. Infant agents are those that imitate a learning bias in infancy and learn the vocabulary in a virtual social group. Recently, a number of studies that proposed the models of an infant agent that learns the vocabulary or language with interactions between the parent and its infants/children, that is, monophyletic evolution, and evaluate them using computational simulations are conducted. Languages, however, evolve in infants with interacting with other infants in a human &#039;s social group. In our proposed model, infant agents learn languages from other infants in the same generation as well as being told by their parents in order to implement polyphyletic evolution by generational learning in the society of infant agents. We then investigate the characteristics of generational learning in a polyphyletic group by comparing those in a monophyletic group. Our experimental results shows that language learning in the polyphyletic group is more efficient.

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%.

インターネット上のサービスに対応したタスクは，それを構成する複数のサブタスクを処理することで達成される．効率的なタスク処理のためには，サブタスクを対応する能力やリソースを持つエージェントに適切に割り当てる必要がある．我々はこれまで，強化学習とネットワーク構造の再構成により，チーム編成を効率化する手法を提案してきた．しかし，そこで用いた学習は，近隣のエージェントの内部状態を既知としており，必ずしも現実のシステムと合致しない．また，実験で仮定したエージェントの配置も固定的であった．本論文では，提案手法を，他のエージェントの内部状態ではなく，近隣からのメッセージと遅延を考慮した減衰率から報酬を求め，それに基づいて Q 学習するようにモデル化する．次に，初期配置によらず，学習と組織構造の変化を組み合わせ既存手法よりも効率化できることを示す．さらに，タスクの種類の変化についても，効率的なチーム編成が可能なことを実験により評価する．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. We showed that the proposed method combines the learning for team formation and reorganization in a way that is adaptive to the environment and that it can improve the overall performance and increase the success in communication delay that may change dynamically. But the machine learning that we used there knows inside state of neighborhood agents and this cannot be assumed in real systems. We propose a method of distributed team formation that uses modified Q-learning with reward based in messages from neighborhood and communication delay. We show that it can improve the overall performance in any initial placement and in environment change of range of task.

本研究では，赤外線センサを用いたセンサネットワークのトポロジーを，センサの時系列データのみから推定するモデルを提案する．提案手法では，より確実性の高い隣接関係の推定結果を用いながら，段階的に推定する隣接関係の数を増やす手法を用いる．これにより，推定の精度を保ちながら，より多くの隣接関係を推定することを可能とする．実験では，実際の環境で収集したセンサデータを用いて提案手法を評価し，従来手法と比較して高精度・広範囲に隣接関係が推定できることを示す．This paper proposes the method for accurately estimating topology of sensor networks from time-series data obtained from infrared proximity sensors. Our proposed method is an incremental estimation methods in which the reliable adjacent-relationship results are first identified, then other relationships are gradually estimated based on the previous results. It can estimate more topology with high accuracy. We show that, using actual data gathered from real-world environments, our method can estimate the topology more accurately than the conventional methods.

&lt;p&gt;本研究では、幼児期における学習と経験を通じて語彙を獲得する過程を模した幼児エージェントモデルを拡張する。具体的には、学習情報に誤りや雑音を含む環境において語彙が獲得できることを示す。さらに、言語が世代を経るごとに構造化されていくこと、一部の学習バイアスが導出可能であることを述べる。&lt;/p&gt;

高速道路の交通流は渋滞に至る過程で、渋滞が起こり得る交通密度に至っても、交通流の流量が増加し続けるメタ安定相を経る。本研究では、渋滞の緩和と発生の遅延をめざし、視野範囲内の先行車が低速の際に車間距離をとる渋滞緩和車を提案する。これをメタ安定相を再現できる拡張 Nagel-Schreckenberg モデルに加え、マルチエージェントシミュレーションにより、渋滞解消ができることをしめす。特に、渋滞時に渋滞緩和車を複数台連続させて投入する配置が、少ない渋滞緩和車で、メタ安定相への遷移を実現できることが分かった。Even if traffic density in highway reaches the state in which congestion can happen, we can sometimes observe the phenomenon where the traffic flow still keep growing. This state is called the metastable phase. We introduce a number of traffic congestion reducers (TCRs) that take sufficient distance from the front car to ease traffic congestion. Then we investigate whether or not the congestion can be eased or resolved by adding TCRs using the extended Nagel- Schreckenberg model that can generate the metastable phase. Our results show by placing the more than two TCRs straight, the congestion can be resolve with higher probabilities.

高速道路の交通流は渋滞に至る過程で、渋滞が起こり得る交通密度に至っても、交通流の流量が増加し続けるメタ安定相を経る。本研究では、渋滞の緩和と発生の遅延をめざし、視野範囲内の先行車が低速の際に車間距離をとる渋滞緩和車を提案する。これをメタ安定相を再現できる拡張 Nagel-Schreckenberg モデルに加え、マルチエージェントシミュレーションにより、渋滞解消ができることをしめす。特に、渋滞時に渋滞緩和車を複数台連続させて投入する配置が、少ない渋滞緩和車で、メタ安定相への遷移を実現できることが分かった。Even if traffic density in highway reaches the state in which congestion can happen, we can sometimes observe the phenomenon where the traffic flow still keep growing. This state is called the metastable phase. We introduce a number of traffic congestion reducers (TCRs) that take sufficient distance from the front car to ease traffic congestion. Then we investigate whether or not the congestion can be eased or resolved by adding TCRs using the extended Nagel- Schreckenberg model that can generate the metastable phase. Our results show by placing the more than two TCRs straight, the congestion can be resolve with higher probabilities.

Due to the large number of web pages, recommendation systems that assist users to find intended information from web pages has been proposed and developed. Our goal is to develop the less onerous recommendation system from webpages of all domains for a small community at search actions in web browsing. However, we have some problems. In this paper, we propose the method for extracting search actions from browsing history, in order to find the pages that deserve for being recommended if someone in the small community begin the search actions with the same/similar search words. The result of our experiment reveals that the proposed method can extract search actions correctly with approximately 52%, and then it can find, with approximately 87%, the web pages that are appropriate for recommendation.

本論文では,任意形状のクラスタの分割を目的とした非階層的クラスタリング手法を提案し,それを他のクラスタリング手法と比較して評価した結果について述べる.現在の社会において,大量のデータから何らかの意味をもつ情報を抽出することが必要になっている.そのような現状において,クラスタリングは教師なしデータ分類の重要な一手法として用いられている.クラスタリングは情報科学だけでなく,経済学や自然科学,社会科学など様々な分野で利用されており,各分野において基礎的な部分を構成している.しかし,利用されている従来の非階層的クラスタリング手法では任意形状のクラスタの検出が難しく,また,データに含まれるノイズに対して脆弱であるなどの欠点ももつ.提案したクラスタリング手法は,グラフ構造を用いてデータ間の関係を簡略化した後,生物の同期現象をモデルとした結合振動子の自己組織化により実現する.提案手法の性能を調べるために,三つのデータセットに対してクラスタリングを行い,結果を外的評価指標を用いて評価した.評価の結果,提案手法は任意形状のクラスタ検出に高い効果を発揮した.

Due to the large number of web pages, recommendation systems that assist users to find intended information from web pages has been proposed and developed. Our goal is to develop the less onerous recommendation system from webpages of all domains for a small community at search actions in web browsing. However, we have some problems. In this paper, we propose the method for extracting search actions from browsing history, in order to find the pages that deserve for being recommended if someone in the small community begin the search actions with the same/similar search words. The result of our experiment reveals that the proposed method can extract search actions correctly with approximately 52%, and then it can find, with approximately 87%, the web pages that are appropriate for recommendation.

本稿では，Angle Modulated Particle Swarm Optimization(AMPSO) を用いた VLAN 環境下における動的中継点制御のスケーラビリティの向上を報告する．我々は今までに，VLAN 環境下における中継点を動的に制御することで，冗長パケットを削減する手法を提案してきた．しかし，既存手法では VLAN 数やルータ数の増加に従って探索性能が低下することがわかった．そこで，本稿ではスケーラビリティの向上を目的として AMPSO を VLAN 環境に適用させた手法を提案する．最後に，実トラフィックに基づいて作成したシミュレーション環境を用いて既存手法と比較・評価することにより，スケーラビリティの向上を示す．We report a improving the scalability of the dynamic migration of the IP routing points in Virtual LAN environments by angle modulated particle swarm optimization (AMPSO). We have developed the method that can adaptively select the routing points dynamically according to the observed traffic patterns and thus reduce the redundant traffic. However, we found that the developed method decrese the search performance according to the increase of the number of VLAN and router. In this paper, we will show that method using AMPSO in order to improve of scalability. Finally, we will evaluate the proposed method using the simulation environment that can generate the traffic based on the packet flows observed in the real-world environment.

多数のエージェントが多数のタスク割当を要求し,その結果が相互に影響し合う状況における交渉プロトコルの性能特性を報告し,更にその結果を利用してタスクの割当方法を動的に変更する戦略を提案する.近年のインターネットやセンサの高機能化により,複数かつ大量のエージェントが相互に協調を行う場面が想定される.しかし,このような大規模な環境で,これまで提案されてきた交渉プロトコルによるタスク割当がシステム全体の潜在能力を十分に引き出すかどうかは分からない.本論文では,まず契約ネットプロトコル(CNP)を題材として,このような状況でのCNPの特性を報告する.次に,その特性に基づき,システム全体及びシステムの局所状態の推定によって動的に変動する広報/落札戦略の提案と評価を行う.本評価実験では,単純なCNPと比較して,最大で30%程度の効率上昇がシステムの限界近くで得られることが分かった.

本論文では,センサの位置情報についての事前知識を用いずに,反応情報のみからセンサ間の隣接関係の推定法を提案する.コンピュータ機器やセンサデバイスの発展とともに様々なセンサネットワークアプリケーションが提案されてきた.これらのアプリケーションにおいて人間の行動に基づいたトポロジー情報は,人間の行動を支援するために必須のものである.しかし,大量のセンサを使用するアプリケーションにとってこの情報を手動で設定し,維持するのは簡単でない.提案手法ではAnt Colony Optimization(ACO)を用いて精度の高いトポロジーの自動推定を行う.本手法では取得したセンサデータの信頼性を推定し,ACOに適用することによって高精度化を実現する.最後に,独立した三つの環境で収集したセンサデータを用いて提案手法を評価し,従来の手法と比べすべての環境について推定誤差率がかなり向上したことを示す.

We present a method to discover contexts peculiar to a given term (a concept represented by a given term) by analyzing a document set. In our approach, first, a factor that contributes to definitions of contexts is selected. Then, the document set is organized (structured) on the basis of the factor. Finally, the distribution of term occurrence over the structured documents is analyzed. We also show some actual examples of context discovery where time, 1 year periodicity, interrelationships among people are respectively used as context factors.

We present a method to discover contexts peculiar to a given term (a concept represented by a given term) by analyzing a document set. In our approach, first, a factor that contributes to definitions of contexts is selected. Then, the document set is organized (structured) on the basis of the factor. Finally, the distribution of term occurrence over the structured documents is analyzed. We also show some actual examples of context discovery where time, 1 year periodicity, interrelationships among people are respectively used as context factors.

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 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 affect team formations of the agents. We will show that the utility and the failure of the team formation is deeply affected by depth of the tree structure.

データリンク層の仮想化技術である仮想LAN（VLAN）は，ネットワーク構成の変更を容易にし設計の自由度を増すことから，ある程度の規模を持った組織内ネットワークでは広く使われている．しかし，1つの論理的なデータリンクの範囲が広がるため，ネットワーク層でのパケット中継のトポロジとの間で不整合が発生することがある．本稿では，ネットワーク層のパケット中継点を動的に制御することにより，この不整合の問題を解消する機構について述べる．Virtual LAN (VLAN) is a useful technique for constructing the large scale enterprise network. Despite of the useful features given from the virtualization, it has possibility to cause some inefficient traffic transfer because of a mismatch between the topology of an overlaying logical network and one of an underlaying physical network. In this paper, we propose a distributed architecture to solve this problem, and evaluate the mechanism through the experiments and simulations.

We will propose the method for estimating sensor network topology only from time-series sensor data, without prior knowledge about location information of sensors. The proposed method is based on the ant colony optimization but is further improved to construct more accurate topology by estimating the reliability of acquired sensor data. Finally, we will evaluate our method using the actual sensor data.

We will propose the method for estimating sensor network topology only from time-series sensor data, without prior knowledge about location information of sensors. The proposed method is based on the ant colony optimization but is further improved to construct more accurate topology by estimating the reliability of acquired sensor data. Finally, we will evaluate our method using the actual sensor data.

The degree of co-occurrence of two terms in the same web page is recently used to measure a relevance between them. We cannot measure any kind of relevance with this method, however, since the result of a term co-occurrence analysis depends on the certain kind of term co-occurrence context defined by the document set to be analyzed. This also means that we may be able to measure a new kind of relevance by choosing an appropriate document set. In this paper, we tried a new type of term co-occurrence analysis in which bloggers are used in place of web pages. The reslut of an experiment reveals that the blogger base co-occurrence analysis can be used for recommendation services.

The degree of co-occurrence of two terms in the same web page is recently used to measure a relevance between them. We cannot measure any kind of relevance with this method, however, since the result of a term co-occurrence analysis depends on the certain kind of term co-occurrence context defined by the document set to be analyzed. This also means that we may be able to measure a new kind of relevance by choosing an appropriate document set. In this paper, we tried a new type of term co-occurrence analysis in which bloggers are used in place of web pages. The reslut of an experiment reveals that the blogger base co-occurrence analysis can be used for recommendation services.

組織内の労働者の知人関係やタスク処理量に着目した人事異動によるタスク処理の効率化を図るシミュレーションを行う。また、人事異動手法の違いによって現れる、知人関係、知人関係をたどった学習による知識継承の特徴を分析する。

In the Internet, the illegal attack packets are always falling to our network. It is very important to observe and model the those attacking traffic for constructing the protection system from the attacks. In this paper, we describe the concept of a distributed cooperative monitoring architecture, which collects attacking packets and build the model of them efficiently with the cooperation of distributed small-range of monitoring networks. We also report the result of the preliminary analysis of the collected attack traffic.

The Free Scale Network (FSN) architecture provides conventional networks with an unlimited extension capability. FSN consists of hierarchical or meshed realms. Each realm has its unique realm address. The address works as a prefix of the conventional addresses in the realm. FSN gateway interconnects them transparently by a multiple virtual space (MVS) mechanism. In MVS, a local address space is reserved for virtual addresses and an address in the space is allocated dynamically every time a host requests the gateway to resolve address of an FQDN. Thus, it enables the conventional hosts and routers to access whole the address space with no modification.

VLAN (Virtual LAN) technologies are usually used in the large-scale Intranet in the universities and the companies. Using the VLAN technology, a network segment is built on anywhere in the campus or the building. On the other hand, wide-area VLAN segment may cause inefficient network utilization under some network topology and router allocation. In this paper, we discuss the possibility of the inefficient utilization and solutions to solve the problem. We also found the occurrence of the inefficient traffic through the real traffic observation.

How human interact with environment and how environment interact with human are discussed. An important word is &quot;resonance&quot;. Each human has his own frequency, which is the metaphor of personality or habit, and behavior of human reacts environment, and environment learns his own frequency. As for environment, environment always observe human, and if there are information to inform to human, environment makes interaction to human by using his own frequency, then he resonates with the interaction from environment, and can easily and efficiently get the information from environment. In this paper, we will propose the basic framework of interaction from human to environment and environment to human, and show some result of primary experiment.

Due to the nature that a distributed IDS has to monitor the whole distributed system, the IDSes constructing a distributed IDS are scattered throughout hosts in the distributed system. In addition, each IDS is embedded into a host and a network in the distributed system. As such, the distributed IDSes are not separated from the distributed system and therefore cause a security problem. A distributed IDS can be compromised via the distributed system. In this paper, we propose a virtual distributed environment called the HyperSpector, which is separated from the rest of a distributed system. The HyperSpector consists of virtual machines called the portspaces and a VPN. The portspacc enables an IDS in it to monitor file systems, a network, and processes of servers running in the outside of it. Using the HyperSpector, a distributed IDS is protected from active attacks and damages by passive attacks are confined inside the HyperSpector.

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. However, none of the systems for the indoor environment satisfies that need yet. In this paper we propose the Proximity Mining, a novel technique 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 environmental sensors. We deal with trend curves representing time series sensor data, and use their topological characteristics to classify locations where the sensors are placed.

In this paper, we propose Organic Entia, an open architecture for real-space computing. It focuses on objects in real-space rather than information in digital (cyber) space. The key requirements for this system are ability to handle location information without pre-configuration and to implement interfaces between real-space objects and people. We also introduce a novel location model based on cells and proximity measure.

In this paper, we propose Organic Entia, an open architecture for real-space computing. It focuses on objects in real-space rather than information in digital (cyber) space. The key requirements for this system are ability to handle location information without pre-configuration and to implement interfaces between real-space objects and people. We also introduce a novel location model based on cells and proximity measure.

This paper proposes a programmable packet analyzer package that generates the realtime packet analyzers based on the rule-based analysis procedures. As recent growth of the Internet enables people to use it for the wide range of activities such as business, education and research/development, it is required to maintain/monitor the networks and the nodes (hosts/servers/routers) as well as to protect over-eager accesses, attackers, intruders and various computer virus. Responding to these requirements, a number of tools such as network and host monitors, network profilers and intruder detection systems have been proposed and used. These systems usually share a packet-based analysis component whose actions are induced by captured packets. The proposed package provides the rule-like descriptions of packet-based analysis procedures and generates the desired network analyzers/monitors from the corresponding set of rules.

This paper proposes a programmable packet analyzer package that generates the realtime packet analyzers based on the rule-based analysis procedures. As recent growth of the Internet enables people to use it for the wide range of activities such as business, education and research/development, it is required to maintain/monitor the networks and the nodes (hosts/servers/routers) as well as to protect over-eager accesses, attackers, intruders and various computer virus. Responding to these requirements, a number of tools such as network and host monitors, network profilers and intruder detection systems have been proposed and used. These systems usually share a packet-based analysis component whose actions are induced by captured packets. The proposed package provides the rule-like descriptions of packet-based analysis procedures and generates the desired network analyzers/monitors from the corresponding set of rules.

Minority game, which is the simulation program to analyze the competitive phenomena of the market economy, has been studying at macroscopic behaviors of agents. So, in our study, we will focus on the behaviors of each agent, and try to acquire a wide use coordination methodology of agents from this game.

Minority game, which is the simulation program to analyze the competitive phenomena of the market economy, has been studying at macroscopic behaviors of agents. So, in our study, we will focus on the behaviors of each agent, and try to acquire a wide use coordination methodology of agents from this game.

If the Internet is operated reliably to ensure stable access, it is important to verify whether the routing information originated from an autonomous system (AS) is correctly spread throughout the Internet as the AS intends. Because the routing information changes as it spreads, it is necessary to observe the routing information from outside the AS. Each AS is controlled by a single administrative authority based on that AS&#039;s own policy, so a cooperative distributed solution is desirable. To cope with these requirements, we have proposed a multiagent-based inter-AS diagnostic system called ENCORE, where a collection of intelligent agents are located in multiple ASs and perform collective observation and analysis. This paper describes its diagnostic model and functions by focusing on agents&#039; cooperative actions, and discusses the effectiveness and limitations of ENCORE.

We analyze efficiency of probabilistic routing algorithms in computer network. From the simulation, we found that the routing algorithm based on the number of transfered packet achieves better performance than both the random algorithms and the cooperative algorithm based on the mean queue length in the neighbor routers.

Minority game, which is the simulation program to analyze the competitive phenomena of the market economy, has been studying at macroscopic behaviors of agents. So, in our study, we will focus on the behaviors of each agent, and try to acquire a wide use coordination methodology of agents from this game.

Progress of computer network technologies and multiple channels of satellite broadcasting produce a flood of movie information, and users find it difficult to acquire information they want. To shorten the time of viewing movie information, fast-forwarding is the most popular technique. However, current fast-forwarding focuses only on increasing the speed of displaying video images and audio part is not played in many systems. In this paper, we propose a video skimming mechanism which is based on information of audio part and scene changes in video part.

自律システム()がインターネットにアドバタイズした経路情報の振舞を理解し，自組織の意図が正しく反映されて伝わっていることを検証することは重要である．この機能を実現するため，他のASからの視点で情報を収集するリフレクタモデルに基づいて，協調して動作するマルチエージェントによるAS間障害診断システムを提案する．本システムでは，各ASに観測・診断機能を持ったエージェントを配置し，他のAS中のエージェントと協調してデータを交換することにより，ネットワークの障害を検出し，その原因を解析する．This paper proposes a network diagnostic system using the reflector model to infer the dynamics of the Internet. It provides essential functions that an autonomous system (AS) can view how the routing information about the AS spread in the Internet and can diagnose anomalies. To achieve these functions, the system is constructed using agents located in multiple ASs. Each agent monitors the routing information and reports anomalies based on diagnostic knowledge. These agents can cooperate autonomously to identify problems through observation from multiple viewpoints.

In cooperative distributed problem solving, an agent has to create a plan based on its local viewpoint in a distributed manner, in order to achieve coordinated actions appropriate to global agent coherence. From lack of non-local information, the created plan often contains unnecessary tasks or does not contain important tasks thus results in inefficient coordinated inferences and inappropriate resource usages. This paper presents a learning method to cooperatively identify situation-specific rules that enable a system to have the important part of the non-local model involved in the situation and the agents&#039; states for creating an appropriate plan.

Computer network is animportant infrastructure for divers fields of human activities.Integration of computers and communications can realize efficient and effective works in universities and companies.thus low-cost and timeliness can be achieved.Since those activities,however,highly rely on networks,it is quite important to provide network services constantly,and thus network management and quick trouble shooting are strougly requived.This paper first describes an internetwork moniforing and diagnostic system,which is an actual example of cooperative and distributed problem- solving system.Then based on our experience of applying this system to internetwork,required issues for more actual uses of AI systems in network management and diagnosis are presented.

近年、TCP/IP(Transmission Control Protocol/Internet Protocol)プロトコル群をISDN上に通す、戸謂、IP-over-ISDNによって、孤立した事務所や家庭のワークステーションなどから、インターネットワーク透過的かつ高速に利用する試みが行われるようになった。ところが、多くの異なったアプローチが行われたため、方式やリンクプロトコルに互換性がなく、マルチベンダ環境での相互接続ができない。これらの互換性のない方式の混在は、従来の装置からISDN指向の装置へのスムーズな移行を不可能にしている。また、マルチベンダ環境構築の障害にもなっている。そこで、我々は、異なった複数のリングプロトコルを同時に利用できるMLP(Multiple Link Protocol)-over-ISDNプロトコルを開発中である。本論文では、そのプロトコル,及び、アーキテクチャについて説明する。

単独で解決できる問題と協調して解くべき問題が混在した分散問題を考える。問題解決では、問題解決の知識と問題の絞り込みを可能とするフォーカスが必要である。問題の混在は、その場合に応じて、知識とフォーカスが同一エイジェントまたは異なったエイジェントに存在することにより起こる。ここでは具体例としてインターネットワークの診断問題を取り上げる。ネットワークでは、障害原因があるエイジェントの管理範囲にあるにもかかわらず、障害の認知やデータの収集ができないという問題がある。一方、他のエイジェントは障害発生の可能性を推測できるが診断はできない。これは知識とフォーカスが分離した典型例である。このような問題では、障害発生を知識を持つエイジェントになるべく早く認知させ（フォーカスを与え）、全体の主導権を握ることが迅速な推論を実現する。本論文では、単純な実験を通して、単独/協調の混在の問題点を洗いだし、統一して扱える協調問題解決のコントロールを追究することにある。We consider the case that two types of distributed problems, which should be resolved autonomously or cooperatively, alternately appear. For problem-solving, knowledge for diagnosing tire problem and focus which can restrict the range of the problem are necessary. Such a mixture is caused by which knowledge and focus is in an agent or in other agents. Diagnosis of internetwork problems are examples of this kind of problems. In internetworking, the focus of the problem sometimes exists in the agent which is phycially or logically far from the network segments where the cause is. Thus, if the agent having knowledge finds that he cannot resolve it autonomously, he must contact the agent having focus as soon as possible. Through actual experiments, uniform control strategies which can treat these two types are discussed.

TCP/IPプロトコルによるインターネットワークに置ける典型的な障害例であるA Cking ACKとbroadcast stormの自動発見方法を提案する。これらの障害の真の原因を究明するためには、インターネットワークとTCP/IPプロトコルに関する深い知識を必要とし、さらに多量のデータを解析する必要があったために、かなりの時間を費やしていた。ここで提案する方法は我々の研究所における約5年以上のネットーワークの使用経験とその間に集めたデータに基づき、各障害発生時の特性を解析し、それを自動発見へ適用したものである。本方法により障害の発生が自動的に認識でき、タイムリーなデータの収集が可能となる。このため少ないデータの解析で原因の究明ができ、障害発見のための負担が大幅に削減される。本論文ではこれらの方法を裏付けるデータと、実際に適用した結果を示す。これらの発見方法はインターネットワーク監視・診断システムLODESで採用されている。We propose methods for automatic detection of ACKing ACK and broadcast storm, which are typical problems often occurring in TCP/IP-based internetworks. Isolating the causes of these problems requires knowledge of TCP/IP protocol suites with which general users are not familiar. Furthermore, it takes a long time to troubleshoot these problems because a large amount of packet data has to be analyzed. The methods proposed here are based on our more than 5 years of internetworking experiences. We identify the distinguishing characters and symptoms of these problems and apply these results to automatic problem detection. Timely packet collections as well as automatic detections are thereby available. This enables resolution of the problems by analyzing only a small amount of packet data. This paper presents actual data supporting these methods and evaluates their actual use in our network. The proposed methods are applied to the distributed knowledge-based system called LODES, which is capable of diagnosing logical problems in internetworks.

近年、ワークステーションの普及に伴い、それらをLAN(Local Area Network)で結合した分散処理システムの構築が行われるようになった。これらのシステムの特徴は、さまざまな製造メーカの装置から構成される点である。このようなマルチベンダシステムでは、通信プロトコルとして、PCからメインフレームまでサポートされているTCP/IP(Transmission Control Protocol/Internet Protocol)が、用される。最近では、このような独立したネットワークを、ルータなどのネットワーク結合装置によって接続し、全体をあたかも一つのネットワークのごとく動作させる、インターネットワークの構築も行われるようになった。インターネットワークは、膨大な数、および多種多様な要素から構成され、しかも、それらは地理的に分散している。このため、一旦、事故が発生すると、その原因の追求が極めて困難であり、解決までに長い時間を要する。これに加え、大規模ネットワークにおける複雑な問題を解決できるエキスパートが少数であるということも、問題をますます困難なものとしている。このような問題を解決するため、我々は、ネットワークを監視し、異常の発生や、その兆候を発見して、速やかに問題を解決するインターネットワーク監視・診断エキスパートシステム(Large Internetwork Observation and Diagnostic Expert System-LODES)を開発中である。本論文では、障害診断に用いられる技法とエキスパートシステムのアーキテクチャとの関係について説明する。

研究所・大学・企業等でLANで結合されたインターネットワークによるコンピュータ通信が盛んになってきた。インターネットワークは非常に有益なサービスを可能とする一方で、特に大規模なネットワークでは、多くのトラブルが発生しがちである。これらは、(1)(大規模な)ネットワークの管理の難しさ(2)計算機・インターネット・LANの知識不足(3)通信ソフトウエア・インストレーションの問題等に起因する。しかも障害が発生するとネットワークを共有している第三者に影響がおよぶばかりでなく、ゲートウエイ・ブリッジを越えて他のネットワークにも障害が伝染することもある。このようなネットワークの障害は、たとえば、通信が確立されない・転送が遅い・通信が不意に切れる、等が主な症状である。障害が発生するとその原因究明にかなりの時間と労力を要する。これらは、ネットワークが物理的にも機能的にも分散されて原因個所の同定が難しいこと、管理の分散化に伴い一人のネットワークマネージャーが障害の解消に必要な情報をすべて持っていないこと、症状の再現が難しいこと等の理由がある。たとえば、他ネットワークから伝染した障害の真の原因をつかむことは不可能に近い。しかも、問題自体がnon-monotonic、つまり、正常なネットワークに新たなホストをつけ加えて障害が発生したとしても、真の原因がそれまで一見正常に動いていたホストにあることがある。このようなインターネットワークの問題に対し、LANの状態を監視するとともに、異常が発生したとき速やかに障害の解消を行うインターネット監視・診断エキスパートシステム(Large Internetwork Observation and Diagnostic Expert System-LODES)を提案する。本システムはユーザからの申告に基づいて診断を行うばかりではなく、LANに流れているバケットを監視し、障害もしくは障害の兆候を検出し、発見された場合には診断システムが自動的に呼ばれてその原因の究明を行う。本論文では、エキスパートシステムの構成と概要および特徴を述べ、システムによる診断可能範囲を説明する。

近年、様々なエキスパートシステムの構築が試みられ、それをサポートするAIツール(知識表現システム)の試作あるいは商用化が行われている。NTT電気通信研究所においても、フレームの階層表現とProlog(以下PRIMEと呼ぶ)とを有機的に結合させた知識表現・推論環境KRINE(Knowledge Representation and INference Environment)を試作してきた。実際のシステムで、知識ベースを利用しながら推論を行うとき、適用すべきルールの候補が複数個現れることがある。このような場合、適用する前に何らかの戦略によって、ルールを一つに絞り込むことが必要である。しかし、事前に最適なルールを選び出すことは限界がある。複数個のルールを適用し、その結果を適宜比較し、最良なものを選択することが要求される。本発表では、上記のような試行錯誤を伴う推論を行うために、従来の操作取り消し機構を拡張し、その機能をKRINEに付加したことを報告する。

In this study we have studied adaptive multiagent planning formation change algorithm. Centralized type, direct coordination type, and indirect coordination type is typical formation. This time, we have mainly adopted multiagent based traffic control system as case study, and proposed multi agent based traffic light control framework for intelligent transport systems. For smooth traffic flow, real-time adaptive coordination of traffic lights is necessary, but many conventional approaches are of the centralized control type and do not have this feature. Our multi agent based control framework combines both indirect and direct coordination. Reaction to dynamic traffic flow is attained by indirect coordination, and green-wave formation, which is a systematic traffic flow control strategy involving several traffic lights, is attained by direct coordination. We show the detailed mechanism of our framework and verify its effectiveness through comparative evaluation through simulation.

We proposed the negotiation method, especially the effective task assignment method, in large-scale autonomous multi-agent systems based on contract net protocol and market-based allocation. In task assignment by the market- and bid-based approaches, agents will concentrate on a few specific "good" tasks for their selections. Thus, if the systems are large, the system’s efficiency often falls as a result. However, this performance degrade highly depends to the degree of the system’s workload. We introduced the concept of phantom tasks that are used to estimate the local workloads, and proposed the method in which agents decide their allocation strategy depending on the estimated workload

In this research, we propose a multi-points switching technology for virtualized networks. The goal of our research enables an intelligent control on exchanging IP-layer traffic over multiple routing switches in parallel. The results of our research will be a basis of the efficient controls of virtualized networking

We have developed the mechanism generators which automatically generate the mechanism that can satisfy the given conditions. Especially, we proposed component mechanisms stored in mechanism data bases and also developed the technologies of automated mechanism design which are fundamental to mechanism generators.As our research results, we presented 68 papers at international/domestic conferences and published 54 papers in international/domestic journals. We received the best student award in 2008 and the best student award runner up in 2009 at Int. Conf. on AutonomousAgents and Multiagent Systems (AAMAS), which is one of the top international conferences in the research field of multiagent systems. Furthermore, in 2008, we received the best paper award at IEEE/WIC/ACM Int. Conf. on Intelligent Agent Technology (IAT). Our paper on the automated mechanism design technologies received Funai best paper award at FIT2011, which is a major domestic conference on information technologies

We proposed the learning method in which agents produce norm in the society for effective conflict resolution and investigated the characteristics (convergence, stability, etc.) of the norm. For this purpose, we expressed conflict situations using a Markov game with a variety of payoff matrices that indicate agent's attitudes to situations and rewards as the result of behavior. We also represent the conflict situations that are never resolved unless one of agents gives up the best action (so this may result in the temporal penalty). Using our proposed method, we could find that (1) norms could emerge but its efficiency of resolution and stability is strongly affected by the payoff matrices in agents; (2) we often observed the phenomenon in which the established norms are broken by a few anomaly of agents that have strong attitude to conflicts; and finally (3) inconsistent norms often coexist in the agent network whose structure has the small-world property.

We proposed the negotiation method, especially the effective task assignment method, in large-scale autonomous multi-agent systems based on contract net protocol and market-based allocation. In task assignment by the market- and bid-based approaches, agents will concentrate on a few specific "good" tasks for their selections. Thus, if the systems are large, the system’s efficiency often falls as a result. However, this performance degrade highly depends to the degree of the system’s workload. We introduced the concept of phantom tasks that are used to estimate the local workloads, and proposed the method in which agents decide their allocation strategy depending on the estimated workload.

In this research, we propose a multi-points switching technology for virtualized networks. The goal of our research enables an intelligent control on exchanging IP-layer traffic over multiple routing switches in parallel. The results of our research will be a basis of the efficient controls of virtualized networking.

We have developed the mechanism generators which automatically generate the mechanism that can satisfy the given conditions. Especially, we proposed component mechanisms stored in mechanism data bases and also developed the technologies of automated mechanism design which are fundamental to mechanism generators.As our research results, we presented 68 papers at international/domestic conferences and published 54 papers in international/domestic journals. We received the best student award in 2008 and the best student award runner up in 2009 at Int. Conf. on AutonomousAgents and Multiagent Systems (AAMAS), which is one of the top international conferences in the research field of multiagent systems. Furthermore, in 2008, we received the best paper award at IEEE/WIC/ACM Int. Conf. on Intelligent Agent Technology (IAT). Our paper on the automated mechanism design technologies received Funai best paper award at FIT2011, which is a major domestic conference on information technologies.

In this study, we have proposed a new framework to integrate the bottom up and top down coordination of multiagent systems consisting of many autonomous agents having a local view. We have proposed the methodology in which both coordination types perform competition to make a dynamic equilibrium. We have evaluated the effectiveness of our proposal by applying this methodology to the systems of anticipating the traffic jam and controlling traffic lights of the new generation intelligent traffic control systems.

本年度は以下の3つのアプローチで研究を行った.
「観測空間相互の相関解析」では, 時間・アドレス空間のにおける攻撃パターンの相関解析を行い, 比較的小規模の監視アドレスブロック(32ホスト分)のデータから1000アドレス程度離れたアドレス空間の統計的な挙動が推定可能であることを明らかにした. 同様に, 攻撃者の平均的な攻撃速度(伝播遅延)の推定方法を確立した. また, これらの伝播速度はベースとなる監視アドレスの位置によって大きく変化することを明らかにした. これらの結果は分散協調観測の際の監視アドレス配置を決定する上での重要な指針である.
「断片Darknet用パケット収集ブリッジ」は実ネットワークにおける各種サービスの利用と攻撃情報の収集を並立させることを目指した基盤技術である. 実トラフィックの流れを監視・制御しつつDarknetを実現するブリッジを実現したことにより, 分散協調のポリシに基づいた観測アドレス空間の変更を容易に行うことが可能となり, さらにネットワークの利用状況に応じた柔軟な攻撃情報の収集が可能となった. 「アドレス空間の変更による自律防衛基盤」では, サービス提供用に公開しているアドレスを動的に入れ替えながら運用を行うことが可能なアーキテクチャを提案・実装した. サービスを提供するサーバに対する攻撃を抑制(抑制率 : 18-60%)するとともに, 攻撃性のトラフィックを効率的に収集することが可能となった.

The IPv4++ is an IPv4 compatible protocol. Unlike IPv4, it provides unlimited number of addresses by a multiple virtual address space technique. The IPv4++ network is a collection of IPv4 network called realm and realms are connected each other via DAT(Dynamic Address Translator). IPv4++ assumes that the realms form a tree structure and each realm has a unique local IPv4 address within its upper realm. Each realm has a unique IPv4++ address formed by concatenating its local IPv4 addresses from the leaf to the root. In a realm, DAT allocates a virtual IPv4 address for an external destination host on-demand. Because of the access locality, only a small number of IP addresses are required to access whole the lPv4++ address space. Thus, DAT provides access transparency between any realms.
Our activities in the fiscal year of 2006 and 2007 are follows ;
1. We found that the concept of a tree structured realm make it easy to explain the IPv4++ network architecture. It is named Free Scale Network Architecture because of the unlimited address space expansion capability provided by DAT.
2. For the mission-critical use, we found that a backup routing function is indispensable. It is provided by inter-DAT protocol named RGP(Realm Gateway Protocol). RGP adopts TPV(Temporal Path Vector) algorithm to accelerate the route convergence. RGP is upward compatible with the conventional BGP(Border Gateway Protocol).
3. We came to the conclusion that POC(Proof of Concept) is indispensable for the marketing prior to standardize the IPv4++ protocol. Thus, we focused on developing POC rather than writing its protocol documents.
4. Although we focused on implementing POC within these fiscal years, we have not completed it yet. We believe that it will take a couple of months to complete it.

This research aims to evaluate the market-based fair and efficient protocol, in order to apply it to the allocations of networked resources for its future applications to this domain. In ad hoc networks used in P2P and the decentralized sensor network, for example, individual nodes are owned by different persons and designed based different specifications. In this case, it is necessary to consider the incentives, that is, reward, to transmit data to each node appropriately. The auction protocol is often used for the decision of this reward. However, by using the fake (false-name) node or by conspiring with other nodes, a certain node can acquire the reward illegally in conventional protocols. We theoretically showed that this type of illegal behaviors cannot be prevented even in Vickrey-Clarke-Groves protocol (VCG) in the research period by this grant.
We then proposed Reserve-Cost protocol (RC), which is the extension of VCG by introducing the penalty proportional to the number of agents (nodes) who manage the network route. We also clarified that the RC is false-name proof, that is, the fairness of RC protocol is not influenced by the false-name bids. In addition, we also showed that RC is more efficient than VCG about 60-80% by small-scale network simulation.
Moreover, it is necessary for agents to decide, by using some protocols such as auctions, where to receive/send data based on locally available information in an actual network. This corresponds to the selection of an awarder to some degree when multiple bidding agents (this corresponds to servers in this case) are identified as the appropriate for awarders.
In this research, we investigated and analyzed the phenomenon occurring when such a resource allocation protocol was used in a large-scale multi-agent system such as network.
In this type of systems, many demands like the resource allocation on the network occurs simultaneously from many different agents independently, thus the entire efficiency falls down. We also identified that a little bit of fluctuation can significantly improved the entire performance by avoiding concentration.

本研究では、高度な推論や直接の情報交換を最小限に抑えながらも適切な分業を創発させ、効率性を狙うことにある。本期間では、提案してきたアルゴリズムについて、(1) 環境に障害物、特に複雑な形状の障害物を含むときの影響、(2) 通信可能範囲に制限を導入したときの分業創発への影響を調査した。課題(1)では、おおむね分業は進むが、到達に時間がかかる場所が発生し、収束が遅くなる課題が見つかった[3]。課題(2)では、通信範囲を限定しても性能に大きな低下は発生しないが、頻繁に作業すべき地点が通信不可能であるとその影響を受け、効率の低下が観測された [1]。これらは新しい知見として、今後の研究課題とする。

本研究では、自律的な主体であるエージェントが、他のエージェント達との共同作業を通じて作業効率や受託率などを一般化した信頼度と呼ぶ尺度で結びつきを表現し、そのエージェント社会全体の構造を活用して共同作業を促進させる基本メカニズムを発見することが目的である。本期間では、分散環境でのタスク割当を抽象的に表したチーム編成ゲームを提案した。提案ゲームを繰り返し、実際に安定したチームを構成する学習手法を提案し、またその結果競合が減少し、自然な協調グループが構成され、ゲーム効率が向上した。特に、合理的行動の他に、人間社会で見られる互恵行動を導入することが重要であることが分かった。

本研究の目的は、適切な作業分担をエージェント自らの能力に応じて学習させること、さらに複数の作業分担法とエージェントの組織化を融合し、全体の効率を向上させることである。学術的にも、能力に応じて自ら作業分担範囲を決める研究はなく、新たな知見を得られる。本期間では、複数エージェント作業の分割に加えて、環境の学習を同時行う手法を提案した。新たな知見として、(1)比較的単純な環境ではイベント発生を既知とした場合と同等の効率を達成できる、(2)複雑な環境ではイベント発生を既知としたよりも高い効率を達成できる、を得た。後者は、学習による異なる環境のモデル化により自然な分業によるものと分かった。

　　本研究の目的は、マルチエージェントシステムの基本問題であるタスク割当問題をチーム編成問題と捉え、チーム形成の成否と報酬配分によるフィードバックをチーム編成ゲームとして抽象化・提案し、ゲーム効率化に必要なメカニズムを解明することにある。このゲームは、繰返しn人最後通牒ゲームに類似し、経済学・生物学・社会科学等の知見を計算機のアルゴリズムとして反映し、それを実現する。本期間で、タスクの処理のためのチーム編成提案を高い確率で受託するエージェントを学習し、それらと仮想的な協同を組むこと、チームはその協同体を中心に組むことでその成功率の格段の向上が可能なことを実験により確認した。

本研究では、ロボットなどの自律的な主体が、工場や深夜の公共の場でなどの広い領域の清掃、広範囲の警備や監視などを複数で協調しながら作業を行う際に、自律的かつ適切に作業範囲を分割する学習手法の研究を目的としている。これまで、複数エージェント（ロボットの行動決定制御ソフトウェア）の協調作業のために、領域を分割して、それぞれが担当する領域を清掃あるいは監視するなどの手法がとられてきた。この領域分割については、予め人手で分割し領域情報を与える、それぞれの能力は同等として自動分割する、などの手法がある。これらの分割は、基本的には面積の等分割を目指しているが、実際の応用を考えると、これらの事前知識や仮定は必ずしも望ましくない。たとえば、ロボットには移動速度、サイズ、バッテリー容量（連続稼働時間）、巡回アルゴリズムなどの差が、一方環境には起伏や障害物、（清掃では汚れやすさ、警備ではセキュリティレベルに基づく）要求される巡回頻度の差を考慮する必要がある。本研究では、これらの差を反映でき、しかもエージェント自ら自律的に決定する領域分割方法を提案する。　本研究提案期間において、複数ロボットによる清掃問題において、エージェントの巡回アルゴリズム、環境の汚れやすさを反映する手法を提案した。具体的には、作業の余力を表す値を計算し、それに基づいてある戦略に基づいて担当領域を拡大する（担当領域拡大戦略と呼ぶ）。この拡大行動の後に近隣のエージェントに拡大した領域を近隣に通知するが、その領域に競合がある（つまり重なりがある）場合、その余力に基づいて、その範囲を決定する。これにより、各種差を反映した分割が可能となることを示した。また本結果を、国内研究会および国際会議で発表を行った。　本研究のさらなる課題も多数ある。たとえば、環境の学習（清掃問題の場合）、各種パラメータの自律的設定がある。また、提案手法では、障害物やロボットの物理的能力（サイズ、移動速度）も反映できるはずではあるが、その実験は時間の関係で行っていない。これらの課題を今後の研究方針とする。

　本研究課題では、 Bio-Inspiredアルゴリズムの一つである群知能(swarm intelligence)の手法を活用し、L3スイッチを使用しVLAN運用をしているネットワーク環境において、利用者の使用履歴に応じ自律的にL3スイッチングの配置を決め、冗長なトラフィックの削減を実現するアルゴリズムを提案する。特に利用者の組織的移動に応じて論理トポロジを適切に自動変化させ、やや長期的な変動に対する適応化をねらう。学術面では新たな群知能アルゴリズムとその可能性を見いだし、ネットワークの運用、特にトポロジやトラフィック管理を中心とする基本的なアルゴリズムの礎を築くことが目的である。　　本研究では、(1) VLANの導入によりL2 (データリンク)ネットワークの結びつきを点ではなく面としてとらえること（L2ネットワークの接続モデル）、(2) 連続問題に多く活用されているPSOのアルゴリズムを離散問題に拡張すること、(3) PSOのアルゴリズム分散化、多点で実行しそれを統合するアプローチを取った。　　具体的には、(1)については、論文[1]においてそのモデルと一学習手法を提案している。また、(2) および(3)については論文[2]および投稿中の論文（報告時点では投稿のみであるため成果発表には未記載）において、PSO (particle swarm optimization, 粒子群モデルによる最適化)により動的にルーティングポイントを配置する手法、および分散化と粒子群モデルの改良により大きなネットワークでも動作可能なスケーラビリティのある手法を提案した。

近年のインターネットやセンサーの高機能化などにより，複数かつ大量のエージェントが相互に協調を行う場面が想定される．たとえば，インターネット上の電子商取引では，商品の提示，顧客管理，在庫管理，配送，決済処理などの異なるエージェントが協調して実現されている．特に，人気のある商品を扱うサーバでは，その負荷が問題となる．また，サプライチェーン管理，グリッド（特にPCグリッドやエージェントグリッドでは，適切なタスクを適切な計算機に割当て，全体として効率の高い処理を実現することが求められる．このような状況は今後とも進行し，広域に配置された非常に多数のPCが相互に競争あるいは協調しながら処理を進める大規模マルチエージェントシステムの研究が必須となる．このような多数のエージェント群が全体として効率的な処理を行うためには，個々のタスクを適切なエージェントに割り当てる必要がある．このような観点から，マルチエージェントシステムでは，交渉プロトコルによるタスク・資源割当ての研究が行われきた．たとえば契約ネットプロトコル(Contract NetProtocol, 以下CNP)の研究が分散AI研究の初期からなされ，その改良や，情報経済学の観点からもオークションの研究などがある．しかし工学的な観点から，特に大規模なシステムに適用した場合，その処理効率を十分にあげることができるのかは不明である．そこで我々はCNPにおいて，タスクが単純な構造を持つという仮定のもと，エージェントが自ら動的に広報および落札戦略を確率的に選択する手法を提案し，その評価を行なってきた．本研究では，本理論の適用範囲を広げるため，タスクの構造をより一般的なものとし，そこでタスクの負荷に応じた落札戦略の選択とその効果について調べた．さらに負荷情報は直接得られないので，それを間接的に推定する手法を提案し，合わせてその効率化の度合いを調べた．概ね20%以上の効率化が実現できる可能性があることが分かった．

　　近年、インターネット、センサーネットワーク、Grid Computingなど多数の計算機がネットワークに接続され、そこで動くソフトウェア（エージェント）が相互に協調・調整・競争することで、質の高いサービスを提供することが提案されている。たとえば、電子商取引では、商品の提示から、契約の受付、在庫管理、顧客管理、配送管理、決済、認証といった異なる役割を持つエージェントが連携しなくてはならない。当然、これらのエージェントは多数存在し、多数の要求を受け付けている。しかし、インターネットのように全体を管理することも、また全体の情報を収集することもできない環境では、それぞれのエージェントが局所的な情報を元に「最適」と判断する戦略で必要なタスクを依頼しなくてはならない。　　このような状況のもと、本研究の目的は、インターネットのサービスのように非常に多数のソフトウェアエージェントが相互に影響しあいながら活動する状況において、各コンピュータの能力を最大限に引き出すためにタスクを適切に配分するプロトコルを提案することにある。特に、本研究提案では、我々がこれまで提案してきた契約ネットプロトコルの制御方式に関して、それ以外の制御方式を採用してタスクを依頼したときの影響を調べることにある。　　本研究期間では、(1) 上記の研究のためのシミュレーション環境を構築すること、(2) 提案したプロトコルと通常の契約ネットプロトコルをそれぞれ採用するエージェントの比率をから、その特徴を解析した。その結果、多くの場合、提案プロトコルを採用したエージェントの方が利得が高い（処理能力が高くなる）が、契約ネットプロトコルを採用しているエージェントが少数の場合には、その少数のエージェントの方が高い利得を得ることが分かった。ただし、全体の処理能力の低下には結びつかないことも分かった。　　　　

　　インターネットを活用した自動取引や各種グリッド、ＣＰＵを内包するセンサーによるユビキタス・センサーネットワーク、広域分散システムの資源割当てなど、大量の計算機上で自律的に動作するソフトウェアが効率の面で互いに影響し合う状況で、効果的な動作を実現するためには、適切なタスク割当てが必要である。本研究では、大規模なマルチエージェントシステムに向けて、スケーラビリティを考慮した交渉プロトコル (タスク・資源割当てプロトコル）を提案することを目的とする。　　これまで交渉プロトコルの研究は、非常に空いたシステムで小規模なものを想定している。これを大規模なものに適用した場合、明らかにスケーラビリティに問題があるが、それ以前に、大規模に適用したときの性能の性質や各エージェントの振舞いの特性も分かっていない。本特定課題研究の目的は、代表的な交渉プロトコルである契約ネット(CNP)を対象に、相互に干渉する有限な能力や容量(たとえばCPU資源の割当てや予算が限定された電子商取引など)を対象とした交渉に着目し、特に、多数のエージェントが介在する環境での個々の振舞いと、系全体の効率およびそれらの特性について解析する。　　本研究期間では、CNPの広報戦略と落札戦略に着目しそれらの戦略の差と全体の効率の関係をシミュレーションにより求めた。本実験では、広報の範囲を狭めると能力の高いエージェントにタスクの通知が行かず、全体の効率が落ちる懸念があった。しかし、大規模なシステムでは、むしろ広報範囲を狭めた方が全体としての平均効率が上がることが分かった。　　また、落札戦略についても、常に一番高い値を入札したものではなく、ある程度の揺らぎを加え、２番手、3番手のエージェントを選択しタスクを割り当てる戦略が全体の効率を著しく上げることが分かった。この揺らぎの度合いとシステムの負荷には大きな関連性があり、これらをうまく調整することで、システム全体の潜在能力を引き出す交渉プロトコルへの手がかりが分かってきた。