Agents in most types of societies use information about potential partners to determine whether to form mutually beneficial partnerships. We can say that when this information is used to decide to form a partnership that one agent trusts another, and when agents work together for mutual benefit in a partnership, we refer to this as a form of cooperation. Current multi-robot teams typically have the team's goals either explicitly or implicitly encoded into each robot's utility function and are expected to cooperate and perform as designed. However, there are many situations in which robots may not be interested in full cooperation, or may not be capable of performing as expected. In addition, the control strategy for robots may be fixed with no mechanism for modifying the team structure if teammate performance deteriorates. This dissertation investigates the application of trust to multi-robot teams. This research also addresses the problem of how cooperation can be enabled through the use of incentive mechanisms. We posit a framework wherein robot teams may be formed dynamically, using models of trust. These models are used to improve performance on the team, through evolution of the team dynamics. In this context, robots learn online which of their peers are capable and trustworthy to dynamically adjust their teaming strategy. We apply this framework to multi-robot task allocation and patrolling domains and show that performance is improved when this approach is used on teams that may have poorly performing or untrustworthy members. The contributions of this dissertation include algorithms for applying performance characteristics of individual robots to task allocation, methods for monitoring performance of robot team members, and a framework for modeling trust of robot team members. This work also includes experimental results gathered using simulations and on a team of indoor mobile robots to show that the use of a trust model can improve performance on multi-robot teams in the patrolling task.

The task assignment problem is one of the fundamental combinatorial optimization problems. It has been extensively studied in operation research, management science, computer science and robotics. Task assignment problems arise in various applications of multi-robot systems (MRS), such as environmental monitoring, disaster response, extraterrestrial exploration, sensing data collection and collaborative autonomous manufacturing. In these MRS applications, there are realistic constraints on robots and tasks that must be taken into account both from the modeling perspective and the algorithmic perspective. From the modeling aspect, such constraints include (a) Task group constraints: where tasks form disjoint groups and each robot can be assigned to at most one task in each group. One example of the group constraints comes from tightly-coupled tasks, where multiple micro tasks form one tightly-coupled macro task and need multiple robots to perform each simultaneously. (b) Task deadline constraints: where tasks must be assigned to meet their deadlines. (c) Dynamically-arising tasks: where tasks arrive dynamically and the payoffs of future tasks are unknown. Such tasks arise in scenarios like searchrescue, where new victims are found dynamically. (d) Robot budget constraints: where the number of tasks each robot can perform is bounded according to the resource it possesses (e.g., energy). From the solution aspect, there is often a need for decentralized solution that are implemented on individual robots, especially when no powerful centralized controller exists or when the system needs to avoid single-point failure or be adaptive to environmental changes. Most existing algorithms either do not consider the above constraints in problem modeling, are centralized or do not provide formal performance guarantees. In this thesis, I propose methods to address these issues for two classes of problems, namely, the constrained linear assignment problem and constrained generalized assignment problem. Constrained linear assignment problem belongs to P, while constrained generalized assignment problem is NP-hard. I develop decomposition-based distributed auction algorithms with performance guarantees for both problem classes. The multi-robot assignment problem is decomposed into an optimization problem for each robot and each robot iteratively solving its own optimization problem leads to a provably good solution to the overall problem. For constrained linear assignment problem, my approaches provides an almost optimal solution. For constrained generalized assignment problem, I present a distributed algorithm that provides a solution within a constant factor of the optimal solution. I also study the online version of the task allocation problem with task group constraints. For the online problem, I prove that a repeated greedy version of my algorithm gives solution with constant factor competitive ratio. I include simulation results to evaluate the average-case performance of the proposed algorithms. I also include results on multi-robot cooperative package transport to illustrate the approach.

Many computer vision problems, such as object classification, motion estimation or shape registration rely on solving the correspondence problem. Existing algorithms to solve spatial or temporal correspondence problems are usually NP-hard, difficult to approximate, lack flexible models and mechanism for feature weighting. This proposal addresses the correspondence problem in computer vision, and proposes two new spatio-temporal correspondence problems and three algorithms to solve spatial, temporal and spatio-temporal matching between video and other sources. The main contributions of the thesis are: (1) Factorial graph matching (FGM). FGM extends existing work on graph matching (GM) by finding an exact factorization of the affinity matrix. Four are the benefits that follow from this factorization: (a) There is no need to compute the costly (in space and time) pairwise affinity matrix; (b) It provides a unified framework that reveals commonalities and differences between GM methods. Moreover, the factorization provides a clean connection with other matching algorithms such as iterative closest point; (c) The factorization allows the use of a path-following optimization algorithm, that leads to improved optimization strategies and matching performance; (d) Given the factorization, it becomes straight-forward to incorporate geometric transformations (rigid and non-rigid) to the GM problem. (2) Canonical time warping (CTW). CTW is a technique to temporally align multiple multi-dimensional and multi-modal time series. CTW extends DTW by incorporating a feature weighting layer to adapt different modalities, allowing a more flexible warping as combination of monotonic functions, and has linear complexity (unlike DTW that has quadratic). We applied CTW to align human motion captured with different sensors (e.g., audio, video, accelerometers). (3) Spatio-temporal matching (STM). Given a video and a 3D motion capture model, STM finds the correspondence between subsets of video trajectories and the motion capture model. STM is efficiently and robustly solved using linear programming. We illustrate the performance of STM on the problem of human detection in video, and show how STM achieves state-of-the-art performance.

