+publisher:"University of Michigan" +contributor:("Durfee, Edmund H")

University of Michigan

1. Sleight, Jason Lee. Agent-Driven Representations, Algorithms, and Metrics for Automated Organizational Design.

Degree: PhD, Computer Science and Engineering, 2015, University of Michigan

URL: http://hdl.handle.net/2027.42/113616

► As cooperative multiagent systems (MASs) increase in interconnectivity, complexity, size, and longevity, coordinating the agents' reasoning and behaviors becomes increasingly difficult. One approach to address… (more)

▼ As cooperative multiagent systems (MASs) increase in interconnectivity, complexity, size, and longevity, coordinating the agents' reasoning and behaviors becomes increasingly difficult. One approach to address these issues is to use insights from human organizations to design structures within which the agents can more efficiently reason and interact. Generally speaking, an organization influences each agent such that, by following its respective influences, an agent can make globally-useful local decisions without having to explicitly reason about the complete joint coordination problem. For example, an organizational influence might constrain and/or inform which actions an agent performs. If these influences are well-constructed to be cohesive and correlated across the agents, then each agent is influenced into reasoning about and performing only the actions that are appropriate for its (organizationally-designated) portion of the joint coordination problem. In this dissertation, I develop an agent-driven approach to organizations, wherein the foundation for representing and reasoning about an organization stems from the needs of the agents in the MAS. I create an organizational specification language to express the possible ways in which an organization could influence the agents' decision making processes, and leverage details from those decision processes to establish quantitative, principled metrics for organizational performance based on the expected impact that an organization will have on the agents' reasoning and behaviors. Building upon my agent-driven organizational representations, I identify a strategy for automating the organizational design process~(ODP), wherein my ODP computes a quantitative description of organizational patterns and then searches through those possible patterns to identify an (approximately) optimal set of organizational influences for the MAS. Evaluating my ODP reveals that it can create organizations that both influence the MAS into effective patterns of joint policies and also streamline the agents' decision making in a coordinate manner. Finally, I use my agent-driven approach to identify characteristics of effective abstractions over organizational influences and a heuristic strategy for converging on a good abstraction. Advisors/Committee Members: Durfee, Edmund H. (committee member), Cohn, Amy Ellen (committee member), Lesser, Victor R. (committee member), Baveja, Satinder Singh (committee member).

Subjects/Keywords: Artificial Intelligence; Multiagent Coordination; Organizational Design; Computer Science; Engineering

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Sleight, J. L. (2015). Agent-Driven Representations, Algorithms, and Metrics for Automated Organizational Design. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/113616

Chicago Manual of Style (16^th Edition):

Sleight, Jason Lee. “Agent-Driven Representations, Algorithms, and Metrics for Automated Organizational Design.” 2015. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/113616.

MLA Handbook (7^th Edition):

Sleight, Jason Lee. “Agent-Driven Representations, Algorithms, and Metrics for Automated Organizational Design.” 2015. Web. 04 Mar 2021.

Vancouver:

Sleight JL. Agent-Driven Representations, Algorithms, and Metrics for Automated Organizational Design. [Internet] [Doctoral dissertation]. University of Michigan; 2015. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/113616.

Council of Science Editors:

Sleight JL. Agent-Driven Representations, Algorithms, and Metrics for Automated Organizational Design. [Doctoral Dissertation]. University of Michigan; 2015. Available from: http://hdl.handle.net/2027.42/113616

University of Michigan

2. Strom, Johannes H. Online Mapping and Perception Algorithms for Multi-robot Teams Operating in Urban Environments.

Degree: PhD, Computer Science and Engineering, 2015, University of Michigan

URL: http://hdl.handle.net/2027.42/113516

► This thesis investigates some of the sensing and perception challenges faced by multi-robot teams equipped with LIDAR and camera sensors. Multi-robot teams are ideal for… (more)

▼ This thesis investigates some of the sensing and perception challenges faced by multi-robot teams equipped with LIDAR and camera sensors. Multi-robot teams are ideal for deployment in large, real-world environments due to their ability to parallelize exploration, reconnaissance or mapping tasks. However, such domains also impose additional requirements, including the need for a) online algorithms (to eliminate stopping and waiting for processing to finish before proceeding) and b) scalability (to handle data from many robots distributed over a large area). These general requirements give rise to specific algorithmic challenges, including 1) online maintenance of large, coherent maps covering the explored area, 2) online estimation of communication properties in the presence of buildings and other interfering structure, and 3) online fusion and segmentation of multiple sensors to aid in object detection. The contribution of this thesis is the introduction of novel approaches that leverage grid-maps and sparse multi-variate gaussian inference to augment the capability of multi-robot teams operating in urban, indoor-outdoor environments by improving the state of the art of map rasterization, signal strength prediction, colored point cloud segmentation, and reliable camera calibration. In particular, we introduce a map rasterization technique for large LIDAR-based occupancy grids that makes online updates possible when data is arriving from many robots at once. We also introduce new online techniques for robots to predict the signal strength to their teammates by combining LIDAR measurements with signal strength measurements from their radios. Processing fused LIDAR+camera point clouds is also important for many object-detection pipelines. We demonstrate a near linear-time online segmentation algorithm to this domain. However, maintaining the calibration of a fleet of 14 robots made this approach difficult to employ in practice. Therefore we introduced a robust and repeatable camera calibration process that grounds the camera model uncertainty in pixel error, allowing the system to guide novices and experts alike to reliably produce accurate calibrations. Advisors/Committee Members: Olson, Edwin (committee member), Eustice, Ryan M. (committee member), Durfee, Edmund H. (committee member), Hsieh, M. Ani (committee member).

Subjects/Keywords: field robotics; mapping; segmentation; camera calibration; signal-strength prediction; occupancy-grid; Computer Science; Engineering

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Strom, J. H. (2015). Online Mapping and Perception Algorithms for Multi-robot Teams Operating in Urban Environments. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/113516

Chicago Manual of Style (16^th Edition):

Strom, Johannes H. “Online Mapping and Perception Algorithms for Multi-robot Teams Operating in Urban Environments.” 2015. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/113516.

MLA Handbook (7^th Edition):

Strom, Johannes H. “Online Mapping and Perception Algorithms for Multi-robot Teams Operating in Urban Environments.” 2015. Web. 04 Mar 2021.

Vancouver:

Strom JH. Online Mapping and Perception Algorithms for Multi-robot Teams Operating in Urban Environments. [Internet] [Doctoral dissertation]. University of Michigan; 2015. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/113516.

Council of Science Editors:

Strom JH. Online Mapping and Perception Algorithms for Multi-robot Teams Operating in Urban Environments. [Doctoral Dissertation]. University of Michigan; 2015. Available from: http://hdl.handle.net/2027.42/113516

University of Michigan

3. Zhang, Shun. Efficiently Finding Approximately-Optimal Queries for Improving Policies and Guaranteeing Safety.

Degree: PhD, Computer Science & Engineering, 2020, University of Michigan

URL: http://hdl.handle.net/2027.42/163125

► When a computational agent (called the “robot”) takes actions on behalf of a human user, it may be uncertain about the human’s preferences. The human… (more)

▼ When a computational agent (called the “robot”) takes actions on behalf of a human user, it may be uncertain about the human’s preferences. The human may initially specify her preferences incompletely or inaccurately. In this case, the robot’s performance may be unsatisfactory or even cause negative side effects to the environment. There are approaches in the literature that may solve this problem. For example, the human can provide some demonstrations which clarify the robot’s uncertainty. The human may give real-time feedback to the robot’s behavior, or monitor the robot and stop the robot when it may perform anything dangerous. However, these methods typically require much of the human’s attention. Alternatively, the robot may estimate the human’s true preferences using the specified preferences, but this is error-prone and requires making assumptions on how the human specifies her preferences. In this thesis, I consider a querying approach. Before taking any actions, the robot has a chance to query the human about her preferences. For example, the robot may query the human about which trajectory in a set of trajectories she likes the most, or whether the human cares about some side effects to the domain. After the human responds to the query, the robot expects to improve its performance and/or guarantee that its behavior is considered safe by the human. If we do not impose any constraint on the number of queries the robot can pose, the robot may keep posing queries until it is absolutely certain about the human’s preferences. This may consume too much of the human’s cognitive load. The information obtained in the responses to some of the queries may only marginally improve the robot’s performance, which is not worth the human’s attention at all. So in the problems considered in this thesis, I constrain the number of queries that the robot can pose, or associate each query with a cost. The research question is how to efficiently find the most useful query under such constraints. Finding a provably optimal query can be challenging since it is usually a combinatorial optimization problem. In this thesis, I contribute to providing efficient query selection algorithms under uncertainty. I first formulate the robot’s uncertainty as reward uncertainty and safety-constraint uncertainty. Under only reward uncertainty, I provide a query selection algorithm that finds approximately-optimal k-response queries. Under only safety-constraint uncertainty, I provide a query selection algorithm that finds an optimal k-element query to improve a known safe policy, and an algorithm that uses a set-cover-based query selection strategy to find an initial safe policy. Under both types of uncertainty simultaneously, I provide a batch-query-based querying method that empirically outperforms other baseline querying methods. Advisors/Committee Members: Baveja, Satinder Singh (committee member), Durfee, Edmund H (committee member), Lewis, Richard L (committee member), Lasecki, Walter (committee member).

Subjects/Keywords: human-agent interaction; Markov decisions processes; query selection algorithms; planning under uncertainty; Computer Science; Engineering

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Zhang, S. (2020). Efficiently Finding Approximately-Optimal Queries for Improving Policies and Guaranteeing Safety. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/163125

Chicago Manual of Style (16^th Edition):

Zhang, Shun. “Efficiently Finding Approximately-Optimal Queries for Improving Policies and Guaranteeing Safety.” 2020. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/163125.

MLA Handbook (7^th Edition):

Zhang, Shun. “Efficiently Finding Approximately-Optimal Queries for Improving Policies and Guaranteeing Safety.” 2020. Web. 04 Mar 2021.

Vancouver:

Zhang S. Efficiently Finding Approximately-Optimal Queries for Improving Policies and Guaranteeing Safety. [Internet] [Doctoral dissertation]. University of Michigan; 2020. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/163125.

Council of Science Editors:

Zhang S. Efficiently Finding Approximately-Optimal Queries for Improving Policies and Guaranteeing Safety. [Doctoral Dissertation]. University of Michigan; 2020. Available from: http://hdl.handle.net/2027.42/163125

University of Michigan

4. Zhang, Qi. Making and Keeping Probabilistic Commitments for Trustworthy Multiagent Coordination.

Degree: PhD, Computer Science & Engineering, 2020, University of Michigan

URL: http://hdl.handle.net/2027.42/162948

► In a large number of real world domains, such as the control of autonomous vehicles, team sports, medical diagnosis and treatment, and many others, multiple… (more)

