In the simulation of human crowd behavior including evacuation planning, transportation management, and safety engineering in architecture design, the development of pedestrian model for higher behavior fidelity is an important task. To construct plausible facsimiles of real crowd movements, simulations should exhibit human behaviors for navigation, pedestrian decision-making, and social behaviors such as grouping and crowding. The research field is quite mature in some sense, with a large number of approaches that have been proposed to path finding, collision avoidance, and visually pleasing steering behaviors of virtual humans. However, there is still a clear disparity between the variety of approaches and the quality of crowd behaviors in simulations. Many social science field studies inform us that crowds are typically composed of multiple social groups (James, 1953; Coleman and James, 1961; Aveni, 1977). These observations indicate that one component of the complexity of crowd dynamics emerges from the presence of various patterns of social interactions within small groups that make up the crowd. Hence, realism in a crowd simulation may be enhanced when virtual characters are organized in multiple social groups, and exhibit human-like coordination behaviors. Motivated by the need for modeling groups in a crowd, we present a multi-agent model for large crowd simulations that incorporates socially plausible group behaviors. A computational model for multi-agent coordination and interaction informed by well- established Common Ground theory (Clark, 1996; Clark and Brennan, 1991) is proposed. In our approach, the task of navigation in a group is viewed as performing a joint activity which requires maintaining a state of common ground among group members regarding walking strategies and route choices. That is, group members communicate with, and adapt their behaviors to each other in order to maintain group cohesiveness while walking. In the course of interaction, an agent may present gestures or other behavioral cues according to its communicative purpose. It also considers the spatiotemporal conditions of the agent-group's environment in which the agent interacts when selecting a kind of motions. With the incorporation of our agent model, we provide a unified framework for crowd simulation and animation which accommodates high-level socially-aware behavioral realism of animated characters. The communicative purpose and motion selection of agents are consistently carried through from simulation to animation, and a resulted sequence of animated character behaviors forms not merely a chain of reactive or random gestures but a socially meaningful interactions. We conducted several experiments in order to investigate the impact of our social group interaction model in crowd simulation and animation. By showing that group communicative behaviors have a substantial influence on the overall distribution of a crowd, we demonstrate the importance of incorporating a model of social group interaction into multi-agent simulations of large crowd behaviors. With a series of perceptual user studies, we show that our model produces more believable behaviors of animated characters from the viewpoint of human observers. / Ph. D.

