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

No description available.

Decision-making is an essential topic for multi-robot coordination and collaboration and is also the main topic of this thesis. Examples can be found in autonomous driving, environmental monitoring, intelligent transportation, etc. To study this problem, we first use multiple applications as motivating examples and then construct the general formulation and solution for those applications. Finally, we extend our investigation from the fundamental problem formulation to resilient and decentralized versions. All those problems are studied in the combinatorial optimization domain with the help of submodular and matroid optimization techniques. As a motivating example, we use a multi-robot environmental monitoring problem to extract the general formulation of a multi-robot decision-making problem. Consider the problem of deploying multi-agent teams for environmental monitoring in a precision farming application. We want to answer the question of when and where to deploy our robots. This is a typical task allocation problem in multi-robot systems. Using the above problem as an example, we first focus on this decision-making problem, e.g., intermittent deployment problem, in a centralized scenario. Given a predictable agriculture environment, we want to make decisions for robots for this monitoring task. The problem is formulated as a combinatorial submodular optimization with matroid constraints. By utilizing the properties of submodularity, we aim to develop a solution with performance guarantees. This motivating example demonstrates how to use a submodular function and matroids to model and solve decision-making problems in multi-robot systems. Based on this framework, we continue to explore the fundamental decision-making problem in several other directions in multi-robot systems, including the robust decision-making problem. All those problems and solutions are formulated and considered in a centralized scenario. In the second part of this thesis, we switch our focus from centralized to decentralized scenarios. We first investigate a case where the robots in a distributed multi-robot system need to work together to guard the system against worst-case attacks while making decisions. By worst-case attacks, we refer to the case where the system may have up to $K$ sensor failures. To increase resilience, we propose a fully distributed algorithm to guide each robot's action selection when the system is attacked. The proposed algorithm guarantees performance in a worst-case scenario where up to a portion of the robots malfunction due to attacks. Based on this specific task allocation problem in robotics, we then create a unified framework for a more general case in a decentralized scenario, e.g., asynchronous decentralized decision-making problems with matroid and knapsack constraints. Finally, several applications in decentralized scenarios are used to validate the theoretical guaranteed performance in robotics. / Doctor of Philosophy / Robots have been widely used as mobile sensing agents nowadays in various applications. Especially with the help of multi-robot systems and artificial intelligence, our lives have changed dramatically in the last decades. One of the most fundamental questions is how to utilize multi-robot systems to finish tasks successfully. To answer this, we need first to formulate the problem from applications and then find theoretically guaranteed answers to those questions. Meanwhile, the robustness and resilience of the solution also need to be taken care of, as cyber-attacks or system failures can happen everywhere. Motivated by those two main goals, this thesis will first use multiple applications to introduce the thesis's topic. We then provide solutions to those problems in centralized and decentralized scenarios. Meanwhile, to increase the system's ability to handle failures, we need to answer how to improve the robustness and resilience of the proposed solutions. Therefore, the topic of this thesis spread from problem formulation to failure-proof solutions. The result of this thesis can be widely used in multi-robot decision-making applications, including autonomous driving, intelligent transportation, and other cyber-physical systems.

Multi-robot task assignment (allocation) involves assigning robots to tasks in order to optimize the entire team’s performances. Until now, one of the most useful non-domain-specific ways to coordinate multi-robot systems is through task allocation mechanisms. This dissertation addresses the classic task assignment problems in which robots and tasks are eventually matched by forming a one-to-one mapping, and their overall performances (e.g., cost, utility, and risk) can be linearly summed. At a high level, this research emphasizes two facets of the multi-robot task assignment, including (1) novel extensions from classic assignment algorithms, and (2) completely newly designed task allocation methods with impressive new features. For the former, we first propose a strongly polynomial assignment sensitivity analysis algorithm as well as a means to measure the assignment uncertainties; after that we propose a novel method to address problems of multi-robot routing and formation morphing, the trajectories of which are obtained from projections of augmenting paths that reside in a new three-dimensional interpretation of embedded matching graphs. For the latter, we present two optimal assignment algorithms that are distributable and suitable for multi-robot task allocation problems: the first one is an anytime assignment algorithm that produces non-decreasing assignment solutions along a series of task-swapping operations, each of which updates the assignment configurations and thus can be interrupted at any moment; the second one is a new market-based algorithm with a novel pricing policy: in contrast to the buyers’ “selfish” bidding behaviors in conventional auction/market-based approaches, we employ a virtual merchant to strategically escalate market prices in order to reach a state of equilibrium that satisfies both the merchant and buyers. Both of these newly developed assignment algorithms have a strongly polynomial running time close to the benchmark algorithms but can be easily decentralized in terms of computation and communication.