▼ In a large number of real world domains, such as the control of autonomous vehicles, team sports, medical diagnosis and treatment, and many others, multiple autonomous agents need to take actions based on local observations, and are interdependent in the sense that they rely on each other to accomplish tasks. Thus, achieving desired outcomes in these domains requires interagent coordination. The form of coordination this thesis focuses on is commitments, where an agent, referred to as the commitment provider, specifies guarantees about its behavior to another, referred to as the commitment recipient, so that the recipient can plan and execute accordingly without taking into account the details of the provider's behavior. This thesis grounds the concept of commitments into decision-theoretic settings where the provider's guarantees might have to be probabilistic when its actions have stochastic outcomes and it expects to reduce its uncertainty about the environment during execution. More concretely, this thesis presents a set of contributions that address three core issues for commitment-based coordination: probabilistic commitment adherence, interpretation, and formulation. The first contribution is a principled semantics for the provider to exercise maximal autonomy that responds to evolving knowledge about the environment without violating its probabilistic commitment, along with a family of algorithms for the provider to construct policies that provably respect the semantics and make explicit tradeoffs between computation cost and plan quality. The second contribution consists of theoretical analyses and empirical studies that improve our understanding of the recipient's interpretation of the partial information specified in a probabilistic commitment; the thesis shows that it is inherently easier for the recipient to robustly model a probabilistic commitment where the provider promises to enable preconditions that the recipient requires than where the provider instead promises to avoid changing already-enabled preconditions. The third contribution focuses on the problem of formulating probabilistic commitments for the fully cooperative provider and recipient; the thesis proves structural properties of the agents' values as functions of the parameters of the commitment specification that can be exploited to achieve orders of magnitude less computation for 1) formulating optimal commitments in a centralized manner, and 2) formulating (approximately) optimal queries that induce (approximately) optimal commitments for the decentralized setting in which information relevant to optimization is distributed among the agents. Advisors/Committee Members: Baveja, Satinder Singh (committee member), Durfee, Edmund H (committee member), Lewis, Richard L (committee member), Sinha, Arunesh (committee member).

Subjects/Keywords: Multiagent Coordination; Sequential Decision Making; Commitment; Markov Decision Process; Computer Science; Engineering

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Zhang, Q. (2020). Making and Keeping Probabilistic Commitments for Trustworthy Multiagent Coordination. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/162948

Chicago Manual of Style (16^th Edition):

Zhang, Qi. “Making and Keeping Probabilistic Commitments for Trustworthy Multiagent Coordination.” 2020. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/162948.

MLA Handbook (7^th Edition):

Zhang, Qi. “Making and Keeping Probabilistic Commitments for Trustworthy Multiagent Coordination.” 2020. Web. 04 Mar 2021.

Vancouver:

Zhang Q. Making and Keeping Probabilistic Commitments for Trustworthy Multiagent Coordination. [Internet] [Doctoral dissertation]. University of Michigan; 2020. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/162948.

Council of Science Editors:

Zhang Q. Making and Keeping Probabilistic Commitments for Trustworthy Multiagent Coordination. [Doctoral Dissertation]. University of Michigan; 2020. Available from: http://hdl.handle.net/2027.42/162948

University of Michigan

5. Cox, Jeffrey S. Efficient methods for solving the multiagent plan coordination problem.

Degree: PhD, Computer science, 2005, University of Michigan

URL: http://hdl.handle.net/2027.42/125333

► The Multiagent Plan Coordination Problem arises whenever multiple agents plan to achieve their individual goals independently, but might mutually benefit by coordinating their plans to… (more)

▼ The Multiagent Plan Coordination Problem arises whenever multiple agents plan to achieve their individual goals independently, but might mutually benefit by coordinating their plans to avoid working at cross purposes or duplicating effort. Although variations of this problem have been studied in the literature, there is as yet no agreement over a general characterization of the problem. In this dissertation, I describe a general framework that extends the partial-order, causal-link plan representation to the multiagent case, and that treats coordination as a form of iterative repair of plan flaws between agents. I show, analytically and empirically, that this algorithmic formulation can scale to the multiagent case better than can a straightforward application of the most advanced existing coordination techniques, highlighting fundamental differences between my algorithmic framework and these earlier approaches. I then examine whether and how the Multiagent Plan Coordination Problem can be cast as a Distributed Constraint Optimization Problem (DCOP). I use ADOPT, a state-of-the-art system that can solve DCOPs in an asynchronous, parallel manner using local communication between individual computational agents. I extend the ADOPT framework to take advantage of problem structure, in an effort to improve its performance on representative Multiagent Plan Coordination Problems. Although the performance gains from using ADOPT were negligible, I show how the same problem structure can be used to enable my algorithm to operate more efficiently. In the interest of scaling my approaches to larger problems, I build on previous work in the area of multiagent coordination [8] to make use of abstraction techniques that create hierarchical planning structures that are decomposed into primitive actions. By exploiting past work on developing summary information at abstract levels of agent plan hierarchies, I then extend my coordination algorithm to reason about agent interactions at abstract levels of the agents' plan hierarchies, and empirically establish that this technique greatly reduces the amount of computation required to derive coordinated planning solutions for the agents. I conclude with a discussion of possible ways of extending my work to handle richer and alternative plan coordination problems. Advisors/Committee Members: Durfee, Edmund H. (advisor).

Subjects/Keywords: Artificial Intelligence; Coordination; Efficient; Methods; Multiagent; Plan; Planning; Problem; Solving

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Cox, J. S. (2005). Efficient methods for solving the multiagent plan coordination problem. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/125333

Chicago Manual of Style (16^th Edition):

Cox, Jeffrey S. “Efficient methods for solving the multiagent plan coordination problem.” 2005. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/125333.

MLA Handbook (7^th Edition):

Cox, Jeffrey S. “Efficient methods for solving the multiagent plan coordination problem.” 2005. Web. 04 Mar 2021.

Vancouver:

Cox JS. Efficient methods for solving the multiagent plan coordination problem. [Internet] [Doctoral dissertation]. University of Michigan; 2005. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/125333.

Council of Science Editors:

Cox JS. Efficient methods for solving the multiagent plan coordination problem. [Doctoral Dissertation]. University of Michigan; 2005. Available from: http://hdl.handle.net/2027.42/125333

University of Michigan

6. Huber, Marcus James. Plan-based plan recognition models for the effective coordination of agents through observation.

Degree: PhD, Computer science, 1996, University of Michigan

URL: http://hdl.handle.net/2027.42/130017

► Our research is aimed at providing agents with the ability to use observations of actions taken by others not only to recognize current actions but… (more)

▼ Our research is aimed at providing agents with the ability to use observations of actions taken by others not only to recognize current actions but also to infer ongoing plans and goals, a process called plan recognition. Once our agents can recognize the plans and goals of others, they can then employ a number of techniques for coordinating their planned actions with those of others. Multi-agent coordination has typically been performed using explicit communication between agents. Plan recognition offers several potential advantages over explicit communication however, including lower communication overhead, higher reliability, greater information content, and robustness in the face of agents who are not forthcoming about their plans. On the other hand, it also has potential disadvantages, including the fact that agents need to know how other agents act in pursuit of their goals, that actions might not be accurately observable or might support multiple possible plans, and that inferring the plans of others can be more time consuming than being told explicitly by them. In this research, we have developed a probabilistic plan recognition model called a plan recognition network (PRN) and a computational system called ASPRN (Automated Synthesis of Plan Recognition Networks) that can automatically construct a PRN from a plan model. PRNs provide an observing agent with a wide range of inferred information and handle the uncertainty associated with plan recognition and observations in a natural, robust manner. We demonstrate that plan recognition can be done in a competitive, real-time, simulated environment such that plan recognizing agents win up to 90% of the time, despite the inherent overhead and uncertainty of the recognition process. Our experiments reveal that even though PRNs provide numeric information, they may currently be more amenable to symbolic reasoning method than decision-theoretic approaches. Other experiments highlight that waiting for plan recognition information to become more certain before acting upon it reduces coordination performance because of the delay before imitation of coordination activities. Analysis of our experiments also highlights that the temporal distribution of observations while performing plan recognition has a distinctly negative impact upon the observing agent's ability to effectively coordinate as the distribution is pushed later toward the end of plan execution. Lastly, our experiments show us that coordinating agents can take advantage of plans with early plan disambiguation points and that plans with late plan disambignation points may hinder effective plan recognition-based coordination. Advisors/Committee Members: Durfee, Edmund H. (advisor).

Subjects/Keywords: Agents; Artificial Intelligence; Based; Belief Networks; Coordination; Effective; Models; Observation; Plan; Procedural Reasoning; Recognition

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Huber, M. J. (1996). Plan-based plan recognition models for the effective coordination of agents through observation. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/130017

Chicago Manual of Style (16^th Edition):

Huber, Marcus James. “Plan-based plan recognition models for the effective coordination of agents through observation.” 1996. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/130017.

MLA Handbook (7^th Edition):

Huber, Marcus James. “Plan-based plan recognition models for the effective coordination of agents through observation.” 1996. Web. 04 Mar 2021.

Vancouver:

Huber MJ. Plan-based plan recognition models for the effective coordination of agents through observation. [Internet] [Doctoral dissertation]. University of Michigan; 1996. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/130017.

Council of Science Editors:

Huber MJ. Plan-based plan recognition models for the effective coordination of agents through observation. [Doctoral Dissertation]. University of Michigan; 1996. Available from: http://hdl.handle.net/2027.42/130017

University of Michigan

7. Vidal, Jose M. Computational agents that learn about agents: Algorithms for their design and a predictive theory of their behavior.

Degree: PhD, Computer science, 1998, University of Michigan

URL: http://hdl.handle.net/2027.42/131343

► In this thesis, we show how to build agents that learn about agents in Multi-Agent Systems (MASs) composed of learning agents. We give a framework… (more)

▼ In this thesis, we show how to build agents that learn about agents in Multi-Agent Systems (MASs) composed of learning agents. We give a framework for describing a MAS and its agents, along with their behaviors and the errors in these behaviors. The framework is supplemented with notation that captures the knowledge of agents with recursive models of other agents. Working under the assumption that agents can generate recursive models of other agents, we design an algorithm (LR-RMM) that works by calculating an agent's expected gain in order to tell the agent when it should stop thinking about other agents and take action. We implement LR-RMM and verify its results in the Pursuit Task. We then consider agents that must learn models of other agents via observation. We extend our framework (CLRI) to capture the agents' learning abilities, regardless of the particular machine learning algorithms used by the agents, and the degree to which the agents impact each others' behaviors. CLRI predicts the correctness of the expected behavior of any learning agent in a MAS. Since agents impact each other, an agent's desired behavior might change due to changes in the other agents' behaviors, as caused by their learning. The CLRI framework takes all these changes into account when predicting the correctness of an agent's expected behavior. We confirm the CLRI predictions with experimental results from our research and from the research literature. While determining the CLRI parameter values requires an analysis of the agent's implementation, we use computational learning theory to calculate bounds on some of these parameters. These bounds apply regardless of the agent's learning algorithm. Finally, we study a specific market-based MAS in detail. We confirm the agents' behaviors, as predicted by the CLRI framework, and present other findings specific to market-based MASs, such as the fact that learning agents make the system more robust to the presence of malicious agents, and that agents can expect decreasing returns for increasing levels of strategic thinking. Advisors/Committee Members: Durfee, Edmund H. (advisor).

Subjects/Keywords: Algorithms; Behavior; Computational Agents; Design; Learn; Learning Agents; Predictive; Recursive Models; Theory

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Vidal, J. M. (1998). Computational agents that learn about agents: Algorithms for their design and a predictive theory of their behavior. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/131343

Chicago Manual of Style (16^th Edition):

