This dissertation addresses the problem of influence maximization in social networks. In- fluence maximization is applicable to many types of real-world problems, including modeling contagion, technology adoption, and viral marketing. Here we examine an advertisement domain in which the overarching goal is to find the influential nodes in a social network, based on the network structure and the interactions, as targets of advertisement. The assumption is that advertisement budget limits prevent us from sending the advertisement to everybody in the network. Therefore, a wise selection of the people can be beneficial in increasing the product adoption. To model these social systems, agent-based modeling, a powerful tool for the study of phenomena that are difficult to observe within the confines of the laboratory, is used. To analyze marketing scenarios, this dissertation proposes a new method for propagating information through a social system and demonstrates how it can be used to develop a product advertisement strategy in a simulated market. We consider the desire of agents toward purchasing an item as a random variable and solve the influence maximization problem in steady state using an optimization method to assign the advertisement of available products to appropriate messenger agents. Our market simulation 1) accounts for the effects of group membership on agent attitudes 2) has a network structure that is similar to realistic human systems 3) models inter-product preference correlations that can be learned from market data. The results on synthetic data show that this method is significantly better than network analysis methods based on centrality measures. The optimized influence maximization (OIM) described above, has some limitations. For instance, it relies on a global estimation of the interaction among agents in the network, rendering it incapable of handling large networks. Although OIM is capable of finding the influential nodes in the social network in an optimized way and targeting them for advertising, in large networks, performing the matrix operations required to find the optimized solution is intractable. To overcome this limitation, we then propose a hierarchical influence maximization (HIM) iii algorithm for scaling influence maximization to larger networks. In the hierarchical method the network is partitioned into multiple smaller networks that can be solved exactly with optimization techniques, assuming a generalized IC model, to identify a candidate set of seed nodes. The candidate nodes are used to create a distance-preserving abstract version of the network that maintains an aggregate influence model between partitions. The budget limitation for the advertising dictates the algorithm’s stopping point. On synthetic datasets, we show that our method comes close to the optimal node selection, at substantially lower runtime costs. We present results from applying the HIM algorithm to real-world datasets collected from social media sites with large numbers of users (Epinions, SlashDot, and WikiVote) and compare it with two benchmarks, PMIA and DegreeDiscount, to examine the scalability and performance. Our experimental results reveal that HIM scales to larger networks but is outperformed by degreebased algorithms in highly-connected networks. However, HIM performs well in modular networks where the communities are clearly separable with small number of cross-community edges. This finding suggests that for practical applications it is useful to account for network properties when selecting an influence maximization method.

The security objectives enforce the security policy, which defines what is to be protected in a network environment. The violation of these security objectives induces security threats. We introduce an explicit notion of security objectives for a security protocol. This notion should precede the formal verification process. In the absence of such a notion, the security protocol may be proven correct despite the fact that it is not equipped to defend against all potential threats. In order to establish the correctness of security objectives, we present a formal model that provides basis for the formal verification of security protocols. We also develop the modal logic, proof based, and multi-agent approaches using the Strand Space framework. In our modal logic approach, we present the logical constructs to model a protocol's behavior in such a way that the participants can verify different security parameters by looking at their own run of the protocol. In our proof based model, we present a generic set of proofs to establish the correctness of a security protocol. We model the 802.11i protocol into our proof based system and then perform the formal verification of the authentication property. The intruder in our model is imbued with powerful capabilities and repercussions to possible attacks are evaluated. Our analysis proves that the authentication of 802.11i is not compromised in the presented model. We further demonstrate how changes in our model will yield a successful man-in-the-middle attack. Our multi-agent approach includes an explicit notion of multi-agent, which was missing in the Strand Space framework. The limitation of Strand Space framework is the assumption that all the information available to a principal is either supplied initially or is contained in messages received by that principal. However, other important information may also be available to a principal in a security setting, such as a principal may combine information from different roles played by him in a protocol to launch a powerful attack. Our presented approach models the behavior of a distributed system as a multi-agent system. The presented model captures the combined information, the formal model of knowledge, and the belief of agents over time. After building this formal model, we present a formal proof of authentication of the 4-way handshake of the 802.11i protocol.