Tesis por compendio / [EN] Automated planning is a centralized process in which a single planning entity, or agent, synthesizes a course of action, or plan, that satisfies a desired set of goals from an initial situation. A Multi-Agent System (MAS) is a distributed system where a group of autonomous agents pursue their own goals in a reactive, proactive and social way. Multi-Agent Planning (MAP) is a novel research field that emerges as the integration of automated planning in MAS. Agents are endowed with planning capabilities and their mission is to find a course of action that attains the goals of the MAP task. MAP generalizes the problem of automated planning in domains where several agents plan and act together by combining their knowledge, information and capabilities. In cooperative MAP, agents are assumed to be collaborative and work together towards the joint construction of a competent plan that solves a set of common goals. There exist different methods to address this objective, which vary according to the typology and coordination needs of the MAP task to solve; that is, to which extent agents are able to make their own local plans without affecting the activities of the other agents. The present PhD thesis focuses on the design, development and experimental evaluation of a general-purpose and domain-independent resolution framework that solves cooperative MAP tasks of different typology and complexity. More precisely, our model performs a multi-agent multi-heuristic search over a plan space. Agents make use of an embedded search engine based on forward-chaining Partial Order Planning to successively build refinement plans starting from an initial empty plan while they jointly explore a multi-agent search tree. All the reasoning processes, algorithms and coordination protocols are fully distributed among the planning agents and guarantee the preservation of the agents' private information. The multi-agent search is guided through the alternation of two state-based heuristic functions. These heuristic estimators use the global information on the MAP task instead of the local projections of the task of each agent. The experimental evaluation shows the effectiveness of our multi-heuristic search scheme, obtaining significant results in a wide variety of cooperative MAP tasks adapted from the benchmarks of the International Planning Competition. / [ES] La planificación automática es un proceso centralizado en el que una única entidad de planificación, o agente, sintetiza un curso de acción, o plan, que satisface un conjunto deseado de objetivos a partir de una situación inicial. Un Sistema Multi-Agente (SMA) es un sistema distribuido en el que un grupo de agentes autónomos persiguen sus propias metas de forma reactiva, proactiva y social. La Planificación Multi-Agente (PMA) es un nuevo campo de investigación que surge de la integración de planificación automática en SMA. Los agentes disponen de capacidades de planificación y su propósito consiste en generar un curso de acción que alcance los objetivos de la tarea de PMA. La PMA generaliza el problema de planificación automática en dominios en los que diversos agentes planifican y actúan conjuntamente mediante la combinación de sus conocimientos, información y capacidades. En PMA cooperativa, se asume que los agentes son colaborativos y trabajan conjuntamente para la construcción de un plan competente que resuelva una serie de objetivos comunes. Existen distintos métodos para alcanzar este objetivo que varían de acuerdo a la tipología y las necesidades de coordinación de la tarea de PMA a resolver; esto es, hasta qué punto los agentes pueden generar sus propios planes locales sin afectar a las actividades de otros agentes. La presente tesis doctoral se centra en el diseño, desarrollo y evaluación experimental de una herramienta independiente del dominio y de propósito general para la resolución de tareas de PMA cooperativa de distinta tipología y nivel de complejidad. Particularmente, nuestro modelo realiza una búsqueda multi-agente y multi-heurística sobre el espacio de planes. Los agentes hacen uso de un motor de búsqueda embebido basado en Planificación de Orden Parcial de encadenamiento progresivo para generar planes refinamiento de forma sucesiva mientras exploran conjuntamente el árbol de búsqueda multiagente. Todos los procesos de razonamiento, algoritmos y protocolos de coordinación están totalmente distribuidos entre los agentes y garantizan la preservación de la información privada de los agentes. La búsqueda multi-agente se guía mediante la alternancia de dos funciones heurísticas basadas en estados. Estos estimadores heurísticos utilizan la información global de la tarea de PMA en lugar de las proyecciones locales de la tarea de cada agente. La evaluación experimental muestra la efectividad de nuestro esquema de búsqueda multi-heurístico, que obtiene resultados significativos en una amplia variedad de tareas de PMA cooperativa adaptadas a partir de los bancos de pruebas de las Competición Internacional de Planificación. / [CA] La planificació automàtica és un procés centralitzat en el que una única entitat de planificació, o agent, sintetitza un curs d'acció, o pla, que satisfau un conjunt desitjat d'objectius a partir d'una situació inicial. Un Sistema Multi-Agent (SMA) és un sistema distribuït en el que un grup d'agents autònoms persegueixen les seues pròpies metes de forma reactiva, proactiva i social. La Planificació Multi-Agent (PMA) és un nou camp d'investigació que sorgeix de la integració de planificació automàtica en SMA. Els agents estan dotats de capacitats de planificació i el seu propòsit consisteix en generar un curs d'acció que aconseguisca els objectius de la tasca de PMA. La PMA generalitza el problema de planificació automàtica en dominis en què diversos agents planifiquen i actúen conjuntament mitjançant la combinació dels seus coneixements, informació i capacitats. En PMA cooperativa, s'assumeix que els agents són col·laboratius i treballen conjuntament per la construcció d'un pla competent que ressolga una sèrie d'objectius comuns. Existeixen diferents mètodes per assolir aquest objectiu que varien d'acord a la tipologia i les necessitats de coordinació de la tasca de PMA a ressoldre; és a dir, fins a quin punt els agents poden generar els seus propis plans locals sense afectar a les activitats d'altres agents. La present tesi doctoral es centra en el disseny, desenvolupament i avaluació experimental d'una ferramenta independent del domini i de propòsit general per la resolució de tasques de PMA cooperativa de diferent tipologia i nivell de complexitat. Particularment, el nostre model realitza una cerca multi-agent i multi-heuristica sobre l'espai de plans. Els agents fan ús d'un motor de cerca embegut en base a Planificació d'Ordre Parcial d'encadenament progressiu per generar plans de refinament de forma successiva mentre exploren conjuntament l'arbre de cerca multiagent. Tots els processos de raonament, algoritmes i protocols de coordinació estan totalment distribuïts entre els agents i garanteixen la preservació de la informació privada dels agents. La cerca multi-agent es guia mitjançant l'aternança de dues funcions heurístiques basades en estats. Aquests estimadors heurístics utilitzen la informació global de la tasca de PMA en lloc de les projeccions locals de la tasca de cada agent. L'avaluació experimental mostra l'efectivitat del nostre esquema de cerca multi-heurístic, que obté resultats significatius en una ampla varietat de tasques de PMA cooperativa adaptades a partir dels bancs de proves de la Competició Internacional de Planificació. / Torreño Lerma, A. (2016). Cooperative planning in multi-agent systems [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/65815 / TESIS / Premios Extraordinarios de tesis doctorales / Compendio

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19124号 / 情博第570号 / 新制||情||100(附属図書館) / 32075 / 京都大学大学院情報学研究科システム科学専攻 / (主査)教授 杉江 俊治, 教授 太田 快人, 教授 大塚 敏之, 准教授 東 俊一 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第21356号 / 工博第4515号 / 新制||工||1703(附属図書館) / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 藤井 聡, 准教授 QURESHI,Ali Gul, 准教授 SCHMOECKER,Jan-Dirk / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DGAM

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第21916号 / 情博第699号 / 新制||情||120(附属図書館) / 京都大学大学院情報学研究科数理工学専攻 / (主査)准教授 加嶋 健司, 教授 太田 快人, 教授 山下 信雄 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

