Distributed Reasoning for Multiagent Simple Temporal Problems
This research focuses on building foundational algorithms for scheduling agents that assist people in managing their activities in environments where tempo and complex activity interdependencies outstrip people's cognitive capacity. We address the critical challenge of reasoning over individual...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for the Advancement of Artificial Intelligence
2013
|
| Online Access: | http://hdl.handle.net/1721.1/80710 |
| _version_ | 1811094338302640128 |
|---|---|
| author | Boerkoel, James Durfee, Edmund H. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Boerkoel, James Durfee, Edmund H. |
| author_sort | Boerkoel, James |
| collection | MIT |
| description | This research focuses on building foundational algorithms for scheduling agents that assist people in managing their activities in environments where tempo and complex activity interdependencies outstrip people's cognitive capacity. We address the critical challenge of reasoning over individuals' interacting schedules to efficiently answer queries about how to meet scheduling goals while respecting individual privacy and autonomy to the extent possible. We formally define the Multiagent Simple Temporal Problem for naturally capturing and reasoning over the distributed but interconnected scheduling problems of multiple individuals. Our hypothesis is that combining bottom-up and top-down approaches will lead to effective solution techniques. In our bottom-up phase, an agent externalizes constraints that compactly summarize how its local subproblem affects other agents' subproblems, whereas in our top-down phase an agent proactively constructs and internalizes new local constraints that decouple its subproblem from others'. We confirm this hypothesis by devising distributed algorithms that calculate summaries of the joint solution space for multiagent scheduling problems, without centralizing or otherwise redistributing the problems. The distributed algorithms permit concurrent execution to achieve significant speedup over the 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 problems. |
| first_indexed | 2024-09-23T15:58:27Z |
| format | Article |
| id | mit-1721.1/80710 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:58:27Z |
| publishDate | 2013 |
| publisher | Association for the Advancement of Artificial Intelligence |
| record_format | dspace |
| spelling | mit-1721.1/807102022-10-02T05:28:12Z Distributed Reasoning for Multiagent Simple Temporal Problems Boerkoel, James Durfee, Edmund H. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Boerkoel, James This research focuses on building foundational algorithms for scheduling agents that assist people in managing their activities in environments where tempo and complex activity interdependencies outstrip people's cognitive capacity. We address the critical challenge of reasoning over individuals' interacting schedules to efficiently answer queries about how to meet scheduling goals while respecting individual privacy and autonomy to the extent possible. We formally define the Multiagent Simple Temporal Problem for naturally capturing and reasoning over the distributed but interconnected scheduling problems of multiple individuals. Our hypothesis is that combining bottom-up and top-down approaches will lead to effective solution techniques. In our bottom-up phase, an agent externalizes constraints that compactly summarize how its local subproblem affects other agents' subproblems, whereas in our top-down phase an agent proactively constructs and internalizes new local constraints that decouple its subproblem from others'. We confirm this hypothesis by devising distributed algorithms that calculate summaries of the joint solution space for multiagent scheduling problems, without centralizing or otherwise redistributing the problems. The distributed algorithms permit concurrent execution to achieve significant speedup over the 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 problems. National Science Foundation (U.S.) (Grant IIS-0534280) National Science Foundation (U.S.) (Grant IIS-0964512) United States. Air Force Office of Scientific Research (Contract FA9550-07-1-0262) 2013-09-13T13:54:46Z 2013-09-13T13:54:46Z 2013-05 2012-10 Article http://purl.org/eprint/type/JournalArticle 1943-5037 1076-9757 http://hdl.handle.net/1721.1/80710 James, Boerkoel, and Edmund H. Durfee. "Distributed Reasoning for Multiagent Simple Temporal Problems." Journal of Artificial Intelligence Research 47 (2013): 95-156. © 2013 AI Access Foundation, Inc. en_US http://jair.org/papers/paper3840.html Journal of Artificial Intelligence Research Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Association for the Advancement of Artificial Intelligence AI Access Foundation |
| spellingShingle | Boerkoel, James Durfee, Edmund H. Distributed Reasoning for Multiagent Simple Temporal Problems |
| title | Distributed Reasoning for Multiagent Simple Temporal Problems |
| title_full | Distributed Reasoning for Multiagent Simple Temporal Problems |
| title_fullStr | Distributed Reasoning for Multiagent Simple Temporal Problems |
| title_full_unstemmed | Distributed Reasoning for Multiagent Simple Temporal Problems |
| title_short | Distributed Reasoning for Multiagent Simple Temporal Problems |
| title_sort | distributed reasoning for multiagent simple temporal problems |
| url | http://hdl.handle.net/1721.1/80710 |
| work_keys_str_mv | AT boerkoeljames distributedreasoningformultiagentsimpletemporalproblems AT durfeeedmundh distributedreasoningformultiagentsimpletemporalproblems |