Vidal, Jose M. “Computational agents that learn about agents: Algorithms for their design and a predictive theory of their behavior.” 1998. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/131343.

MLA Handbook (7^th Edition):

Vidal, Jose M. “Computational agents that learn about agents: Algorithms for their design and a predictive theory of their behavior.” 1998. Web. 04 Mar 2021.

Vancouver:

Vidal JM. Computational agents that learn about agents: Algorithms for their design and a predictive theory of their behavior. [Internet] [Doctoral dissertation]. University of Michigan; 1998. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/131343.

Council of Science Editors:

Vidal JM. Computational agents that learn about agents: Algorithms for their design and a predictive theory of their behavior. [Doctoral Dissertation]. University of Michigan; 1998. Available from: http://hdl.handle.net/2027.42/131343

University of Michigan

8. Sen, Sandip. Predicting tradeoffs in contract-based distributed scheduling.

Degree: PhD, Computer Science and Engineering, 1993, University of Michigan

URL: http://hdl.handle.net/2027.42/103842

► We are interested in building intelligent, autonomous software agents that can relieve human users from the burden of routine, tedious information processing activities in organizations.… (more)

▼ We are interested in building intelligent, autonomous software agents that can relieve human users from the burden of routine, tedious information processing activities in organizations. As part of that research agenda, we present in this thesis results of our investigations in building autonomous agents for the problem domain of distributed scheduling. In particular, we have analyzed in detail the real-life domain of distributed meeting scheduling, in which autonomous, partially cooperative meeting scheduling agents negotiate with each other to schedule dynamically arriving meeting requests. To be effective and useful in such domains, autonomous agents need to use a structured information exchange mechanism that helps them quickly identify solutions to individual and global goals, as well as provide the capability to explain their actions to associated users on demand. Our agents achieve these capabilities by using the contract-net protocol, which has been used widely to coordinate the activities of agents in distributed problem-solving systems. To effectively implement this protocol in the distributed scheduling domain, we address each of the critical problem-solving aspects of a contracting agent: how to structure and search for contract proposals in the solution space, how much information to exchange to quickly converge the negotiation process without incurring excessive communication cost, how to bid effectively against announced contracts, how to represent and reason about tentative proposals, and when to withdraw past commitments if faced with new contingencies. We investigate heuristic strategy dimensions to control each of the above aspects of local problem solving. By using a finite state automata model of contracting agents, we precisely represent the processing stages, the resource requirements, and the interaction possibilities between meeting scheduling agents. We also develop probabilistic estimates of the performance of heuristic strategy options under a variety of environmental and local problem-solving conditions. We demonstrate the necessity of adaptive scheduling by showing that a static choice of strategy combinations leads to increasingly ineffective problem solving over time. As a remedial measure, we outline the design of an intelligent, adaptive scheduling agent that chooses from available strategy options to optimize certain performance measures for each new meeting it is asked to schedule. Advisors/Committee Members: Durfee, Edmund H. (advisor).

Subjects/Keywords: Computer Science

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Sen, S. (1993). Predicting tradeoffs in contract-based distributed scheduling. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/103842

Chicago Manual of Style (16^th Edition):

Sen, Sandip. “Predicting tradeoffs in contract-based distributed scheduling.” 1993. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/103842.

MLA Handbook (7^th Edition):

Sen, Sandip. “Predicting tradeoffs in contract-based distributed scheduling.” 1993. Web. 04 Mar 2021.

Vancouver:

Sen S. Predicting tradeoffs in contract-based distributed scheduling. [Internet] [Doctoral dissertation]. University of Michigan; 1993. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/103842.

Council of Science Editors:

Sen S. Predicting tradeoffs in contract-based distributed scheduling. [Doctoral Dissertation]. University of Michigan; 1993. Available from: http://hdl.handle.net/2027.42/103842

University of Michigan

9. Montgomery, Thomas Anthony. The use of abstraction in coordinating artificially intelligent agents.

Degree: PhD, Computer Science and Engineering, 1993, University of Michigan

URL: http://hdl.handle.net/2027.42/103458

► The coordination of networked computer systems (and of other distributed intelligent agents) is becoming an increasingly important area of research. By viewing the process of… (more)

▼ The coordination of networked computer systems (and of other distributed intelligent agents) is becoming an increasingly important area of research. By viewing the process of coordination as a distributed search, we are able to adapt recent research on search – and how its complexity can be reduced through the use of abstraction – to the coordination of intelligent agents. We do this using a framework which allows our intelligent agents to reason and communicate at multiple levels of abstraction. Communication is necessary in a distributed search since each agent only searches a fraction of the overall space. By beginning dialogues at an abstract level, our intelligent agents can reduce the amount of information that they must communicate when coordinating their actions. Any reduction in information exchanged that is accomplished by this hierarchical communication reduces both the transmission load on the communication medium, and the processing load on the agents. However, since there is some overhead associated with sending abstract information, we describe the circumstances under which hierarchical communication results in the transmission of less information than the brute force approach of exchanging all details. Extending hierarchical communication to the level of teams of agents, and allowing the teams to negotiate in parallel, makes further efficiency gains possible. In general, the combined effects of parallelism and abstraction can reduce the complexity of an exponential search to logarithmic time. By recognizing that a hierarchical organization of teams of agents can map onto more common abstraction hierarchies in search, we are able to show how this complexity reduction can be applied to the coordination problem. We validate our analysis through empirical results at both the task-level (in the Towers of Hanoi problem domain) and meta-level (in the coordination of robots in a delivery task). Since this research requires the distinctions between schedules, plans, and organizations to be blurred, it is a step toward an interdisciplinary study of coordination that includes such diverse fields as operations research, artificial intelligence, and organization theory. Advisors/Committee Members: Durfee, Edmund H. (advisor).

Subjects/Keywords: Artificial Intelligence; Computer Science

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Montgomery, T. A. (1993). The use of abstraction in coordinating artificially intelligent agents. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/103458

Chicago Manual of Style (16^th Edition):

Montgomery, Thomas Anthony. “The use of abstraction in coordinating artificially intelligent agents.” 1993. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/103458.

MLA Handbook (7^th Edition):

Montgomery, Thomas Anthony. “The use of abstraction in coordinating artificially intelligent agents.” 1993. Web. 04 Mar 2021.

Vancouver:

Montgomery TA. The use of abstraction in coordinating artificially intelligent agents. [Internet] [Doctoral dissertation]. University of Michigan; 1993. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/103458.

Council of Science Editors:

Montgomery TA. The use of abstraction in coordinating artificially intelligent agents. [Doctoral Dissertation]. University of Michigan; 1993. Available from: http://hdl.handle.net/2027.42/103458

University of Michigan

10. Pappachan, Pradeep M. Coordinating plan execution in dynamic multiagent environments.

Degree: PhD, Computer science, 2002, University of Michigan

URL: http://hdl.handle.net/2027.42/130344

► Autonomous agents operating in shared, dynamic environments need to coordinate their plans to preclude negative interactions. In this dissertation, we describe an online algorithm that… (more)

Subjects/Keywords: Autonomous Agents; Coordinating; Coordination; Dynamic; Environments; Multiagent; Plan Execution

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Pappachan, P. M. (2002). Coordinating plan execution in dynamic multiagent environments. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/130344

Chicago Manual of Style (16^th Edition):

Pappachan, Pradeep M. “Coordinating plan execution in dynamic multiagent environments.” 2002. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/130344.

MLA Handbook (7^th Edition):

Pappachan, Pradeep M. “Coordinating plan execution in dynamic multiagent environments.” 2002. Web. 04 Mar 2021.

Vancouver:

Pappachan PM. Coordinating plan execution in dynamic multiagent environments. [Internet] [Doctoral dissertation]. University of Michigan; 2002. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/130344.

Council of Science Editors:

Pappachan PM. Coordinating plan execution in dynamic multiagent environments. [Doctoral Dissertation]. University of Michigan; 2002. Available from: http://hdl.handle.net/2027.42/130344

University of Michigan

11. Brooks, Christopher H. Niche formation and efficient learning of consumer preferences in a dynamic information economy.

Degree: PhD, Computer science, 2002, University of Michigan

URL: http://hdl.handle.net/2027.42/123134

► In many multiagent systems, agents are required to solve a generalization of the connection problem, locating other agents that they want to interact with. This… (more)

▼ In many multiagent systems, agents are required to solve a generalization of the connection problem, locating other agents that they want to interact with. This can require an agent to learn about the other agents in a population. When this learning is costly, a tradeoff results between the quality of the connection and the time needed to discover this connection. In this thesis, we examine the problem of computational agents attempting to solve the connection problem within the context of an information economy. This leads us to an examination of niche formation, where an agent that is selling information goods must decide to which subset (or niche) of the consumer population it wishes to sell. We study this problem at several levels. Initially, we consider a monopolist interacting with a consumer population and ask how it can best learn what prices to charge. Different models of the consumer population approximate the consumer demand to different degrees of precision. When learning is costly, an agent must trade off the profit captured by different models of a population against the time needed to learn these models. In many cases, an agent must also consider other agents that are simultaneously learning. We examine this problem within the context of two producer agents that are simultaneously learning price schedules. When producers selling identical goods can compete only on price, a price war emerges. When producers can differentiate themselves through the use of different schedules and the consumer population is sufficiently heterogeneous, the decision as to whether to engage in a price war can be formulated as a Hawk-Dove game. When producers must learn and learning is costly, niches become even more attractive compared to a price war. A key to producers being able to successfully target separate niches is their ability to differentiate themselves. One way to do this is through the selection of categories of goods to offer. When producers compete in category space, the incentive to target separate niches, rather than to act as generalists and try to appeal to the entire population, depends upon both the way the consumer population evolves and the cost consumers incur for determining a good's value. We then turn to the problem of niche formation in the large, when many producers and consumers are learning simultaneously. We refer to this as congregating. We present a model of congregations and characterize the difficulty of congregating, both in the affinity group domain and in an information economy. When agents must pay a search cost in order to allocate goods, congregating both improves net profit and allows a multiagent system to scale to large numbers of agents. Advisors/Committee Members: Durfee, Edmund H. (advisor).

Subjects/Keywords: Consumer Preferences; Dynamic; Economy; Efficient; Electronic Commerce; Information; Learning; Multiagent; Niche Formation

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Brooks, C. H. (2002). Niche formation and efficient learning of consumer preferences in a dynamic information economy. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/123134

Chicago Manual of Style (16^th Edition):

Brooks, Christopher H. “Niche formation and efficient learning of consumer preferences in a dynamic information economy.” 2002. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/123134.

MLA Handbook (7^th Edition):

Brooks, Christopher H. “Niche formation and efficient learning of consumer preferences in a dynamic information economy.” 2002. Web. 04 Mar 2021.

Vancouver:

Brooks CH. Niche formation and efficient learning of consumer preferences in a dynamic information economy. [Internet] [Doctoral dissertation]. University of Michigan; 2002. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/123134.

Council of Science Editors:

Brooks CH. Niche formation and efficient learning of consumer preferences in a dynamic information economy. [Doctoral Dissertation]. University of Michigan; 2002. Available from: http://hdl.handle.net/2027.42/123134

University of Michigan

12. Clement, Bradley Jefferson. Abstract reasoning for multiagent coordination and planning.

Degree: PhD, Computer science, 2002, University of Michigan

URL: http://hdl.handle.net/2027.42/129322

