This work deals with an artificial intelligence problematics in real-time computer games. Goal of this project is a creation of an intelligent computer opponent in a real-time enviroment of a multiagent systems.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第20028号 / 情博第623号 / 新制||情||108(附属図書館) / 33124 / 京都大学大学院情報学研究科社会情報学専攻 / (主査)教授 石田 亨, 教授 多々納 裕一, 教授 山本 章博 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

An issue with learning effective policies in multi-agent adversarial games is that the size of the search space can be prohibitively large when the actions of both teammates and opponents are considered simultaneously. Opponent modeling, predicting an opponent’s actions in advance of execution, is one approach for selecting actions in adversarial settings, but it is often performed in an ad hoc way. In this dissertation, we introduce several methods for using opponent modeling, in the form of predictions about the players’ physical movements, to learn team policies. To explore the problem of decision-making in multi-agent adversarial scenarios, we use our approach for both offline play generation and real-time team response in the Rush 2008 American football simulator. Simultaneously predicting the movement trajectories, future reward, and play strategies of multiple players in real-time is a daunting task but we illustrate how it is possible to divide and conquer this problem with an assortment of data-driven models. By leveraging spatio-temporal traces of player movements, we learn discriminative models of defensive play for opponent modeling. With the reward information from previous play matchups, we use a modified version of UCT (Upper Conference Bounds applied to Trees) to create new offensive plays and to learn play repairs to counter predicted opponent actions. iii In team games, players must coordinate effectively to accomplish tasks while foiling their opponents either in a preplanned or emergent manner. An effective team policy must generate the necessary coordination, yet considering all possibilities for creating coordinating subgroups is computationally infeasible. Automatically identifying and preserving the coordination between key subgroups of teammates can make search more productive by pruning policies that disrupt these relationships. We demonstrate that combining opponent modeling with automatic subgroup identification can be used to create team policies with a higher average yardage than either the baseline game or domain-specific heuristics.

Designing a system of multiple, heterogeneous agents that cooperate to achieve a common goal is a difficult task, but it is also a common real-world problem. Multiagent learning addresses this problem by training the team to cooperate through a learning algorithm. However, most traditional approaches treat multiagent learning as a combination of multiple single-agent learning problems. This perspective leads to many inefficiencies in learning such as the problem of reinvention, whereby fundamental skills and policies that all agents should possess must be rediscovered independently for each team member. For example, in soccer, all the players know how to pass and kick the ball, but a traditional algorithm has no way to share such vital information because it has no way to relate the policies of agents to each other. In this dissertation a new approach to multiagent learning that seeks to address these issues is presented. This approach, called multiagent HyperNEAT, represents teams as a pattern of policies rather than individual agents. The main idea is that an agent’s location within a canonical team layout (such as a soccer team at the start of a game) tends to dictate its role within that team, called the policy geometry. For example, as soccer positions move from goal to center they become more offensive and less defensive, a concept that is compactly represented as a pattern. iii The first major contribution of this dissertation is a new method for evolving neural network controllers called HyperNEAT, which forms the foundation of the second contribution and primary focus of this work, multiagent HyperNEAT. Multiagent learning in this dissertation is investigated in predator-prey, room-clearing, and patrol domains, providing a real-world context for the approach. Interestingly, because the teams in multiagent HyperNEAT are represented as patterns they can scale up to an infinite number of multiagent policies that can be sampled from the policy geometry as needed. Thus the third contribution is a method for teams trained with multiagent HyperNEAT to dynamically scale their size without further learning. Fourth, the capabilities to both learn and scale in multiagent HyperNEAT are compared to the traditional multiagent SARSA(λ) approach in a comprehensive study. The fifth contribution is a method for efficiently learning and encoding multiple policies for each agent on a team to facilitate learning in multi-task domains. Finally, because there is significant interest in practical applications of multiagent learning, multiagent HyperNEAT is tested in a real-world military patrolling application with actual Khepera III robots. The ultimate goal is to provide a new perspective on multiagent learning and to demonstrate the practical benefits of training heterogeneous, scalable multiagent teams through generative encoding.

Canonical problems are simplified representations of a class of real world problems. They allow researchers to compare algorithms in a standard setting which captures the most important challenges of the real world problems being modeled. In this dissertation, we focus on negotiating a collaboration in space and time, a problem with many important real world applications. Although technically a multi-issue negotiation, we show that the problem can not be represented in a satisfactory manner by previous models. We propose the "Children in the Rectangular Forest" (CRF) model as a possible canonical problem for negotiating spatio-temporal collaboration. In the CRF problem, two embodied agents are negotiating the synchronization of their movement for a portion of the path from their respective sources to destinations. The negotiation setting is zero initial knowledge and it happens in physical time. As equilibrium strategies are not practically possible, we are interested in strategies with bounded rationality, which achieve good performance in a wide range of practical negotiation scenarios. We design a number of negotiation protocols to allow agents to exchange their offers. The simple negotiation protocol can be enhanced by schemes in which the agents add additional information of the negotiation flow to aid the negotiation partner in offer formation. Naturally, the performance of a strategy is dependent on the strategy of the opponent and the iii characteristics of the scenario. Thus we develop a set of metrics for the negotiation scenario which formalizes our intuition of collaborative scenarios (where the agents’ interests are closely aligned) versus competitive scenarios (where the gain of the utility for one agent is paid off with a loss of utility for the other agent). Finally, we further investigate the sophisticated strategies which allow agents to learn the opponents while negotiating. We find strategies can be augmented by collaborativeness analysis: the approximate collaborativeness metric can be used to cut short the negotiation. Then, we discover an approach to model the opponent through Bayesian learning. We assume the agents do not disclose their information voluntarily: the learning needs to rely on the study of the offers exchanged during normal negotiation. At last, we explore a setting where the agents are able to perform physical action (movement) while the negotiation is ongoing. We formalize a method to represent and update the beliefs about the valuation function, the current state of negotiation and strategy of the opponent agent using a particle filter. By exploring a number of different negotiation protocols and several peer-to-peer negotiation based strategies, we claim that the CRF problem captures the main challenges of the real world problems while allows us to simplify away some of the computationally demanding but semantically marginal features of real world problems.