Numerous aspects of job scheduling in manufacturing systems have been the focus of several studies in the past decades. However, human factors in manufacturing systems such as workers’ mental conditions are still neglected issues and have not received adequate attentions. Job boredom and mental fatigue are both aspects of workers’ mental condition. They affect work performances by increasing sick leave duration and decreasing work productivity. On the other hand, job rotation could be an alternative strategy to cope with such human issues at work. The benefits of job rotation for both employees and firms have been widely recognized in the literature. Although some studies found job rotation as a means to reduce workers' physical work-related traumas, they did not consider the effect of variable mental conditions on workers. Despite the proven importance of boredom and mental fatigue at the workplace, they have not been a combined precise objective of any job rotation problem in current literature. The study of mental conditions proposed in this paper attempts to extend the previous works by addressing new methods and developing a feasible solution to increase manufacturing productivity. A new job scheduling program has been designed specifically which combines a new job rotation model and a job assignment method.

This thesis focuses on the development of a distributed software project planning tool that enables more than one participant to prepare the different parts of the project scope, schedule and task assignment by allowing to utilize the predefined organizational level processes. For this purpose, we discuss the need for a distributed software project planning tool, identify tool requirements and compare available tools with respect to the requirements. In addition, we evaluate the tool based on two criteria: first one is the tool&rsquo / s adequacy to meet the identified functional attributes and the second one is the validation of the tool by utilizing the data of the project schedule of a real project. This tool enables preparation of project scope, schedule and task assignments in a more effective, accurate and seamless way.

This thesis describes the critical game flow and dynamic role assignment based on potential fields in robot soccer game and actions taken depending on role assignment. Role assignment is a standard problem of multi-agent game system like robot soccer and it can be realized by many techniques. In this thesis, game flow is described dynamically in terms of critical zones which is formed by potential fields based on the field environment as hills and valleys.

This thesis introduces a multi-objective variation of the personnel assignment problem, by including additional hierarchical and team constraints, which put restrictions on possible matchings of the bipartite graph. Besides maximization of summation of weights that are assigned to the edges of the graph, these additional constraints are also treated as objectives which are subject to minimization. In this work, different genetic algorithm approaches to multi-objective optimization are considered to solve the problem. Weighted Sum &ndash / a classical approach, VEGA - a non-elitist multi-objective evolutionary algorithm, and SPEA &ndash / a popular elitist multi-objective evolutionary algorithm, are considered as means of solution to the problem, and their performances are compared with respect to a number of multi-objective optimization criteria.

This study investigates the relevance of dynamic traffic assignment models under uncertainty. In the last years researchers have dealt with advanced traffic control systems since road provision is not regarded as a proper solution to relieve congestion. Dynamic assignment which is an essential component of investment planning is regarded as a new research area in the field of urban transportation. In this study the performance of dynamic traffic assignment method, which incorporates time dependent flow, is compared with that of static model. Research outcomes showed that dynamic assignment method provides more reliable outcomes in predicting traffic flow / therefore its solution algorithm is integrated to conventional four staged model. Literature survey showed that researches have hot provided an appropriate framework for transforming networks. This study investigates travel demand variations in a dynamic city and discuses possible strategies to respond dynamic and uncertain properties of individuals&rsquo / travel behavior. Research findings showed that both external and internal uncertainties have significant influences on reliability of the model. Recommended procedure aims reducing uncertainty in order to improve reliability of model. Finally, the relevancy of the problem and the applicability of recently developed methods are discussed in Ankara case.

Mobile sensor networks have been shown to be a powerful tool for enabling a number of activities that require recording of environmental parameters at various spatial and temporal distributions. These mobile sensor networks could be implemented using a team of robots, usually called robotic sensor networks. This type of sensor network involves the coordinated control of multiple robots to achieve specific measurements separated by varied distances. In most formation measurement applications, initialization involves identifying a number of interesting sites to which mobility platforms, instrumented with a variety of sensors, are tasked. This process of determining which instrumented robot should be tasked to which location can be viewed as solving the task allocation problem. Unfortunately, a centralized approach does not fit in this type of application due to the fault tolerance requirements. Moreover, as the size of the network grows, limitations in bandwidth severely limits the possibility of conveying and using global information. As such, the utilization of decentralized techniques for forming new sensor topologies and configurations is a highly desired quality of robotic sensor networks. In this thesis, several distributed task allocation algorithms will be explained and compared in different scenarios. They are based on a market approach since our interest is not only to obtain a feasible solution, but also an efficient one. Also, an analysis of the efficiency of those algorithms using probabilistic techniques will be explained. Finally, the task allocation algorithms will be implemented on a real system consisted of a team of six robots and integrated in a complete robotic system that considers obstacle avoidance and path planning. The results will be validated in both simulations and real experiments.

Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2010. / Committee Chair: Earl Barnes; Committee Member: Arkadi Nemirovski; Committee Member: Faiz Al-Khayyal; Committee Member: Guillermo H. Goldsztein; Committee Member: Joel Sokol. Part of the SMARTech Electronic Thesis and Dissertation Collection.