This study aims to explore how the gendered allocation of tasks within political parties influences the career path for male and female politicians through a case study of the Swedish Center party. A gendered allocation of tasks has earlier been observed in the context of academia and business, where women tend to perform more tasks with low promotability and men more tasks with high promotability. According to the existing research, this contributes to the enduring work place inequality. A survey was conducted among leading politicians in the Center party to determine which tasks have high and low promotability. A parallel survey was then administered among members of the party’s youth organization to determine which tasks male and female members perform. The results show that men are significantly more interested than women in pursuing a political career and perform a significantly larger amount of tasks. The study provides no evidence that female members of the Center party youth organization in general perform more tasks with low promotability than their male colleagues, and more research is required to determine if and why that is so.

With the promise to shape the future of industry, multi-agent robotic technologies have the potential to change many aspects of daily life. Over the coming decade, they are expected to impact transportation systems, military applications such as reconnaissance and surveillance, search-and-rescue operations, or space missions, as well as provide support to emergency first responders. Motivated by the latest developments in the field of robotics, this thesis contributes to the evolution of the future generation of multi-agent robotic systems as they become smarter, more accurate, and diversified in terms of applications. But in order to achieve these goals, the individual agents forming cooperative robotic systems need to be specialized in what they can accomplish, while ensuring accuracy and preserving the ability to perform diverse tasks. This thesis addresses the problem of task allocation in swarm robotics in the specific context where specialized capabilities of the individual agents are considered. Based on the assumption that each individual agent possesses specialized functional capabilities and that the expected tasks, which are distributed in the surrounding environment, impose specific requirements, the proposed task allocation mechanisms are formulated in two different spaces. First, a rudimentary form of the team members’ specialization is formulated as a cooperative control problem embedded in the agents’ dynamics control space. Second, an advanced formulation of agents’ specialization is defined to estimate the individual agents’ task allocation probabilities in a dedicated specialization space, which represents the core contribution of this thesis to the advancement and practice in the area of swarm robotics. The original task allocation process formulated in the specialization space evolves through four stages of development. First, a task features recognition stage is conceptually introduced to leverage the output of a sensing layer embedded in robotic agents to drive the proposed task allocation scheme. Second, a matching scheme is developed to best match each agent’s specialized capabilities with the corresponding detected tasks. At this stage, a general binary definition of agents’ specialization serves as the basis for task-agent association. Third, the task-agent matching scheme is expanded to an innovative probabilistic specialty-based task-agent allocation framework to generalize the concept and exploit the potential of agents’ specialization consideration. Fourth, the general framework is further refined with a modulated definition of the agents’ specialization based on their mechanical, physical structure, and embedded resources. The original framework is extended and a prioritization layer is also introduced to improve the system’s response to complex tasks that are characterized based on the recognition of multiple classes. Experimental validation of the proposed specialty-based task allocation approach is conducted in simulation and on real-world experiments, and the results are presented and discussed in light of potential applications to demonstrate the effectiveness and efficiency of the proposed framework.