No description available.

In various industries, such as manufacturing, logistics, agriculture, defense, search and rescue, and transportation, Multi-robot systems (MRSs) are increasingly gaining popularity. These systems involve multiple robots working together towards a shared objective, either autonomously or under human supervision. However, as MRSs operate in uncertain or even adversarial environments, and the sensors and actuators of each robot may be error-prone, they are susceptible to faults and security threats unique to MRSs. Classical techniques from distributed systems cannot detect or mitigate these threats. In this dissertation, novel techniques are proposed to enhance the security and fault-tolerance of MRSs through inter-robot observations and accusations. A fundamental security property is proposed for MRSs, which ensures that forbidden deviations from a desired multi-robot motion plan by the system supervisor are detected. Relying solely on self-reported motion information from the robots for monitoring deviations can leave the system vulnerable to attacks from a single compromised robot. The concept of co-observations is introduced, which are additional data reported to the supervisor to supplement the self-reported motion information. Co-observation-based detection is formalized as a method of identifying deviations from the expected motion plan based on discrepancies in the sequence of co-observations reported. An optimal deviation-detecting motion planning problem is formulated that achieves all the original application objectives while ensuring that all forbidden plan-deviation attacks trigger co-observation-based detection by the supervisor. A secure motion planner based on constraint solving is proposed as a proof-of-concept to implement the deviation-detecting security property. The security and resilience of MRSs against plan deviation attacks are further improved by limiting the information available to attackers. An efficient algorithm is proposed that verifies the inability of an attacker to stealthily perform forbidden plan deviation attacks with a given motion plan and announcement scheme. Such announcement schemes are referred to as horizon-limiting. An optimal horizon-limiting planning problem is formulated that maximizes planning lookahead while maintaining the announcement scheme as horizon-limiting. Co-observations and horizon-limiting announcements are shown to be efficient and scalable in protecting MRSs, including systems with hundreds of robots, as evidenced by a case study in a warehouse setting. Lastly, the Decentralized Blocklist Protocol (DBP), a method for designing Byzantine-resilient decentralized MRSs, is introduced. DBP is based on inter-robot accusations and allows cooperative robots to identify misbehavior through co-observations and share this information through the network. The method is adaptive to the number of faulty robots and is widely applicable to various decentralized MRS applications. It also permits fast information propagation, requires fewer cooperative observers of application-specific variables, and reduces the worst-case connectivity requirement, making it more scalable than existing methods. Empirical results demonstrate the scalability and effectiveness of DBP in cooperative target tracking, time synchronization, and localization case studies with hundreds of robots. The techniques proposed in this dissertation enhance the security and fault-tolerance of MRSs operating in uncertain and adversarial environments, aiding in the development of secure MRSs for emerging applications.