► As autonomous software and robotic systems (or agents) grow in complexity, they will increasingly need to communicate and coordinate with each other. These agents will… (more)

▼ As autonomous software and robotic systems (or agents) grow in complexity, they will increasingly need to communicate and coordinate with each other. These agents will need planned courses of action to achieve their goals while sharing limited resources. This dissertation addresses the problem of efficiently interleaving planning and coordination for multiple agents. As part of my approach, I represent agents as having hierarchies of tasks that can be decomposed into executable primitive actions. Using task hierarchies, an agent can reason efficiently about its own goals and tasks (and those of others) at multiple levels of abstraction. By exploiting hierarchy, these agents can make planning and coordination decisions while avoiding complex computation involving unnecessary details of their tasks. To reason at abstract levels, agents must be aware of the constraints an abstract task embodies in its potential decompositions. Thus, I provide algorithms that summarize these constraints (represented as propositional state conditions and metric resource us ages) for each abstract task in an agent's library of hierarchical plans. This summary information can be derived offline for a domain of problems and used for any instance of tasks (or plans) assigned to the agents during coordination and planning. I also provide algorithms for reasoning about the concurrent interactions of abstract tasks, for identifying conflicts, and for resolving them. I use these algorithms to build sound and complete refinement-based coordination and planning algorithms. I also integrate summary information with a local search planner/scheduler, showing how the benefits can be extended to different classes of planning algorithms. Complexity analyses and experiments show where abstract reasoning using summary information can reduce computation and communication exponentially along a number of dimensions for coordination, planning, and scheduling in finding a single agent's plan or in optimally coordinating the plans of multiple agents. In addition, I provide pruning techniques and heuristics for decomposition that can further dramatically reduce computation. Overall, the techniques developed in this thesis enable researchers and system designers to scale the capabilities of interleaved coordination, planning, and execution by providing agents with tools to reason efficiently about their plans at multiple levels of abstraction. Advisors/Committee Members: Durfee, Edmund H. (advisor).

Subjects/Keywords: Abstract Reasoning; Artificial Intelligence; Autonomous Software; Coordination; Multiagent; Planning; Robotics; Scheduling

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Clement, B. J. (2002). Abstract reasoning for multiagent coordination and planning. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/129322

Chicago Manual of Style (16^th Edition):

Clement, Bradley Jefferson. “Abstract reasoning for multiagent coordination and planning.” 2002. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/129322.

MLA Handbook (7^th Edition):

Clement, Bradley Jefferson. “Abstract reasoning for multiagent coordination and planning.” 2002. Web. 04 Mar 2021.

Vancouver:

Clement BJ. Abstract reasoning for multiagent coordination and planning. [Internet] [Doctoral dissertation]. University of Michigan; 2002. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/129322.

Council of Science Editors:

Clement BJ. Abstract reasoning for multiagent coordination and planning. [Doctoral Dissertation]. University of Michigan; 2002. Available from: http://hdl.handle.net/2027.42/129322

University of Michigan

13. Lee, Jaeho. An explicit semantics for coordinated multiagent plan execution.

Degree: PhD, Computer science, 1997, University of Michigan

URL: http://hdl.handle.net/2027.42/130286

► An agent coordinating with another needs a model of the other agent to avoid interference or to promote cooperation. Generally, a model consists of both… (more)

Subjects/Keywords: Coordinated; Execution; Explicit; Multiagent; Plan; Semantics

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Lee, J. (1997). An explicit semantics for coordinated multiagent plan execution. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/130286

Chicago Manual of Style (16^th Edition):

Lee, Jaeho. “An explicit semantics for coordinated multiagent plan execution.” 1997. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/130286.

MLA Handbook (7^th Edition):

Lee, Jaeho. “An explicit semantics for coordinated multiagent plan execution.” 1997. Web. 04 Mar 2021.

Vancouver:

Lee J. An explicit semantics for coordinated multiagent plan execution. [Internet] [Doctoral dissertation]. University of Michigan; 1997. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/130286.

Council of Science Editors:

Lee J. An explicit semantics for coordinated multiagent plan execution. [Doctoral Dissertation]. University of Michigan; 1997. Available from: http://hdl.handle.net/2027.42/130286

University of Michigan

14. Dolgov, Dmitri A. Integrated resource allocation and planning in stochastic multiagent environments.

Degree: PhD, Computer science, 2006, University of Michigan

URL: http://hdl.handle.net/2027.42/126015

► Resource allocation is a ubiquitous problem that arises whenever scarce resources have to be distributed among multiple autonomous entities (e.g., people, companies, robots). Stochastic planning… (more)

▼ Resource allocation is a ubiquitous problem that arises whenever scarce resources have to be distributed among multiple autonomous entities (e.g., people, companies, robots). Stochastic planning is also a very common problem that focuses on developing models and algorithms for behaving optimally in uncertain environments. The motivation for this dissertation is that the problems of resource allocation and stochastic planning are often very strongly intertwined: the utility for acquiring some resources is commonly determined by what goals can be achieved using these resources, while devising the best course of action for achieving these goals can involve solving a complex stochastic planning problem. An integrated approach to modeling and solving the problems of resource allocation and stochastic planning allows us to exploit problem structure that would otherwise be lost if the problems were considered separately. The overarching goal of this dissertation is to develop computationally efficient mechanisms for allocating consumable and non-consumable resources among agents whose preferences for these resources are induced by stochastic planning problems. Towards this end, we develop new models of planning problems, based on the framework of Markov decision processes (MDPs), where the action sets are explicitly parameterized by the available resources. Given these models, we design algorithms based on linear and integer programming that simultaneously solve for optimal allocations of resources and strategies for acting in the stochastic environments. These algorithms then form the core of our mechanisms for allocating resources in cooperative as well as competitive multiagent settings. We show analytically and empirically that the integrated approach leads to drastic (in many cases, exponential) improvements in computational efficiency over methods that consider the problems separately. To complement the above, we develop mechanisms that, in addition to exploiting structure in agents' preferences arising from regularities in the underlying planning problems, also exploit structure within the agents' MDPs. By utilizing and extending techniques based on approximate linear programming, we adapt our resource-allocation mechanisms to well-structured planning problems, represented as factored MDPs. This leads to algorithms that scale up to even larger resource-allocation problems, where the agents' preferences are induced by MDPs with extremely large state spaces. Advisors/Committee Members: Durfee, Edmund H. (advisor).

Subjects/Keywords: Artificial Intelligence; Environments; Integrated; Markov Decision Processes; Planning; Resource Allocation; Stochastic Multiagent

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Dolgov, D. A. (2006). Integrated resource allocation and planning in stochastic multiagent environments. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/126015

Chicago Manual of Style (16^th Edition):

Dolgov, Dmitri A. “Integrated resource allocation and planning in stochastic multiagent environments.” 2006. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/126015.

MLA Handbook (7^th Edition):

Dolgov, Dmitri A. “Integrated resource allocation and planning in stochastic multiagent environments.” 2006. Web. 04 Mar 2021.

Vancouver:

Dolgov DA. Integrated resource allocation and planning in stochastic multiagent environments. [Internet] [Doctoral dissertation]. University of Michigan; 2006. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/126015.

Council of Science Editors:

Dolgov DA. Integrated resource allocation and planning in stochastic multiagent environments. [Doctoral Dissertation]. University of Michigan; 2006. Available from: http://hdl.handle.net/2027.42/126015

15. Wolfe, Britton D. Modeling Dynamical Systems with Structured Predictive State Representations.

Degree: PhD, Computer Science & Engineering, 2009, University of Michigan

URL: http://hdl.handle.net/2027.42/64601

► Predictive state representations (PSRs) are a class of models that represent the state of a dynamical system as a set of predictions about future events.… (more)

▼ Predictive state representations (PSRs) are a class of models that represent the state of a dynamical system as a set of predictions about future events. PSRs can model partially observable, stochastic dynamical systems, including any system that can be modeled by a finite partially observable Markov decision process (POMDP). Using PSR models can help an artificial intelligence agent learn an accurate model of its environment (which is a dynamical system) from its experience in that environment. Specifically, I present the suffix-history algorithm and demonstrate that it can learn PSR models that are generally more accurate than POMDP models learned from the same amount of experience. The suffix-history algorithm learns a type of PSR called the linear PSR. However, it is intractable to learn a linear PSR (or a POMDP) to model large systems because these models do not take advantage of regularities or structure in the environment. Therefore, I present three new classes of PSR models that exploit different types of structure in an environment: hierarchical PSRs, factored PSRs, and multi-mode PSRs. Hierarchical PSRs exploit temporal structure in the environment, because a temporally abstract model can be simpler than a fully-detailed model. I demonstrate that learning a hierarchical PSR is tractable in environments in which learning a single linear PSR is intractable. Factored PSRs model systems with vector-valued observations, exploiting conditional independence among the components of the observation vectors. Leveraging that conditional independence can lead to a factored PSR model that is exponentially smaller than an unstructured model of the same system. Finally, multi-mode PSRs model systems that switch among several modes of operation. The modes used by multi-mode PSRs are defined in terms of past and future observations, which leads to advantages both when learning the model and when using it to make predictions. For each class of structured PSR models, I develop a learning algorithm that scales to larger systems than the suffix-history algorithm but still leverages the advantage of predictive state for learning accurate models. Advisors/Committee Members: Baveja, Satinder Singh (committee member), Durfee, Edmund H. (committee member), Eustice, Ryan M. (committee member), Wellman, Michael P. (committee member).

Subjects/Keywords: Predictive State Representations; Artificial Intelligence; Modeling Dynamical Systems; Computer Science; Engineering

7 more images…

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Wolfe, B. D. (2009). Modeling Dynamical Systems with Structured Predictive State Representations. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/64601

Chicago Manual of Style (16^th Edition):

Wolfe, Britton D. “Modeling Dynamical Systems with Structured Predictive State Representations.” 2009. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/64601.

MLA Handbook (7^th Edition):

Wolfe, Britton D. “Modeling Dynamical Systems with Structured Predictive State Representations.” 2009. Web. 04 Mar 2021.

Vancouver:

Wolfe BD. Modeling Dynamical Systems with Structured Predictive State Representations. [Internet] [Doctoral dissertation]. University of Michigan; 2009. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/64601.

Council of Science Editors:

Wolfe BD. Modeling Dynamical Systems with Structured Predictive State Representations. [Doctoral Dissertation]. University of Michigan; 2009. Available from: http://hdl.handle.net/2027.42/64601

16. Duong, Quang A. Graphical Multiagent Models.

Degree: PhD, Computer Science and Engineering, 2012, University of Michigan

URL: http://hdl.handle.net/2027.42/95999

► I introduce Graphical Multiagent Models (GMMs): probabilistic graphical models that capture agent interactions in factored representations for efficient inference about agent behaviors. The graphical model… (more)