The problem of determining who should do what given a set of tasks and a set of agents is called the task allocation problem. The problem occurs in many multi-agent system applications where a workload of tasks should be shared by a number of agents. In our case, the task allocation problem occurs as an integral part of a larger problem of determining if a task can be delegated from one agent to another. Delegation is the act of handing over the responsibility for something to someone. Previously, a theory for delegation including a delegation speech act has been specified. The speech act specifies the preconditions that must be fulfilled before the delegation can be carried out, and the postconditions that will be true afterward. To actually use the speech act in a multi-agent system, there must be a practical way of determining if the preconditions are true. This can be done by a process that includes solving a complex task allocation problem by the agents involved in the delegation. In this thesis a constraint-based task specification formalism, a complex task allocation algorithm for allocating tasks to unmanned aerial vehicles and a generic collaborative system shell for robotic systems are developed. The three components are used as the basis for a collaborative unmanned aircraft system that uses delegation for distributing and coordinating the agents' execution of complex tasks.

The state of the art of autonomous vehicles requires operators to remain vigilant while performing secondary tasks. The goal of this research was to investigate how dynamically allocated secondary tasks affected driving performance, cognitive load, and situation awareness. Secondary tasks were presented at rates based on the autonomy level present and whether the autonomous system was engaged. A rapid secondary task rate was also presented for two short periods regardless of whether autonomy was engaged. There was a three-minute familiarization phase followed by a data collection phase where participants responded to secondary tasks while preventing the vehicle from colliding into random obstacles. After data collection, there was a brief survey to gather data on cognitive load, situation awareness, and relevant demographics. The data was compared to data gathered in a similar study by Cossitt [10] where secondary tasks were presented at a controlled frequency and a gradually increasing frequency.

Recent developments in autopilot technology have increased the potential use of micro air vehicles (MAVs). As the number of applications increase, the demand on MAVs to operate autonomously in any scenario increases. Currently, MAVs cannot reliably fly in cluttered environments because of the difficulty to detect and avoid obstacles. The main contribution of this research is to offer obstacle detection and avoidance strategies using laser rangers and cameras coupled with computer vision processing. In addition, we explore methods of visual target tracking and task allocation. Utilizing a laser ranger, we develop a dynamic geometric guidance strategy to generate paths around detected obstacles. The strategy overrides a waypoint planner in the presence of pop-up-obstacles. We develop a second guidance strategy that oscillates the MAV around the waypoint path and guarantees obstacle detection and avoidance. Both rely on a laser ranger for obstacles detection and are demonstrated in simulation and in flight tests. Utilizing EO/IR cameras, we develop two guidance strategies based on movement of obstacles in the camera field-of-view to maneuver the MAV around pop-up obstacles. Vision processing available on a ground station provides range and bearing to nearby obstacles. The first guidance law is derived for single obstacle avoidance and pushes the obstacle to the edge of the camera field-of-view causing the vehicle to avoid a collision. The second guidance law is derived for two obstacles and balances the obstacles on opposite edges of the camera field-of-view, maneuvering between the obstacles. The guidance strategies are demonstrated in simulation and flight tests. This research also addresses the problem of tracking a ground based target with a fixed camera pointing out the wing of a MAV that is subjected to constant wind. Rather than planning explicit trajectories for the vehicle, a visual feedback guidance strategy is developed that maintains the target in the field-of-view of the camera. We show that under ideal conditions, the resulting flight paths are optimal elliptical trajectories if the target is forced to the center of the image plane. Using simulation and flight tests, the resulting algorithm is shown to be robust with respect to gusts and vehicle modeling errors. Lastly, we develop a method of a priori collision avoidance in assigning multiple tasks to cooperative unmanned air vehicles (UAV). The problem is posed as a combinatorial optimization problem. A branch and bound tree search algorithm is implemented to find a feasible solution using a cost function integrating distance traveled and proximity to other UAVs. The results demonstrate that the resulting path is near optimal with respect to distance traveled and includes a significant increase in expected proximity distance to other UAVs. The algorithm runs in less than a tenth of a second allowing on-the-fly replanning.

<p dir="ltr">The research presented in this thesis presents methods to solve multi-agent task allocation and path planning problems in the application of on-orbit servicing.</p>