Robots are increasingly utilized in industry for their capability to perform repetitive,complex tasks in environments unsuitable for humans. This surge in robotic applicationshas spurred research into Multi-Robot Systems (MRS), which aim to tackle complex tasksrequiring collaboration among multiple robots, thereby boosting overall efficiency. However,MRS introduces multifaceted challenges that span various domains, including robot perception,localization, task assignment, communication, and control. This dissertation delves into theintricate aspects of task assignment and path planning within MRS.The first area of focus is on multi-robot navigation, specifically addressing the limitationsinherent in current Multi-Agent Path Finding (MAPF) models. Traditional MAPF solutionstend to oversimplify, treating robots as holonomic units on grid maps. While this approachis impractical in real-world settings where robots have distinct geometries and kinematicrestrictions, it is important to note that even in its simplified form, MAPF is categorized as anNP-hard problem. The complexity inherent in MAPF becomes even more pronounced whenextending these models to non-holonomic robots, underscoring the significant computationalchallenges involved. To address these challenges, this thesis introduces a novel MAPF solverdesigned for non-holonomic, heterogeneous robots. This solver integrates the hybrid A*algorithm, accommodating kinematic constraints, with a conflict-based search (CBS) for efficientconflict resolution. A depth-first search approach in the conflict tree is utilized to accelerate theidentification of viable solutions.The second research direction explores synergizing task assignment with path-finding inMRS. While there is substantial research in both decentralized and centralized task assignmentstrategies, integrating these with path-finding remains underexplored. This dissertation evaluatesdecoupled methods for sequentially resolving task assignment and MAPF challenges. Oneproposed method combines the Hungarian algorithm and a Traveling Salesman Problem (TSP)solver for swift, albeit suboptimal, task allocation. Subsequently, robot paths are generatedindependently, under the assumption of collision-free navigation. During actual navigation, aNonlinear Model Predictive Controller (NMPC) is deployed for dynamic collision avoidance. Analternative approach seeks optimal solutions by conceptualizing task assignment as a MultipleTraveling Salesman Problem (MTSP), solved using a simulated annealing algorithm. In tandem,CBS is iteratively applied to minimize the cumulative path costs of the robots.

Yes / Industry 4.0 promotes highly automated mechanisms for setting up and operating flexible manufacturing systems, using distributed control and data-driven machine intelligence. This paper presents an approach to reconfiguring distributed production systems based on complex product requirements, combining the capabilities of the available production resources. A method for both checking the “realisability” of a product by matching required operations and capabilities, and adapting resources is introduced. The reconfiguration is handled by a multi-agent system, which reflects the distributed nature of the production system and provides an intelligent interface to the user. This is all integrated with a self-adaptation technique for learning how to improve the performance of the production system as part of a reconfiguration. This technique is based on a machine learning algorithm that generalises from past experience on adjustments. The mechanisms of the proposed approach have been evaluated on a distributed robotic manufacturing system, demonstrating their efficacy. Nevertheless, the approach is general and it can be applied to other scenarios. / This work was supported by the SURE Research Projects Fund of the University of Bradford and the European Commission (grant agreement no. 314762). / Research Development Fund Publication Prize Award winner, Nov 2022

This thesis is concerned with sequential decision making by multiple agents, whether they are acting cooperatively to maximize team reward or selfishly trying to maximize their individual rewards. The practical intractability of this general problem led to efforts in identifying special cases that admit efficient computation, yet still represent a wide enough range of problems. In our work, we identify the class of problems with structured interactions, where actions of one agent can have non-local effects on the transitions and/or rewards of another agent. We addressed the following research questions: 1) How can we compactly represent this class of problems? 2) How can we efficiently calculate agent policies that maximize team reward (for cooperative agents) or achieve equilibrium (selfinterested agents)? 3) How can we exploit structured interactions to make reasoning about communication offline tractable? For representing our class of problems, we developed a new decision-theoretic model, Event-Driven Interactions with Complex Rewards (EDI-CR), that explicitly represents structured interactions. EDI-CR is a compact yet general representation capable of capturing problems where the degree of coupling among agents ranges from complete independence to complete dependence. For calculating agent policies, we draw on several techniques from the field of mathematical optimization and adapt them to exploit the special structure in EDI-CR. We developed a Mixed Integer Linear Program formulation of EDI-CR with cooperative agents that results in programs much more compact and faster to solve than formulations ignoring structure. We also investigated the use of homotopy methods as an optimization technique, as well as formulation of self-interested EDI-CR as a system of non-linear equations. We looked at the issue of communication in both cooperative and self-interested settings. For the cooperative setting, we developed heuristics that assess the impact of potential communication points and add the ones with highest impact to the agents' decision problems. Our heuristics successfully pick communication points that improve team reward while keeping problem size manageable. Also, by controlling the amount of communication introduced by a heuristic, our approach allows us to control the tradeoff between solution quality and problem size. For self-interested agents, we look at an example setting where communication is an integral part of problem solving, but where the self-interested agents have a reason to be reticent (e.g. privacy concerns). We formulate this problem as a game of incomplete information and present a general algorithm for calculating approximate equilibrium profile in this class of games.

Soft robots are inherently safer than traditional robots due to their compliance and high power density ratio resulting in lower accidental impact forces. Thus they are a natural option for human-robot interaction. This thesis specifically looked at human-robot co-manipulation which is defined as a human and a robot working together to move an object too large or awkward to be safely maneuvered by a single agent. To better understand how humans communicate while co-manipulating an object, this work looked at haptic interaction of human-human dyadic co-manipulation trials and studied some of the trends found in that interaction. These trends point to ways robots can effectively work with human partners in the future. Before successful human-robot co-manipulation with large-scale soft robots can be achieved, low-level joint angle control is needed. Low-level model predictive control of soft robot joints requires a sufficiently accurate model of the system. This thesis introduces a recursive Newton-Euler method for deriving the dynamics that is sufficiently accurate and accounts for flexible joints in an intuitive way. This model has been shown to be accurate to a median absolute error of 3.15 degrees for a three-link three-joint six degree of freedom soft robot arm. Once a sufficiently accurate model was developed, a gain-based evolutionary model predictive control (MPC) technique was formulated based on a previous evolutionary MPC technique. This new method is referred to as model evolutionary gain-based predictive control or MEGa-PC. This control law is compared to nonlinear evolutionary model predictive control (NEMPC). The new technique allows intentionally decreasing the control frequency to 10 Hz while maintaining control of the system. This is proven to help MPC solve more difficult problems by having the ability to extend the control horizon. This new controller is also demonstrated to work well on a three-joint three-link soft robot arm. Although complete physical human-robot co-manipulation is outside the scope of this thesis, this thesis covers three main building blocks for physical human and soft robot co-manipulation: human-human haptic communication, soft robot modeling, and model evolutionary gain-based predictive control.