▼ I introduce Graphical Multiagent Models (GMMs): probabilistic graphical models that capture agent interactions in factored representations for efficient inference about agent behaviors. The graphical model formalism exploits locality of agent interactions to support compact expression, and provides a repertoire of inference algorithms for efficient reasoning about joint behavior. I demonstrate that the GMM representation is sufficiently flexible to accommodate diverse sources of knowledge about agent behavior, and to combine these for improved predictions. History-dependent GMMs (hGMMs) extend the static form of GMMs to support representation and reasoning about multiagent behavior over time, offering the particular advantage of capturing joint dependencies induced by abstraction of history information. Computational experiments demonstrate the benefits of explicitly modeling joint behavior and allowing expression of action dependencies when given limited history information, compared to alternative models. Many multiagent modeling tasks that employ probabilistic models entail constructing dependence graph structures from observational data. In the context of graphical games where agents' payoffs depend only on actions of agents in their local neighborhoods, I formally describe the problem of learning payoff dependence structures from limited payoff observations, and investigate several learning algorithms based on minimizing empirical loss. I show that similar algorithms can also be applied to learning both dependence structures and parameters for hGMMs from time-series data. I employ data on human-subject experiments in constructing hGMMs and evaluating the learned models' prediction performance for a consensus dynamics scenario. Analysis of learned graphical structures reveals patterns of action dependence not directly reflected in observed interactions. The problem of modeling information diffusion on partially observed networks provides another demonstration of hGMM flexibility, as unobserved edges may induce correlations among node states. As graphical multiagent models can compensate for correlations induced from missing edges, I find that learning graphical multiagent models for a given network structure from diffusion traces can outperform directly recovering the missing edges, across various network settings. Advisors/Committee Members: Wellman, Michael P. (committee member), Nguyen, Long (committee member), Baveja, Satinder Singh (committee member), Durfee, Edmund H. (committee member).

Subjects/Keywords: Multiagent Reasoning; Graphical Models; Dynamics Behavior; Structure Learning; Computer Science; Engineering; Science

6 more images…

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Duong, Q. A. (2012). Graphical Multiagent Models. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/95999

Chicago Manual of Style (16^th Edition):

Duong, Quang A. “Graphical Multiagent Models.” 2012. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/95999.

MLA Handbook (7^th Edition):

Duong, Quang A. “Graphical Multiagent Models.” 2012. Web. 04 Mar 2021.

Vancouver:

Duong QA. Graphical Multiagent Models. [Internet] [Doctoral dissertation]. University of Michigan; 2012. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/95999.

Council of Science Editors:

Duong QA. Graphical Multiagent Models. [Doctoral Dissertation]. University of Michigan; 2012. Available from: http://hdl.handle.net/2027.42/95999

17. Boerkoel Jr, James C. Distributed Approaches for Solving Constraint-based Multiagent Scheduling Problems.

Degree: PhD, Computer Science & Engineering, 2012, University of Michigan

URL: http://hdl.handle.net/2027.42/96046

► This research focuses on building foundational algorithms for scheduling agents that assist people in managing their activities in environments in which tempo and complexity outstrip… (more)

▼ This research focuses on building foundational algorithms for scheduling agents that assist people in managing their activities in environments in which tempo and complexity outstrip people's cognitive capacity. The critical challenge is that, as individuals decide how to act on their scheduling goals, scheduling agents should answer queries regarding the events in their interacting schedules while respecting individual privacy and autonomy to the extent possible. I formally define both the Multiagent Simple Temporal Problem (MaSTP) and Multiagent Disjunctive Temporal Problem (MaDTP) for naturally capturing and reasoning over the distributed but interconnected scheduling problems of multiple individuals. My hypothesis is that combining a bottom-up approach – where an agent externalizes constraints that compactly summarize how its local subproblem affects other agents' subproblems, with a top-down approach – where an agent proactively constructs and internalizes new local constraints that decouple its subproblem from others', will lead to effective solution techniques. I confirm that my hypothesized approach leads to distributed algorithms that calculate summaries of the joint solution space for multiagent scheduling problems, without centralizing or otherwise redistributing the problems. In both the MaSTP and MaDTP domains, the distributed algorithms permit concurrent execution for significant speedup over current art, and also increase the level of privacy and independence in individual agent reasoning. These algorithms are most advantageous for problems where interactions between the agents are sparse compared to the complexity of agents' individual scheduling problems. Moreover, despite the combinatorially-large and unwieldy nature of the MaDTP solution space, I show that agents can use influence spaces, which compactly capture the impact of agents' interacting schedules, to tractably converge on distributed summaries of the joint solution space. Finally, I apply the same basic principle to the Hybrid Scheduling Problem, which combines constraint-based scheduling with a rudimentary level of planning, and show that my Hybrid Constraint Tightening precompilation algorithm can improve the propagation of information between planning and scheduling subproblems, leading to significant search space pruning and execution time reduction. Advisors/Committee Members: Durfee, Edmund H. (committee member), Cohn, Amy Ellen (committee member), Pollack, Martha E. (committee member), Wellman, Michael P. (committee member).

Subjects/Keywords: Multiagent Scheduling; Constraint-based Scheduling; Simple Temporal Problem; Disjunctive Temporal Problem; Temporal Decoupling; Multiagent Coordination; Computer Science; Engineering

10 more images…

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Boerkoel Jr, J. C. (2012). Distributed Approaches for Solving Constraint-based Multiagent Scheduling Problems. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/96046

Chicago Manual of Style (16^th Edition):

Boerkoel Jr, James C. “Distributed Approaches for Solving Constraint-based Multiagent Scheduling Problems.” 2012. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/96046.

MLA Handbook (7^th Edition):

Boerkoel Jr, James C. “Distributed Approaches for Solving Constraint-based Multiagent Scheduling Problems.” 2012. Web. 04 Mar 2021.

Vancouver:

Boerkoel Jr JC. Distributed Approaches for Solving Constraint-based Multiagent Scheduling Problems. [Internet] [Doctoral dissertation]. University of Michigan; 2012. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/96046.

Council of Science Editors:

Boerkoel Jr JC. Distributed Approaches for Solving Constraint-based Multiagent Scheduling Problems. [Doctoral Dissertation]. University of Michigan; 2012. Available from: http://hdl.handle.net/2027.42/96046

18. Bloch, Mitchell. Computationally Efficient Relational Reinforcement Learning.

Degree: PhD, Computer Science & Engineering, 2018, University of Michigan

URL: http://hdl.handle.net/2027.42/145859

► Relational Reinforcement Learning (RRL) is a technique that enables Reinforcement Learning (RL) agents to generalize from their experience, allowing them to learn over large or… (more)

▼ Relational Reinforcement Learning (RRL) is a technique that enables Reinforcement Learning (RL) agents to generalize from their experience, allowing them to learn over large or potentially infinite state spaces, to learn context sensitive behaviors, and to learn to solve variable goals and to transfer knowledge between similar situations. Prior RRL architectures are not sufficiently computationally efficient to see use outside of small, niche roles within larger Artificial Intelligence (AI) architectures. I present a novel online, incremental RRL architecture and an implementation that is orders of magnitude faster than its predecessors. The first aspect of this architecture that I explore is a computationally efficient implementation of an adaptive Hierarchical Tile Coding (aHTC), a kind of Adaptive Tile Coding (ATC) in which more general tiles which cover larger portions of the state-action space are kept as ones that cover smaller portions of the state-action space are introduced, using k-dimensional tries (k-d tries) to implement the value function for non-relational Temporal Difference (TD) methods. In order to achieve comparable performance for RRL, I implement the Rete algorithm to replace my k-d tries due to its efficient handling of both the variable binding problem and variable numbers of actions. Tying aHTCs and Rete together, I present a rule grammar that both maps aHTCs onto Rete and allows the architecture to automatically extract relational features in order to support adaptation of the value function over time. I experiment with several refinement criteria and additional functionality with which my agents attempt to determine if rerefinement using different features might allow them to better learn a near optimal policy. I present optimal results using a value criterion for several variants of BlocksWorld. I provide transfer results for BlocksWorld and a scalable Taxicab domain. I additionally introduce a Higher Order Grammar (HOG) that grants online, incremental RRL agents additional flexibility to introduce additional variables and corresponding relations as needed in order to learn effective value functions. I evaluate agents that use the HOG on a version of Blocks World and on an Adventure task. In summary, I present a new online, incremental RRL architecture, a grammar to map aHTCs onto the Rete, and an implementation that is orders of magnitude faster than its predecessors. Advisors/Committee Members: Laird, John E (committee member), Lewis, Richard L (committee member), Baveja, Satinder Singh (committee member), Durfee, Edmund H (committee member).

Subjects/Keywords: Relational Reinforcement Learning; Rete; Adaptive Tile Coding; Online Learning; Sequential Decision Making; Computer Science; Engineering

7 more images…

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Bloch, M. (2018). Computationally Efficient Relational Reinforcement Learning. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/145859

Chicago Manual of Style (16^th Edition):

Bloch, Mitchell. “Computationally Efficient Relational Reinforcement Learning.” 2018. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/145859.

MLA Handbook (7^th Edition):

Bloch, Mitchell. “Computationally Efficient Relational Reinforcement Learning.” 2018. Web. 04 Mar 2021.

Vancouver:

Bloch M. Computationally Efficient Relational Reinforcement Learning. [Internet] [Doctoral dissertation]. University of Michigan; 2018. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/145859.

Council of Science Editors:

Bloch M. Computationally Efficient Relational Reinforcement Learning. [Doctoral Dissertation]. University of Michigan; 2018. Available from: http://hdl.handle.net/2027.42/145859

19. Cohn, Robert W. Maximizing Expected Value of Information in Decision Problems by Querying on a Wish-to-Know Basis.

Degree: PhD, Computer Science and Engineering, 2016, University of Michigan

URL: http://hdl.handle.net/2027.42/120772

► An agent acting under uncertainty regarding how it should complete the task assigned to it by its human user can learn more about how it… (more)

▼ An agent acting under uncertainty regarding how it should complete the task assigned to it by its human user can learn more about how it should behave by posing queries to its human user. Asking too many queries, however, may risk requiring undue attentional demand of the user, and so the agent should prioritize asking the most valuable queries. For decision-making agents, Expected Value of Information (EVOI) measures the value of a query, and so given a set of queries the agent can ask, the agent should ask the query that is expected to maximally improve its performance by selecting the query with highest EVOI in its set. Unfortunately, to compute the EVOI of a query, the agent must consider how each possible response would influence its future behavior, which makes query selection particularly challenging in settings where planning the agent's behavior would be expensive even without the added complication of considering queries to ask, especially when there are many potential queries the agent should consider. The focus of this dissertation is on developing query selection algorithms that can be feasibly applied to such settings. The main novel approach studied, Wishful Query Projection (WQP), is based on the intuition that the agent should consider which query to ask on the basis of obtaining knowledge that would help it resolve a particular dilemma that it wishes could be resolved, as opposed to blindly searching its entire query set in hopes of finding one that would give it valuable knowledge. In implementing WQP, this dissertation contributes algorithms that are founded upon the following novel result: for myopic settings, when the agent can ask any query as long as the query has no more than some set number of possible responses, the best query takes the form of asking the user to choose from a specified subset of ways for the agent to behave. The work presented shows that WQP selects queries with near-optimal EVOI when the agent's query set is (1) balanced in the range of queries it contains; and (2) rich in terms of the highest contained query EVOI. Advisors/Committee Members: Baveja, Satinder Singh (committee member), Durfee, Edmund H (committee member), Lewis, Richard L (committee member), Wellman, Michael P (committee member).

Subjects/Keywords: Expected Value of Information; Query Selection Algorithms; Computer Science; Engineering

5 more images…

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Cohn, R. W. (2016). Maximizing Expected Value of Information in Decision Problems by Querying on a Wish-to-Know Basis. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/120772

