京都大学 / 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.

Actualmente existe una creciente demanda de sistemas flexibles, adaptables y con gran escalabilidad para apoyar las interacciones de personas e instituciones distribuidas en entornos heterogéneos. Esto se debe principalmente al incremento en la necesidad de trabajo colaborativo y la descentralización de los procesos en muchos dominios de aplicación. Por lo general, estas aplicaciones de software deben seguir legislaciones y normativas específicas, es decir, las entidades que participan en el sistema tienen derechos, deberes y restricciones específicas. Al igual que en otros trabajos del área, en esta tesis se utiliza el término sistemas normativos abiertos para referirse a los sistemas de este tipo. El desarrollo de sistemas normativos abiertos puede producir importantes beneficios para las compañías que los usen, ya que permiten la comunicación de instituciones, entidades heterogéneas y diferentes dispositivos con el fin de lograr tanto los objetivos globales del sistema como los individuales de cada institución y entidad. Sin embargo, también hay algunas cuestiones importantes que potencialmente pueden complicar el análisis, diseño e implementación de estos sistemas. La mayoría de estos problemas están relacionados con la interoperabilidad de sus procesos, la privacidad, la combinación de los objetivos individuales y la combinación de las restricciones y la legislación de cada una de las entidades del sistema. Por lo tanto, es necesario el uso de métodos de ingeniería del software y herramientas de desarrollo para hacer frente a estos problemas y guiar a los desarrolladores durante el proceso de desarrollo. La tecnología basada en sistemas multiagente (SMA) es considerada una buena candidata para el desarrollo de sistemas normativos abiertos. Durante los últimos años, el uso de las tecnologías SMA se ha incrementado no sólo en el ámbito académico, sino también en el desarrollo e implementación de aplicaciones industriales. Los SMA se han establecido como un paradigma de la ingeniería de software para la creación de sistemas adaptativos complejos, en entornos distribuidos y heterogéneos. Esta tesis se centra en el análisis y diseño de sistemas normativos abiertos utilizando la tecnología SMA. Algunas metodologías SMA se dedican al desarrollo de sistemas de este tipo. Sin embargo, después de analizar en qué medida las metodologías SMA actuales soportan el análisis y el diseño de estos sistemas, podemos concluir que todavía hay importantes problemas a resolver en el área. Algunos de estos problemas son la integración del contexto normativo del sistema durante el proceso de desarrollo, la falta de directrices para identificar y formalizar este contexto normativo, la falta de técnicas de validación y verificación que garanticen la coherencia del diseño final respecto a los requisitos del sistema, la coherencia entre los objetivos individuales, y la coherencia de las restricciones de cada entidad respecto al contexto normativo del sistema global. La principal aportación de esta tesis es una nueva metodología SMA llamada ROMAS (Sistemas Multiagente Regulados y Abiertos), que se centra en el análisis y diseño de procesos para el desarrollo de sistemas multiagente organizacionales, donde los agentes interactúan por medio de servicios estándares, y donde las relaciones sociales y contractuales se formalizan mediante normas y contratos. La metodología ROMAS define un proceso de desarrollo orientado a agentes y proporciona guías específicas para identificar y formalizar el marco normativo del sistema, así como las comunicaciones y los intercambios de servicios y recursos. ROMAS especifica tanto el comportamiento global del sistema como las características individuales de cada entidad. En la metodología ROMAS, agentes, roles y organizaciones se definen a través de una estructura social formal basada en un arquitectura orientada a servicios. Aquí, las organizaciones representan un conjunto de personas e instituciones que tienen que coor / Garcia Marques, ME. (2013). Engineering Regulated Open Multiagent Systems [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/28588

<p dir="ltr">Small molecule structural elucidation of unknown compounds using tandem mass spectrometry (MS/MS) is a significant challenge due to the need for expert interpretation or the use of peak matching software. These methods are time-consuming or constrained by the available molecular entries in databases. To address these limitations, we introduce a machine learning (ML) framework designed to predict functional groups from MS/MS spectra without requiring database searches. The ML models were trained using data from the Mass Bank of North America (MONA) and a custom MS/MS database generated using a high-throughput desorption electrospray ionization (DESI) MS/MS platform. This approach showcases the transferability of model predictions across different instruments, independent of the acquisition method. Our models achieved an average molecular F1 score of 87% for MONA data and 76% for data generated with DESI, with corresponding molecular accuracies of 94% and 87%, respectively. These results demonstrate the robustness of the ML framework across diverse datasets and confirm its validity in predicting structural information.</p><p dir="ltr">To further validate the robustness of our machine learning framework, the models were rigorously tested on blind datasets from independent sources, specifically provided by Corteva Agriscience and Merck & Co., Inc. These datasets were entirely separate from those used in training and validation, ensuring no prior exposure during model development. The blind datasets included spectra generated using a different instrument and a different ionization method—specifically, electrospray ionization (ESI)—which contrasts with the desorption electrospray ionization (DESI) method used to generate the custom MS/MS database for model training one of the models. When tested on this new, unseen data, the model trained on the MONA database, which also contains ESI spectra, achieved an average molecular F1 score of 80% with an accuracy of 88%. The model trained on DESI-generated data performed comparably well, achieving an average molecular F1 score of 78% with an accuracy of 85%. These findings emphasize the practical applicability of the ML framework for mass spectrometry in real-world scenarios, where diverse data sources, instruments, and ionization methods are commonly encountered.</p><p dir="ltr">In an alternate example, lipidomics – the comprehensive study of lipids in a biological system – heavily relies on tandem MS experiments. In particular, multiple reaction monitoring (MRM) profiling has gained considerable attention in MS-based lipidomics, as it can be particularly advantageous for the rapid screening of lipids in biological samples. While effective, the large amounts of data generated from lipidomic MRM-profiling workflows can be daunting. Moreover, existing software tools for lipid annotation often lack comprehensive automated workflows and integration with statistical and bioinformatics platforms. To address these challenges, we developed the Comprehensive Lipidomic Automated Workflow (CLAW) platform, which includes end-to-end modules for worklist generation, lipid annotation, parsing, statistical analysis, and bioinformatic analysis. In particular, CLAW is designed specifically for MRM-profiling, including isomer-specific MRM profiling conducted utilizing ozone electrospray ionization (OzESI), affording lipid species annotation at the carbon-carbon double bond (C=C) level. Notably, CLAW represents a first of its kind platform with integrated AI agents. Importantly, by utilizing a developed integrated language user interface (LUI) with large language models (LLMs), users can interact with CLAW via a chatbot terminal. Specifically, AI agents use LLMs to interpret human language and interact with the various tools and functionalities provided by the CLAW framework, offering robust and context-aware assistance, marking the first end-to-end application of an AI agent in mass spectrometry lipidomics. This innovation represents a significant step forward in automating complex workflows and making advanced analytical tools more accessible to researchers, ultimately accelerating scientific discovery in the field. In short, this AI-driven interface allows users to perform complex statistical analyses more efficiently, positioning CLAW as a powerful tool for high-throughput lipidomics analysis. Successful applications of CLAW to a broad range of biological samples afforded unprecedented insights to disease pathogenesis, including neurodegenerative diseases like Alzheimer's disease.</p>

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.