In this thesis, we address the problem of real-time path search in partially observable grid worlds, and propose two single agent and one multi-agent search algorithm. The first algorithm, Real-Time Edge Follow (RTEF), is capable of detecting the closed directions around the agent by analyzing the nearby obstacles, thus avoiding dead-ends in order to reach a static target more effectively. We compared RTEF with a well-known algorithm, Real-Time A* (RTA*) proposed by Korf, and observed significant improvement. The second algorithm, Real-Time Moving Target Evaluation Search (MTES), is also able to detect the closed directions similar to RTEF, but in addition, determines the estimated best direction that leads to a static or moving target from a shorter path. Employing this new algorithm, we obtain an impressive improvement over RTEF with respect to path length, but at the cost of extra computation. We compared our algorithms with Moving Target Search (MTS) developed by Ishida and the off-line path planning algorithm A*, and observed that MTES performs significanlty better than MTS, and offers solutions very close to optimal ones produced by A*. Finally, we present Multi-Agent Real-Time Pursuit (MAPS) for multiple predators to capture a moving prey cooperatively. MAPS introduces two new coordination strategies namely Blocking Escape Directions (BES) and Using Alternative Proposals (UAL), which help the predators waylay the possible escape directions of the prey in coordination. We compared our coordination strategies with the uncoordinated one, and observed an impressive reduction in the number of moves to catch the prey.

Navigation of a group of autonomous agents that are needed to maintain a formation is a challenging task which has not been studied much in especially 3-D terrains. This thesis presents a novel approach to collision free path finding of multiple agents preserving a predefined formation in a 3-D terrain. The proposed method could be used in many areas like navigation of semi-automated forces (SAF) at unit level in military simulations and non player characters (NPC) in computer games. The proposed path finding algorithm first computes an optimal path from an initial point to a target point after analyzing the 3-D terrain data from which it constructs a weighted graph. Then, it employs a real-time path finding algorithm specifically designed to realize the navigation of the group from one way point to the successive one on the optimal path generated at the previous stage, preserving the formation and avoiding collision both. A software was developed to test the methods discussed here.

Multiagent systems (MAS) are systems consisting of several autonomous entities, called agents, which interact with each other to either further their own interests (competition) or in pursuit of a joint goal (cooperation). In systems composed of multiple autonomous agents, negotiation is a key form of interaction that enables groups of agents to arrive at a mutual agreement regarding some belief, goal or plan. The aim of this thesis is to develop a multiagent system that simulates the negotiation process between parties about sharing of cost overrun in international construction projects. The developed tool can be used to understand how the risks and associated costs are shared between parties under different scenarios related with the risk allocation clauses in the contract, objectives of parties and level of knowledge about actual sources of cost overrun. MAS can be utilized by decision-makers to predict potential outcomes of a negotiation process.

The complexity of the path finding and navigation problem increases when multiple agents are involved and these agents have to maintain a predefined formation while moving on a 3-D terrain. In this thesis, a novel approach for multiresolution formation representation is proposed, that allows hierarchical formations of arbitrary depth to be defined using different referencing schemes. This formation representation approach is then utilized to find and realize a collision free optimal path from an initial location to a goal location on a 3-D terrain, while preserving the formation. The proposed metod first employs a terrain analysis technique that constructs a weighted search graph from height-map data. The graph is used by an off-line search algorithm to find the shortest path. The path is realized by an on-line planner, which guides the formation along the path while avoiding collisions and maintaining the formation. The methods proposed here are easily adaptable to several application areas, especially to real time strategy games and military simulations.

In this thesis, I propose an agent-based cooperative model for supply chains to commit orders by satisfying constraints. Due to the limitation of the real world environment, the centralized schedule model to handle constraint satisfaction is impractical, it is important to excise the distributed constraint satisfaction model to meet the outsourcing paradigm of supply chain management. I introduce a multi-agent system based coordination mechanism that integrates theories of negotiation and distributed constraint satisfaction problem to resolve the constraints in supply chain. I adopt the asynchronous weak-commitment search, a DCSP algorithm to resolve the global constraint in supply chain. Asynchronous weak-commitment search is complete backtracking algorithms that guarantee to find a solution if there is a solution existing and asynchronous weak-commitment search provide priority dynamic mechanism that help us to find a solution quickly than other backtracking algorithms. We construct a coordination agent for each business entity in supplier chain. The agent embedded in the ability to resolve the constraints autonomously. We expect this agent-based coordination mechanism can make supply chain more efficient and enhance supply chain's agility.