Chicago Manual of Style (16^th Edition):

Cohn, Robert W. “Maximizing Expected Value of Information in Decision Problems by Querying on a Wish-to-Know Basis.” 2016. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/120772.

MLA Handbook (7^th Edition):

Cohn, Robert W. “Maximizing Expected Value of Information in Decision Problems by Querying on a Wish-to-Know Basis.” 2016. Web. 04 Mar 2021.

Vancouver:

Cohn RW. Maximizing Expected Value of Information in Decision Problems by Querying on a Wish-to-Know Basis. [Internet] [Doctoral dissertation]. University of Michigan; 2016. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/120772.

Council of Science Editors:

Cohn RW. Maximizing Expected Value of Information in Decision Problems by Querying on a Wish-to-Know Basis. [Doctoral Dissertation]. University of Michigan; 2016. Available from: http://hdl.handle.net/2027.42/120772

20. Vorobeychik, Yevgeniy. Mechanism Design and Analysis Using Simulation-Based Game Models.

Degree: PhD, Computer Science & Engineering, 2008, University of Michigan

URL: http://hdl.handle.net/2027.42/60786

► As agent technology matures, it becomes easier to envision electronic marketplaces teeming with autonomous agents. Since agents are explicitly programmed to (nearly) optimally compete in… (more)

▼ As agent technology matures, it becomes easier to envision electronic marketplaces teeming with autonomous agents. Since agents are explicitly programmed to (nearly) optimally compete in these marketplaces, and markets themselves are designed with specific objectives in mind, tools are necessary for systematic analyses of strategic interactions among autonomous agents. While traditional game-theoretic approaches to the analysis of multi-agent systems can provide much insight, they are often inadequate, as they rely heavily on analytic tractability of the problem at hand; however, even mildly realistic models of electronic marketplaces contain enough complexity to render a fully analytic approach hopeless. To address questions not amenable to traditional theoretical approaches, I develop methods that allow systematic computational analysis of game-theoretic models in which the players' payoff functions are represented using simulations (i.e., simulation-based games). I develop a globally convergent algorithm for Nash equilibrium approximation in infinite simulation-based games, which I instantiate in the context of infinite games of incomplete information. Additionally, I use statistical learning techniques to improve the quality of Nash equilibrium approximation based on data collected from a game simulator. I also derive probabilistic confidence bounds and present convergence results about solutions of finite games modeled using simulations. The former allow an analyst to make statistically-founded statements about results based on game-theoretic simulations, while the latter provide formal justification for approximating game-theoretic solutions using simulation experiments. To address the broader mechanism design problem, I introduce an iterative algorithm for search in the design space, which requires a game solver as a subroutine. As a result, I enable computational mechanism design using simulation-based models of games by availing the designer of a set of solution tools geared specifically towards games modeled using simulations. I apply the developed computational techniques to analyze strategic procurement and answer design questions in a supply-chain simulation, as well as to analyze dynamic bidding strategies in sponsored search auctions. Indeed, the techniques I develop have broad potential applicability beyond electronic marketplaces: they are geared towards any system that features competing strategic players who respond to incentives in a way that can be reasonably predicted via a game-theoretic analysis. Advisors/Committee Members: Wellman, Michael P. (committee member), Baveja, Satinder Singh (committee member), Durfee, Edmund H. (committee member), Ozdenoren, Emre (committee member).

Subjects/Keywords: Simulation-based Game Theory; Computational Game Theory; Multiagent Systems; Computer Science; Engineering

14 more images…

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Vorobeychik, Y. (2008). Mechanism Design and Analysis Using Simulation-Based Game Models. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/60786

Chicago Manual of Style (16^th Edition):

Vorobeychik, Yevgeniy. “Mechanism Design and Analysis Using Simulation-Based Game Models.” 2008. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/60786.

MLA Handbook (7^th Edition):

Vorobeychik, Yevgeniy. “Mechanism Design and Analysis Using Simulation-Based Game Models.” 2008. Web. 04 Mar 2021.

Vancouver:

Vorobeychik Y. Mechanism Design and Analysis Using Simulation-Based Game Models. [Internet] [Doctoral dissertation]. University of Michigan; 2008. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/60786.

Council of Science Editors:

Vorobeychik Y. Mechanism Design and Analysis Using Simulation-Based Game Models. [Doctoral Dissertation]. University of Michigan; 2008. Available from: http://hdl.handle.net/2027.42/60786

21. Jackson, Justin Patrick. Constrained Task Assignment and Scheduling on Networks of Arbitrary Topology.

Degree: PhD, Aerospace Engineering, 2012, University of Michigan

URL: http://hdl.handle.net/2027.42/91527

► This dissertation develops a framework to address centralized and distributed constrained task assignment and task scheduling problems. This framework is used to prove properties of… (more)

▼ This dissertation develops a framework to address centralized and distributed constrained task assignment and task scheduling problems. This framework is used to prove properties of these problems that can be exploited, develop effective solution algorithms, and to prove important properties such as correctness, completeness and optimality. The centralized task assignment and task scheduling problem treated here is expressed as a vehicle routing problem with the goal of optimizing mission time subject to mission constraints on task precedence and agent capability. The algorithm developed to solve this problem is able to coordinate vehicle (agent) timing for task completion. This class of problems is NP-hard and analytical guarantees on solution quality are often unavailable. This dissertation develops a technique for determining solution quality that can be used on a large class of problems and does not rely on traditional analytical guarantees. For distributed problems several agents must communicate to collectively solve a distributed task assignment and task scheduling problem. The distributed task assignment and task scheduling algorithms developed here allow for the optimization of constrained military missions in situations where the communication network may be incomplete and only locally known. Two problems are developed. The distributed task assignment problem incorporates communication constraints that must be satisfied; this is the Communication-Constrained Distributed Assignment Problem. A novel distributed assignment algorithm, the Stochastic Bidding Algorithm, solves this problem. The algorithm is correct, probabilistically complete, and has linear average-case time complexity. The distributed task scheduling problem addressed here is to minimize mission time subject to arbitrary predicate mission constraints; this is the Minimum-time Arbitrarily-constrained Distributed Scheduling Problem. The Optimal Distributed Non-sequential Backtracking Algorithm solves this problem. The algorithm is correct, complete, outputs time optimal schedules, and has low average-case time complexity. Separation of the task assignment and task scheduling problems is exploited here to ameliorate the effects of an incomplete communication network. The mission-modeling conditions that allow this and the benefits gained are discussed in detail. It is shown that the distributed task assignment and task scheduling algorithms developed here can operate concurrently and maintain their correctness, completeness, and optimality properties. Advisors/Committee Members: Girard, Anouck Renee (committee member), Abdelhafiz, Mariam F. (committee member), Durfee, Edmund H. (committee member), Kabamba, Pierre Tshimanga (committee member).

Subjects/Keywords: Who Does What and When, When Who Can Talk to Who Is in Question.; Aerospace Engineering; Engineering

2 more images…

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Jackson, J. P. (2012). Constrained Task Assignment and Scheduling on Networks of Arbitrary Topology. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/91527

Chicago Manual of Style (16^th Edition):

Jackson, Justin Patrick. “Constrained Task Assignment and Scheduling on Networks of Arbitrary Topology.” 2012. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/91527.

MLA Handbook (7^th Edition):

Jackson, Justin Patrick. “Constrained Task Assignment and Scheduling on Networks of Arbitrary Topology.” 2012. Web. 04 Mar 2021.

Vancouver:

Jackson JP. Constrained Task Assignment and Scheduling on Networks of Arbitrary Topology. [Internet] [Doctoral dissertation]. University of Michigan; 2012. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/91527.

Council of Science Editors:

Jackson JP. Constrained Task Assignment and Scheduling on Networks of Arbitrary Topology. [Doctoral Dissertation]. University of Michigan; 2012. Available from: http://hdl.handle.net/2027.42/91527

22. Witwicki, Stefan J. Abstracting Influences for Efficient Multiagent Coordination Under Uncertainty.

Degree: PhD, Computer Science & Engineering, 2011, University of Michigan

URL: http://hdl.handle.net/2027.42/84614

► When planning optimal decisions for teams of agents acting in uncertain domains, conventional methods explicitly coordinate all joint policy decisions and, in doing so, are… (more)

▼ When planning optimal decisions for teams of agents acting in uncertain domains, conventional methods explicitly coordinate all joint policy decisions and, in doing so, are inherently susceptible to the curse of dimensionality, as state, action, and observation spaces grow exponentially with the number of agents. With the goal of extending the scalability of optimal team coordination, the research presented in this dissertation examines how agents can reduce the amount of information they need to coordinate. Intuitively, to the extent that agents are weakly coupled, they can avoid the complexity of coordinating all decisions; they need instead only coordinate abstractions of their policies that convey their essential influences on each other. In formalizing this intuition, I consider several complementary aspects of weakly-coupled problem structure, including agent scope size, corresponding to the number of an agent's peers whose decisions influence the agent's decisions, and degree of influence, corresponding to the proportion of unique influences that peers can feasibly exert. To exploit this structure, I introduce a (transition-dependent decentralized POMDP) model that efficiently decomposes into local decision models with shared state features. This context yields a novel characterization of influences as transition probabilities (compactly encoded using a dynamic Bayesian network). Not only is this influence representation provably sufficient for optimal coordination, but it also allows me to frame the subproblems of (1) proposing influences, (2) evaluating influences, and (3) computing optimal policies around influences as mixed-integer linear programs. The primary advantage of working in the influence space is that there are potentially significantly fewer feasible influences than there are policies. Blending prior work on decoupled joint policy search and constraint optimization, I develop influence-space search algorithms that, for problems with a low degree of influence, compute optimal solutions orders of magnitude faster than policy-space search. When agents' influences are constrained, influence-space search also outperforms other state-of-the-art optimal solution algorithms. Moreover, by exploiting both degree of influence and agent scope size, I demonstrate scalability, substantially beyond the reach of prior optimal methods, to teams of 50 weakly-coupled transition-dependent agents. Advisors/Committee Members: Durfee, Edmund H. (committee member), Baveja, Satinder Singh (committee member), Cohn, Amy Ellen (committee member), Wellman, Michael P. (committee member).

Subjects/Keywords: Multiagent Coordination; Optimal Planning; Sequential Decision Making; Agent Interaction Structure; Decentralized Partially Observable Markov Decision Process; Influence Based Policy Abstraction; Computer Science; Engineering

10 more images…

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Witwicki, S. J. (2011). Abstracting Influences for Efficient Multiagent Coordination Under Uncertainty. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/84614

Chicago Manual of Style (16^th Edition):

Witwicki, Stefan J. “Abstracting Influences for Efficient Multiagent Coordination Under Uncertainty.” 2011. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/84614.

MLA Handbook (7^th Edition):

Witwicki, Stefan J. “Abstracting Influences for Efficient Multiagent Coordination Under Uncertainty.” 2011. Web. 04 Mar 2021.

Vancouver:

Witwicki SJ. Abstracting Influences for Efficient Multiagent Coordination Under Uncertainty. [Internet] [Doctoral dissertation]. University of Michigan; 2011. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/84614.

Council of Science Editors:

Witwicki SJ. Abstracting Influences for Efficient Multiagent Coordination Under Uncertainty. [Doctoral Dissertation]. University of Michigan; 2011. Available from: http://hdl.handle.net/2027.42/84614