The advent of on-demand transport modes such as ride-hailing and microtransit has challenged forecasters to develop new methods of forecasting the use and impacts of such modes. In particular, there is some professional disagreement about the relative role of activity-based transportation behavior models -- which have detailed understanding of the person making a trip and its purpose -- and multi-agent demand simulations which may have a better understanding of the availability and service characteristics of on-demand services. A particular question surrounds how the relative strengths of these two approaches might be successfully paired in practice. Using daily plans generated by the activity-based model ActivitySim as inputs to the BEAM multi-agent simulation, we construct nine different methodological combinations by allowing the choice to use a pooled ride-hail service in ActivitySim, in BEAM with different utility functions, or in both. Within each combination, we estimate ride-hailing ridership and level of service measures. The results suggest that mode choice model structure drastically affects ride-hailing ridership and level of service. In addition, we see that multi-agent simulation overstates the demand interest relative to an activity-based model, but there may be opportunities in future research to implement feedback loops to balance the ridership and level of service forecasts between the two models.

京都大学 / 新制・課程博士 / 博士(情報学) / 甲第24261号 / 情博第805号 / 新制||情||136(附属図書館) / 京都大学大学院情報学研究科社会情報学専攻 / (主査)教授 伊藤 孝行, 教授 吉川 正俊, 教授 神田 崇行, 特定准教授 LIN Donghui / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

No description available.

With the increase of robotic presence in our homes and work environment, it has become imperative to consider human-in-the-loop systems when designing robotic controllers. This includes both a physical presence of humans as well as interaction on a decision and control level. One important aspect of this is to design controllers which are guaranteed to satisfy specified safety constraints. At the same time we must minimize the risk of not finding solutions, which would force the system to stop. This require some room for relaxation to be put on the specifications. Another aspect is to design the system to be adaptive to the human and its environment. In this thesis we approach the problem by considering control synthesis for multi-agent systems under hard and soft constraints, where the human has direct impact on how the soft constraint is violated. To handle the multi-agent structure we consider both a classical centralized automata based framework and a decentralized approach with collision avoidance. To handle soft constraints we introduce a novel metric; hybrid distance, which quantify the violation. The hybrid distance consists of two types of violation; continuous distance or missing deadlines, and discrete distance or spacial violation. These distances are weighed against each other with a weight constant we will denote as the human preference constant. For the human impact we consider two types of feedback; direct feedback on the violation in the form of determining the human preference constant, and direct control input through mixed-initiative control where the human preference constant is determined through an inverse reinforcement learning algorithm based on the suggested and followed paths. The methods are validated through simulations. / I takt med att robotar blir allt vanligare i våra hem och i våra arbetsmiljöer, har det blivit allt viktigare att ta hänsyn till människan plats i systemen när regulatorerna för robotorna designas. Detta innefattar både människans fysiska närvaro och interaktion på besluts- och reglernivå. En viktig aspekt i detta är att designa regulatorer som garanterat uppfyller givna villkor. Samtidigt måste vi minimera risken att ingen lösning hittas, eftersom det skulle tvinga systemet till ett stopp. För att uppnå detta krävs det att det finns rum för att mjuka upp villkoren. En annan aspekt är att designa systemet så att det är anpassningsbart till människan och miljön. I den här uppsatsen närmar vi oss problemet genom att använda regulator syntes för multi-agent system under hårda och mjuka villkor där människan har direkt påverkan på hur det svaga villkoret överträds. För att hantera multi-agent strukturen undersöker vi både det klassiska centraliserade automata-baserade ramverket och ett icke-centraliserat tillvägagångsätt med krockundvikning. För att hantera mjuka villkor introducerar vi en metrik; hybrida avståndet, som kvantifierar överträdelsen. Det hybrida avståndet består av två typer av överträdelse (kontinuerligt avstånd eller missandet av deadlines, och diskret avstånd eller rumsliga överträdelser) som vägs mot varandra med en vikt konstant som vi kommer att kalla den mänskliga preferens kontanten. Som mänsklig påverkan överväger vi direkt feedback på överträdelsen genom att hon bestämmer värdet på den mänskliga preferens kontanten, och direkt påverkan på regulatorn där den mänskliga preferens konstanten bestäms genom en inverserad förstärkt inlärnings algoritm baserad på de föreslagna och följda vägarna. Metoderna valideras genom simuleringar. / <p>QC20190517</p>