Recent rapid advances in computing, communication, sensing, and actuation, together with miniaturization technologies, have offered unprecedented opportunities to employ large numbers of autonomous vehicles (air, ground, and water) working cooperatively to accomplish a mission. Cooperative control of such multi-agent dynamical systems has potential impact on numerous civilian, homeland security, and military applications. Compared with single-agent control problems, new theoretical and practical challenges emerge and need to be addressed in cooperative control of multiagent dynamical systems, including but not limited to problem size, task coupling, limited computational resources at individual agent level, communication constraints, and the need for real-time obstacle/collision avoidance. In order to address these challenges, a unified optimal multi-agent cooperative control strategy is proposed to formulate the multi-objective cooperative control problem into one unified optimal control framework. Many cooperative behaviors, such as consensus, cooperative tracking, formation, obstacle/collision avoidance, or flocking with cohesion and repulsion, can be treated in one optimization process. An innovative inverse optimal control approach is utilized to include these cooperative objectives in derived cost functions such that a closedorm cooperative control law can be obtained. In addition, the control law is distributed and only depends on the local neighboring agents’ information. Therefore, this new method does not demand intensive computational load and is easy for real-time onboard implementation. Furthermore, it is very scalable to large multi-agent cooperative dynamical systems. The closed-loop asymptotic stability and optimality are theoretically proved. Simulations based on MATLAB are conducted to validate the cooperative behaviors including consensus, Rendezvous, formation flying, and flocking, as well as the obstacle avoidance performance.

We investigate an approach to apply Genetic Programming for the evolution of optimal escaping strategies of a team of caribou agents in the wolf-caribou predator prey problem (WCPPP) where the WCPPP is comprised of a team of caribou agents attempting to escape from a single yet superior (in terms of sensory abilities, raw speed, and maximum energy) wolf agent in a simulated twodimensional infinite toroidal world. We empirically verify our hypothesis that the incorporation of empathy in caribou agents significantly improves both the evolution efficiency of the escaping behavior and the effectiveness of such a behavior. This finding may be viewed as a verification of the survival value of empathy and the resulting compassionate behavior of the escaping caribou agents. Moreover, considering the fact that a single caribou cannot escape from the superior wolf, the ability of a team of empathic caribou agents to escape may also be viewed as an illustration of the emergent nature of a successful escaping behavior – in that the team-level properties are more than the mere sum of the properties of the individual entities. Within this context, we also present empirical results that verify the complex (nonlinear) nature of the relationship between the size of team of caribou agents and the efficiency of their escaping behavior. / 博士(工学) / Doctor of Philosophy in Engineering / 同志社大学 / Doshisha University

Background. The A* algorithm is a well-established pathfinding technique frequently used in video game development. However, a disadvantage of the A* algorithm is that it becomes computationally inefficient and impractical to utilize whenthousands of agents demand an optimal path. A solution to mitigate this issue isthe use of the flow field algorithm. This algorithm employs a goal-based pathfindingstrategy, which allows for the movement of a large number of units through the useof a single direction map (flow field map) that indicates the direction units must take to progress toward their goal. Objectives. The main objective of this study is to examine the performance and scalability of precomputed flow field maps with regard to execution time and memory utilization, with the objective of determining the feasibility of precomputed maps as an alternative to maps generated at runtime. Furthermore, the study implements and investigates compression techniques to minimize the memory footprint of precomputed flow field maps. Methods. The study adopts an experimental research design to assess the performance of the two implementations under various conditions of grid size and movement system. Performance evaluation is accomplished through the measurement and comparison of execution time and memory consumption. Additionally, a directional accuracy test is performed to quantify the potential loss of accuracy in the vectors stored in the precomputed flow field maps. Results. The precomputed flow field maps provide constant access time, with a time complexity of O(1), regardless of the grid size and the type of movement system. The memory usage of these maps increases significantly with the growth of the grid size. A doubling of the grid size leads to a more than fifteen-fold increase in memory usage. The techniques proposed in the study significantly reduced the memory footprint by a factor of thirty-two and by a factor of eight, depending on the selected movement system. The average loss in accuracy was approximately 0.35 degrees for the proposed any-angle compression technique. Conclusions. The use of precomputed flow field maps has limitations, including being limited to static environments and having high memory requirements. On the other hand, they provide constant access time for pathfinding information, independent of the grid dimensions, movement system, and the number of target nodes. Whether precomputed flow field maps are better than the traditional runtime implementation depends on the intended use.