23. Mohan, Shiwali. From Verbs to Tasks: An Integrated Account of Learning Tasks from Situated Interactive Instruction.

Degree: PhD, Computer Science and Engineering, 2015, University of Michigan

URL: http://hdl.handle.net/2027.42/111573

► Intelligent collaborative agents are becoming common in the human society. From virtual assistants such as Siri and Google Now to assistive robots, they contribute to… (more)

▼ Intelligent collaborative agents are becoming common in the human society. From virtual assistants such as Siri and Google Now to assistive robots, they contribute to human activities in a variety of ways. As they become more pervasive, the challenge of customizing them to a variety of environments and tasks becomes critical. It is infeasible for engineers to program them for each individual use. Our research aims at building interactive robots and agents that adapt to new environments autonomously by interacting with human users using natural modalities. This dissertation studies the problem of learning novel tasks from human-agent dialog. We propose a novel approach for interactive task learning, situated interactive instruction (SII), and investigate approaches to three computational challenges that arise in designing SII agents: situated comprehension, mixed-initiative interaction, and interactive task learning. We propose a novel mixed-modality grounded representation for task verbs which encompasses their lexical, semantic, and task-oriented aspects. This representation is useful in situated comprehension and can be learned through human-agent interactions. We introduce the Indexical Model of comprehension that can exploit extra-linguistic contexts for resolving semantic ambiguities in situated comprehension of task commands. The Indexical model is integrated with a mixed-initiative interaction model that facilitates a flexible task-oriented human-agent dialog. This dialog serves as the basis of interactive task learning. We propose an interactive variation of explanation-based learning that can acquire the proposed representation. We demonstrate that our learning paradigm is efficient, can transfer knowledge between structurally similar tasks, integrates agent-driven exploration with instructional learning, and can acquire several tasks. The methods proposed in this thesis are integrated in Rosie - a generally instructable agent developed in the Soar cognitive architecture and embodied on a table-top robot. Advisors/Committee Members: Laird, John E. (committee member), Lewis, Richard L. (committee member), Thomaz, Andrea Lockerd (committee member), Olson, Edwin (committee member), Durfee, Edmund H. (committee member).

Subjects/Keywords: interactive task learning; situated interactive instruction; human-robot interaction; robot learning; grounded language comprehension; interactive agents; Chemical Engineering; Engineering

4 more images…

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Mohan, S. (2015). From Verbs to Tasks: An Integrated Account of Learning Tasks from Situated Interactive Instruction. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/111573

Chicago Manual of Style (16^th Edition):

Mohan, Shiwali. “From Verbs to Tasks: An Integrated Account of Learning Tasks from Situated Interactive Instruction.” 2015. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/111573.

MLA Handbook (7^th Edition):

Mohan, Shiwali. “From Verbs to Tasks: An Integrated Account of Learning Tasks from Situated Interactive Instruction.” 2015. Web. 04 Mar 2021.

Vancouver:

Mohan S. From Verbs to Tasks: An Integrated Account of Learning Tasks from Situated Interactive Instruction. [Internet] [Doctoral dissertation]. University of Michigan; 2015. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/111573.

Council of Science Editors:

Mohan S. From Verbs to Tasks: An Integrated Account of Learning Tasks from Situated Interactive Instruction. [Doctoral Dissertation]. University of Michigan; 2015. Available from: http://hdl.handle.net/2027.42/111573

24. Li, Ning Hui. The Goal Re-activation Problem in Cognitive Architectures.

Degree: PhD, Computer Science and Engineering, 2016, University of Michigan

URL: http://hdl.handle.net/2027.42/120676

► Intelligent agents in the real world have to manage multiple goals. However, the pursuit of some goals may only be possible under specific conditions which,… (more)

Subjects/Keywords: cognitive architecture; prospective memory; Computer Science; Engineering

6 more images…

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Li, N. H. (2016). The Goal Re-activation Problem in Cognitive Architectures. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/120676

Chicago Manual of Style (16^th Edition):

Li, Ning Hui. “The Goal Re-activation Problem in Cognitive Architectures.” 2016. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/120676.

MLA Handbook (7^th Edition):

Li, Ning Hui. “The Goal Re-activation Problem in Cognitive Architectures.” 2016. Web. 04 Mar 2021.

Vancouver:

Li NH. The Goal Re-activation Problem in Cognitive Architectures. [Internet] [Doctoral dissertation]. University of Michigan; 2016. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/120676.

Council of Science Editors:

Li NH. The Goal Re-activation Problem in Cognitive Architectures. [Doctoral Dissertation]. University of Michigan; 2016. Available from: http://hdl.handle.net/2027.42/120676

University of Michigan

25. Park, Sunju. The p -strategy: An adaptive agent bidding strategy based on stochastic modeling for continuous double auctions.

Degree: PhD, Computer science, 1999, University of Michigan

URL: http://hdl.handle.net/2027.42/132219

► We expect an e-commerce infrastructure to be populated by software agents who buy and sell goods on behalf of their human owners. As a step… (more)

▼ We expect an e-commerce infrastructure to be populated by software agents who buy and sell goods on behalf of their human owners. As a step towards making this vision come true, we have developed an agent bidding strategy (called the p-strategy) for a class of continuous double auctions (CDAs). The p-strategy is based on stochastic modeling of the auction process. A p-strategy agent uses probabilistic assessment about offer price distributions, offer arrival rates, etc. to figure out the best price to offer at the auction. Using its stochastic model of the auction, the p-strategy agent trades off the probability of success against the payoff of success, which is manifested in its decision of raising (or dropping) and narrowing (or spreading) its offer prices. We have evaluated the performance of the p-strategy through experiments. We have divided the experimental space into three dimensions, and systematically compared the p-strategy seller to sellers with different bidding strategies in various environments. We have found that the p-strategy outperforms other agent strategies in the CDA in a majority of experiments. In particular, the p-strategy seller performs well when many buy offers are available, as it can extract more profit per match at the expense of buyers. However, the performance of the p-strategy seller degrades with high competition among sellers or with multiple competing p-sellers. In addition to stochastic modeling, we have developed an adaptation algorithm. Although the p-seller performs very well in most cases, there are some cases where the sophisticated modeling of the auction does not pay off. In addition, stochastic modeling requires non-trivial computation, and thus deliberation overhead diminishes the advantage of using the stochastic model. The adaptation algorithm allows the p-seller to adaptively figure out when to use stochastic modeling or not at run time. Adding adaptivity to the p-strategy is an important and practical step for using the p-strategy. The experimental results indicate that the adaptive p-strategy outperforms the plain p-strategy when the p-strategy performs poorly, while it performs very similarly to the p-strategy when the p-strategy dominates other simple strategies. Advisors/Committee Members: Durfee, Edmund H. (advisor), Birmingham, William P. (advisor).

Subjects/Keywords: Adaptive Agent; Based; Bidding; Continuous Double Auctions; P-strategy; Stochastic Modeling

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Park, S. (1999). The p -strategy: An adaptive agent bidding strategy based on stochastic modeling for continuous double auctions. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/132219

Chicago Manual of Style (16^th Edition):

Park, Sunju. “The p -strategy: An adaptive agent bidding strategy based on stochastic modeling for continuous double auctions.” 1999. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/132219.

MLA Handbook (7^th Edition):

Park, Sunju. “The p -strategy: An adaptive agent bidding strategy based on stochastic modeling for continuous double auctions.” 1999. Web. 04 Mar 2021.

Vancouver:

Park S. The p -strategy: An adaptive agent bidding strategy based on stochastic modeling for continuous double auctions. [Internet] [Doctoral dissertation]. University of Michigan; 1999. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/132219.

Council of Science Editors:

Park S. The p -strategy: An adaptive agent bidding strategy based on stochastic modeling for continuous double auctions. [Doctoral Dissertation]. University of Michigan; 1999. Available from: http://hdl.handle.net/2027.42/132219

University of Michigan

26. Atkins, Ella Marie. Plan generation and hard real -time execution with application to safe, autonomous flight.

Degree: PhD, Systems science, 1999, University of Michigan

URL: http://hdl.handle.net/2027.42/132068

► We address the problem of constructing and executing control plans for safe, fully-autonomous operation within a complex real-time domain where the combination of an incomplete… (more)

▼ We address the problem of constructing and executing control plans for safe, fully-autonomous operation within a complex real-time domain where the combination of an incomplete knowledge base, limited computational resources, and hard real-time deadlines precludes the success of traditional planning and scheduling algorithms. To meet hard deadlines with limited computational resources, we employ a stochastic world model to prioritize the state-space during planning, then utilize feedback from the scheduler to set a threshold below which the planner removes unlikely states from consideration in order to generate a schedulable plan. Our probabilistic planning algorithm minimizes domain knowledge size and explicitly provides for the construction of real-time control plans. Although approximate instead of optimal, the representational efficiency gained by our approach makes it a viable alternative to the well-established Markov Decision Process for complex real-time problem domains. When resource limits require plan modification, our heuristic algorithms for communicating task resource utilization information from real-time scheduler to planner provide a novel method for directing the expensive planner backtracking process specifically toward a schedulable plan. The tradeoff in ignoring reachable but unlikely states, as well as allowing incomplete domain knowledge, is that we must now provide explicitly for the detection of and reaction to these unexpected states our system may encounter while executing a plan. By detecting such unhandled states and caching contingency plans for events which, though unlikely, could lead to catastrophic failure, we can still guarantee system safety in the probabilistic sense. Ultimately, however, we are still constrained by plan-execution resource limits regardless of the tradeoff algorithms employed. We apply the resultant architecture (CIRCA-II) to simulated autonomous aircraft flight and demonstrate its utility for intelligently making tradeoffs that maximize mission success probability even under adverse circumstances in which other planner/scheduler algorithms would fail. We also describe progress toward fully-automating the University of Michigan Uninhabited Aerial Vehicle (UAV). When UAV hardware and low-level control software development are complete, we hope to apply a combination of CIRCA-II and state-of-the-art dynamic model identification algorithms to detect and react in real-time to dangerous in-flight emergencies including engine failure and airframe icing. Advisors/Committee Members: Durfee, Edmund H. (advisor), Shin, Kang G. (advisor).

Subjects/Keywords: Application; Autonomous Flight; Flight Plan Generation; Hard; Real-time Execution; Safe; Scheduling

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Atkins, E. M. (1999). Plan generation and hard real -time execution with application to safe, autonomous flight. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/132068

Chicago Manual of Style (16^th Edition):

Atkins, Ella Marie. “Plan generation and hard real -time execution with application to safe, autonomous flight.” 1999. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/132068.

MLA Handbook (7^th Edition):

Atkins, Ella Marie. “Plan generation and hard real -time execution with application to safe, autonomous flight.” 1999. Web. 04 Mar 2021.

Vancouver:

Atkins EM. Plan generation and hard real -time execution with application to safe, autonomous flight. [Internet] [Doctoral dissertation]. University of Michigan; 1999. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/132068.

Council of Science Editors:

Atkins EM. Plan generation and hard real -time execution with application to safe, autonomous flight. [Doctoral Dissertation]. University of Michigan; 1999. Available from: http://hdl.handle.net/2027.42/132068

University of Michigan