In the thesis, we provide a solution to solve a schema change problem. In a data warehouse system, if schema changes occur in a data source, the overall system will lose the consistency between the data sources and the data warehouse. These schema changes will render the data warehouse obsolete. We have developed three stages to handle schema changes occurring in databases. They are change detection, diagnosis, and handling. Recommendations are generated by DB-agent to information DW-agent to notify the DBA what and where a schema change affects the star schema. In the study, we mainly handle seven schema changes in a relational database. All of them, we not only handle non-adding schema changes but also handling adding schema changes. A non-adding schema change in our experiment has high correct mapping rate as using a traditional mappings between a data warehouse and a database. For an adding schema change, it has many uncertainties to diagnosis and handle. For this reason, we compare similarity between an adding relation or attribute and the ontology concept or concept attribute to generate a good recommendation. The evaluation results show that the proposed approach is capable to detect these schema changes correctly and to recommend the DBA about the changes appropriately.

With rapid development of information technology, the company can find and communicate with new partners easily, which makes the relation more complex and unstable. How to improve the performance of the supply chain is an important issue. In this study, we try to discuss the problem from the three factors including switching cost, trust and information sharing. First, we propose a conceptual model of switching cost, trust, information sharing and supply chain performance. The performance indexes include the average fulfillment rate, average stock cost, and average cycle time. Second, in order to verify the model, we construct a simulation environment of supply chain and construct a decision mechanism based on the conceptual model. Final, we observe the effect and variation of the different order demand environment, the different information sharing threshold, different propensity of switching cost and trust, and different product price and different producing technology.

Psychological studies have shown that information exchange is a key component of effective teamwork. In addition to requesting information that they need for their tasks, members of effective teams often proactively forward information that they believe other teammates require to complete their tasks. We refer to this type of communication as proactive information exchange and the formalization and implementation of this is the subject of this thesis. The important question that we are trying to answer is: under normative conditions, what types of information needs can agent teammates extract from shared plans and how can they use these information needs to proactively forward information to teammates? In the following, we make two key claims about proactive information exchange: first, agents need to be aware of the information needs of their teammates and that these information needs can be inferred from shared plans; second, agents need to be able to model the beliefs of others in order to deliver this information efficiently. To demonstrate this, we have developed an algorithm named PIEX, which, for each agent on a team, reasonably approximates the information-needs of other team members, based on analysis of a shared team plan. This algorithm transforms a team plan into an individual plan by inserting coomunicative tasks in agents' individual plans to deliver information to those agents who need it. We will incorporate a previously developed architecture for multi-agent belief reasoning. In addition to this algorithm for proactive information exchange, we have developed a formal framework to both describe scenarios in which proactive information exchange takes place and to evaluate the quality of the communication events that agents running the PIEX algorithm generate. The contributions of this work are a formal and implemented algorithm for information exchange for maintaining a shared mental model and a framework for evaluating domains in which this type of information exchange is useful.

We present methods for distributed self-assembly that utilize simple rule-of-thumb control and communication schemes providing probabilistic performance guarantees. These methods represents a staunch departure from existing approaches that require more sophisticated control and communication, but provide deterministic guarantees. In particular, we show that even under severe communication restrictions, any assembly described by an acyclic weighted graph can be assembled with a rule set that is linear in the number of nodes contained in the desired assembly graph. We introduce the concept of stochastic stability to the self-assembly problem and show that stochastic stability of desirable configurations can be exploited to provide probabilistic performance guarantees for the process. Relaxation of the communication restrictions allows simple approaches giving deterministic guarantees. We establish a clear relationship between availability of communication and convergence properties. We consider Self-assembly tasks for the cases of many and few agents as well as large and small assembly goals. We analyze sensitivity of the presented process to communication errors as well as ill-intentioned agents. We discuss convergence rates of the presented process and directions for improving them.

Many biological systems are known to accomplish complex tasks in a decentralized, robust, and scalable manner - characteristics that are desirable to the coordination of engineered systems as well. Inspired by nature, we produce coordination strategies for a network of heterogenous agents and in particular, we focus on intelligent collective systems. Bottlenose dolphins and African lions are examples of intelligent collective systems since they exhibit sophisticated social behaviors and effortlessly transition between functionalities. Through preferred associations, specialized roles, and self-organization, these systems forage prey, form alliances, and maintain sustainable group sizes. In this thesis, we take a three-phased approach to bioinspiration: in the first phase, we produce agent-based models of specific social behaviors observed in nature. The goal of these models is to capture the underlying biological phenomenon, yet remain simple so that the models are amenable to analysis. In the second phase, we produce bio-inspired algorithms that are based on the simple biological models produced in the first phase. Moreover, these algorithms are developed in the context of specific coordination tasks, e.g., the multi-agent foraging task. In the final phase of this work, we tailor these algorithms to produce coordination strategies that are ready to be deployed in target applications.