Embodied agents are agents acting in the physical world, such as persons, robots, unmanned air or ground vehicles and so on. These types of agents are subject to spatio-temporal constraints, which do not exist for agents acting in a virtual environment. The movement of embodied agents is limited by obstacles and maximum velocity, while their communication is limited by the transmission range of their wireless devices. This dissertation presents contributions to the techniques of coalition formation and teamwork coordination for embodied agents. We considered embodied agents in three different settings, each of them representative of a class of practical applications. First, we study coalition formation in the one dimensional world of vehicles driving on a highway. We assume that vehicles can communicate over short distances and carry agents which can advise the driver on convoy formation decisions. We introduce techniques which allow vehicles to influence the speed of the convoys, and show that this yields convoys which have a higher utility for the participating vehicles. Second, we address the problem of coalition formation in the two dimensional world. The application we consider is a disaster response scenario. The agents are forming coalitions through a multi-issue negotiation with spatio-temporal components where the coalitions maintain a set of commitments towards participating agents. Finally, we discuss a scenario where embodied agents form coalitions to optimally address dynamic, non-deterministic, spatio-temporal tasks. The application we consider is firefighters acting in a disaster struck city.

As agents are built for ever more complex environments, methods that consider the uncertainty in the system have strong advantages. This uncertainty is common in domains such as robot navigation, medical diagnosis and treatment, inventory management, sensor networks and e-commerce. When a single decision maker is present, the partially observable Markov decision process (POMDP) model is a popular and powerful choice. When choices are made in a decentralized manner by a set of decision makers, the problem can be modeled as a decentralized partially observable Markov decision process (DEC-POMDP). While POMDPs and DEC-POMDPs offer rich frameworks for sequential decision making under uncertainty, the computational complexity of each model presents an important research challenge. As a way to address this high complexity, this thesis develops several solution methods based on utilizing domain structure, memory-bounded representations and sampling. These approaches address some of the major bottlenecks for decision-making in real-world uncertain systems. The methods include a more efficient optimal algorithm for DEC-POMDPs as well as scalable approximate algorithms for POMDPs and DEC-POMDPs. Key contributions include optimizing compact representations as well as automatic structure extraction and exploitation. These approaches increase the scalability of algorithms, while also increasing their solution quality.

No description available.

Discontinuous dynamical systems and multiagent systems are encountered in numerous engineering applications. This dissertation develops stability and dissipativity of nonlinear dynamical systems with discontinuous right-hand sides, optimality of discontinuous feed-back controllers for Filippov dynamical systems, almost consensus protocols for multiagent systems with innaccurate sensor measurements, and adaptive estimation algorithms using multiagent network identifiers. In particular, we present stability results for discontinuous dynamical systems using nonsmooth Lyapunov theory. Then, we develop a constructive feedback control law for discontinuous dynamical systems based on the existence of a nonsmooth control Lyapunov function de fined in the sense of generalized Clarke gradients and set-valued Lie derivatives. Furthermore, we develop dissipativity notions and extended Kalman-Yakubovich-Popov conditions and apply these results to develop feedback interconnection stability results for discontinuous systems. In addition, we derive guaranteed gain, sector, and disk margins for nonlinear optimal and inverse optimal discontinuous feedback regulators that minimize a nonlinear-nonquadratic performance functional for Filippov dynamical systems. Then, we provide connections between dissipativity and optimality of nonlinear discontinuous controllers for Filippov dynamical systems. Furthermore, we address the consensus problem for a group of agent robots with uncertain interagent measurement data, and show that the agents reach an almost consensus state and converge to a set centered at the centroid of agents initial locations. Finally, we develop an adaptive estimation framework predicated on multiagent network identifiers with undirected and directed graph topologies that identifies the system state and plant parameters online.

We present a motion control framework which allows a group of robots to work together to decide upon their motions by minimizing a collective cost without any central computing component or any one agent performing a large portion of the computation. When developing distributed control algorithms, care must be taken to respect the limited computational capacity of each agent as well as respect the information and communication constraints of the network. To address these issues, we develop a distributed, behavior-based model predictive control (MPC) framework which alleviates the computational difficulties present in many distributed MPC frameworks, while respecting the communication and information constraints of the network. In developing the multi-agent control framework, we make three contributions. First, we develop a distributed optimization technique which respects the dynamic communication restraints of the network, converges to a collective minimum of the cost, and has transients suitable for robot motion control. Second, we develop a behavior-based MPC framework to control the motion of a single-agent and apply the framework to robot navigation. The third contribution is to combine the concepts of distributed optimization and behavior-based MPC to develop the mentioned multi-agent behavior-based MPC algorithm suitable for multi-robot motion control.