27. Musliner, David John. CIRCA: The Cooperative Intelligent Real-time Control Architecture.

Degree: PhD, Computer Science and Engineering, 1993, University of Michigan

URL: http://hdl.handle.net/2027.42/103819

► The Cooperative Intelligent Real-time Control Architecture (CIRCA) is a novel architecture for intelligent real-time control that can guarantee to meet hard deadlines while still using… (more)

▼ The Cooperative Intelligent Real-time Control Architecture (CIRCA) is a novel architecture for intelligent real-time control that can guarantee to meet hard deadlines while still using unpredictable, unrestricted AI methods. CIRCA includes a real-time subsystem used to execute reactive control plans that are guaranteed to meet the domain's real-time deadlines, keeping the system safe. At the same time, CIRCA's AI subsystem performs higher-level reasoning about the domain and the system's goals and capabilities, to develop future reactive control plans. CIRCA thus aims to be intelligent \underline{about} real-time: rather than requiring the system's AI methods to meet deadlines, CIRCA isolates its reasoning about which time-critical reactions to guarantee from the actual execution of the selected reactions. The formal basis for CIRCA's performance guarantees is a state-based world model of agent/environment interactions. Borrowing approaches from real-time systems research, the world model provides the information required to make real-time performance guarantees, but avoids unnecessary complexity. Using the world model, the AI subsystem develops reactive control plans that restrict the world to a limited set of safe and desirable states, by guaranteeing the timely performance of actions to preempt transitions that lead out of the set of states. By executing such "safe" and "stable" plans, CIRCA's real-time subsystem is able to keep the system safe (in the world as modeled) for an indeterminate amount of time, while the parallel AI subsystem develops the next appropriate plan. We have applied a prototype CIRCA implementation to a simulated Puma robot arm performing multiple tasks with real-time deadlines, such as packing parts off a conveyor belt and responding to asynchronous interrupts. Our experimental results show how the system can guarantee to accomplish these tasks under a given set of domain conditions (e.g., conveyor belt speed) and resource limitations (e.g., robot arm speed). Furthermore, because CIRCA reasons explicitly about its own predictable, guaranteed behaviors, the system can recognize when its resources are insufficient for the desired behaviors (e.g., parts are arriving too quickly to be packed carefully), and can then make principled modifications to its performance (e.g., temporarily stacking parts on a table) to maintain system safety. Advisors/Committee Members: Shin, Kang G. (advisor), Durfee, Edmund H. (advisor).

Subjects/Keywords: Engineering, Electronics and Electrical; Artificial Intelligence; Computer Science

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Musliner, D. J. (1993). CIRCA: The Cooperative Intelligent Real-time Control Architecture. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/103819

Chicago Manual of Style (16^th Edition):

Musliner, David John. “CIRCA: The Cooperative Intelligent Real-time Control Architecture.” 1993. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/103819.

MLA Handbook (7^th Edition):

Musliner, David John. “CIRCA: The Cooperative Intelligent Real-time Control Architecture.” 1993. Web. 04 Mar 2021.

Vancouver:

Musliner DJ. CIRCA: The Cooperative Intelligent Real-time Control Architecture. [Internet] [Doctoral dissertation]. University of Michigan; 1993. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/103819.

Council of Science Editors:

Musliner DJ. CIRCA: The Cooperative Intelligent Real-time Control Architecture. [Doctoral Dissertation]. University of Michigan; 1993. Available from: http://hdl.handle.net/2027.42/103819

University of Michigan

28. Gmytrasiewicz, Piotr Jan. A decision-theoretic model of coordination and communication in autonomous systems.

Degree: PhD, Nuclear Engineering, 1992, University of Michigan

URL: http://hdl.handle.net/2027.42/105896

► This thesis presents a formal model of rational, autonomous behavior in single- and multi-agent domains, together with its implementation – the Rational Reasoning System (RRS). The… (more)

Subjects/Keywords: Psychology, Social; Economics, Theory; Artificial Intelligence; Computer Science

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Gmytrasiewicz, P. J. (1992). A decision-theoretic model of coordination and communication in autonomous systems. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/105896

Chicago Manual of Style (16^th Edition):

Gmytrasiewicz, Piotr Jan. “A decision-theoretic model of coordination and communication in autonomous systems.” 1992. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/105896.

MLA Handbook (7^th Edition):

Gmytrasiewicz, Piotr Jan. “A decision-theoretic model of coordination and communication in autonomous systems.” 1992. Web. 04 Mar 2021.

Vancouver:

Gmytrasiewicz PJ. A decision-theoretic model of coordination and communication in autonomous systems. [Internet] [Doctoral dissertation]. University of Michigan; 1992. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/105896.

Council of Science Editors:

Gmytrasiewicz PJ. A decision-theoretic model of coordination and communication in autonomous systems. [Doctoral Dissertation]. University of Michigan; 1992. Available from: http://hdl.handle.net/2027.42/105896

University of Michigan

29. Li, Haksun. Execution resource allocation for distributed real -time controllers.

Degree: PhD, Computer science, 2004, University of Michigan

URL: http://hdl.handle.net/2027.42/124239

► Automated agents operating in a real-time environment face the challenge of not having sufficient resources to execute their preferred control plans to monitor and react… (more)

▼ Automated agents operating in a real-time environment face the challenge of not having sufficient resources to execute their preferred control plans to monitor and react to all possible hazardous situations rapidly enough. In this dissertation, we develop computationally tractable algorithms that the agents can use to modify their preferred control plans to produce schedulable control plans which satisfy their local execution resource constraints, and still respond to the most probable hazards appropriately. We prove that the agents can use certain information to efficiently transform their initially unschedulable plans into schedulable ones. Specifically, when a real-time agent in a multiagent environment is unschedulable, it will first analyze the cost-benefit tradeoffs of its resource usages to attempt to schedule a subset of the actions in its plan that still preempt all conceivable hazards. If this fails, the agent exchanges partial plans with other agents to discover and prune away the unnecessary actions that were planned due to ignorance about other agents' plans. As the agent now becomes more aware of the interactions among the agents, it may realize that some action decisions it has made are now suboptimal. The agent searches for local changes to its plan to correct these suboptimal decisions. If the agent still remains unschedulable, it can analyze its probabilistic temporal trajectory so it can drop the least likely needed actions repeatedly until its plan finally becomes schedulable. We conclude that using our algorithms an agent, whether it is acting alone or in a multiagent environment, can construct a more accurate local model of the world to make resource allocation decisions and better assess their merits. Our experiments show that an agent can, on average, considerably improve its performance by using our techniques. The contributions in this thesis consist of a set of carefully characterized, analyzed, and evaluated data structures and algorithms for discovering, representing, and using new knowledge that a resource-limited real-time agent can efficiently apply to effectively improve resource allocation. Advisors/Committee Members: Durfee, Edmund H. (advisor), Shin, Kang G. (advisor).

Subjects/Keywords: Distributed Systems; Execution; Multiagent; Real-time Controllers; Resource Allocation

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Li, H. (2004). Execution resource allocation for distributed real -time controllers. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/124239

Chicago Manual of Style (16^th Edition):

Li, Haksun. “Execution resource allocation for distributed real -time controllers.” 2004. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/124239.

MLA Handbook (7^th Edition):

Li, Haksun. “Execution resource allocation for distributed real -time controllers.” 2004. Web. 04 Mar 2021.

Vancouver:

Li H. Execution resource allocation for distributed real -time controllers. [Internet] [Doctoral dissertation]. University of Michigan; 2004. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/124239.

Council of Science Editors:

Li H. Execution resource allocation for distributed real -time controllers. [Doctoral Dissertation]. University of Michigan; 2004. Available from: http://hdl.handle.net/2027.42/124239

University of Michigan

30. Schwartz, Peter J. Managing Complex Scheduling Problems with Dynamic and Hybrid Constraints.

Degree: PhD, Computer Science & Engineering, 2007, University of Michigan

URL: http://hdl.handle.net/2027.42/57625

► The task of scheduling can often be a difficult one because of the inherent complexity of real-world problems. In the field of Artificial Intelligence, many… (more)

▼ The task of scheduling can often be a difficult one because of the inherent complexity of real-world problems. In the field of Artificial Intelligence, many representations and algorithms have been developed to automate the scheduling process. Many state of the art scheduling systems deal with this complexity by making assumptions that simplify the algorithms, but in doing so, miss some opportunities to improve performance. Scheduling problems are temporal in nature, and so they often contain constraints that change over time. Many scheduling systems assume that the problems they are solving are all independent, and so they ignore the similarities between subsequent sets of scheduling constraints. Additionally, scheduling problems often contain a mixture of finite-domain and temporal constraints. Many of the systems that can solve problems of this type do so by creating finite-domain variables to represent the constraints, but then ignore the distinction between the different types of variables when searching for a solution. In this dissertation, I identify opportunities to improve performance by exploiting structure where it has previously been overlooked. Following this approach, I develop a set of techniques that apply to a wide variety of situations that can arise in real-world scheduling problems. First, I consider dynamic scheduling problems with constraints that change over time. To address such problems, I introduce a new representation called the Dynamic Disjunctive Temporal Problem, along with several techniques to improve both efficiency and stability when solving one. Second, I consider scheduling problems in which a mixture of finite-domain and temporal variables can interact through hybrid constraints. I introduce the Hybrid Scheduling Problem to represent such problems, and I present a set of techniques that capitalize on the distinction between variable types to improve efficiency across the problem space. Finally, I conclude by proposing several ways that the dynamic and hybrid representations and techniques can be combined. To compare many of the techniques presented throughout this dissertation in the context of structured, real-world problems, I use them to solve scheduling problems based on actual air traffic control constraints recorded from the Dallas/Fort Worth International Airport. Advisors/Committee Members: Pollack, Martha E. (committee member), Cohn, Amy M. (committee member), Durfee, Edmund H. (committee member), Laird, John E. (committee member).

Subjects/Keywords: Scheduling; Constraint Processing; Dynamic Constraints; Hybrid Constraints; Artificial Intelligence; Computer Science; Engineering

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Schwartz, P. J. (2007). Managing Complex Scheduling Problems with Dynamic and Hybrid Constraints. (Doctoral Dissertation). University of Michigan. Retrieved from http://hdl.handle.net/2027.42/57625

Chicago Manual of Style (16^th Edition):

Schwartz, Peter J. “Managing Complex Scheduling Problems with Dynamic and Hybrid Constraints.” 2007. Doctoral Dissertation, University of Michigan. Accessed March 04, 2021. http://hdl.handle.net/2027.42/57625.

MLA Handbook (7^th Edition):

Schwartz, Peter J. “Managing Complex Scheduling Problems with Dynamic and Hybrid Constraints.” 2007. Web. 04 Mar 2021.

Vancouver:

Schwartz PJ. Managing Complex Scheduling Problems with Dynamic and Hybrid Constraints. [Internet] [Doctoral dissertation]. University of Michigan; 2007. [cited 2021 Mar 04]. Available from: http://hdl.handle.net/2027.42/57625.

Council of Science Editors:

Schwartz PJ. Managing Complex Scheduling Problems with Dynamic and Hybrid Constraints. [Doctoral Dissertation]. University of Michigan; 2007. Available from: http://hdl.handle.net/2027.42/57625

		in
And / Or
		in
And / Or
		in
And / Or
		in

Open Access Theses and Dissertations