Shlomo Zilberstein - US grants

9409827 Zilberstein This project is aimed at developing a decision-theoretic, adaptive approach to building systems that can perform robustly a variety of real-time tasks. Such tasks include medical diagnosis job scheduling, and robot navigation. In almost all cases, the deliberation required to select optimal actions degrades the system's overall utility. It is by now well-understood that a successful system must trade off decision quality for deliberation cost. Over the past several years, work by Dean, Horvitz, Russell, Zilberstein, and others has shown that anytime algorithms are a useful tool for real-time system design, since they allow computation time to be larger systems from smaller, reusable anytime modules. The proposed solution to this problem is based on novel off-line compilation process and run-time monitoring that can maximize the overall utility of the system. This research will produce a new architecture for resource-bounded reasoning. The study will cover the problem of constructing anytime algorithms, the representation and manipulation of conditional performance profiles, and the development of efficient compilation and monitoring procedures for systems composed of anytime algorithms.

This is a collaborative project between the Information Retrieval Center and the Resource-Bounded Reasoning Lab at UMass. The project is aimed at developing a new approach to meta-level control of search and applying it to improve the flexibility, adaptability, quality of service, and robustness of information retrieval search engines. Currently, such systems are built by integrating a fixed set of modules and techniques that perform such tasks as query formation, query optimization, query evaluation, precision improvement, and recall improvement. The new approach consists of context-dependent mechanisms for optimal selection of information retrieval techniques based on a probabilistic description of their performance. The approach addresses effectively the high level of uncertainty regarding the duration of complex retrieval techniques and the quality of the result they produce. The current static approach to integration of information retrieval modules continues to produce performance gains of about 10% each year, but the systems are extremely specialized for each task, and it is not clear how well results will generalize to new types of retrieval. This project provides significant advantages because it allows a system to configure itself dynamically to the specific task at hand, to the person using the system, and to limited computational resources. This study will result in systems that are far more flexible in handling a large set of retrieval tasks with possible applications to a range of other problems such as dynamic selection of tasks for autonomous robots to optimize the quality of service.
http://anytime.cs.umass.edu/shlomo/research/DCIR.html

This project develops a decision-theoretic framework for planning and control of multi-agent systems by formalizing the problem as decentralized Markov process. It applies to a wide range of application domains in which decision-making must be performed by multiple collaborating agents such as information gathering, distributed sensing, coordination of multiple robots, as well as the operation of complex human organizations. While substantial progress has been made in planning and control of single agents using MDPs, a similar formal treatment of multi-agent systems has been lacking. Existing techniques tend to avoid a central issue: agents typically have different information about the overall system and they cannot share all this information all the time. Sharing information has a cost that must be factored into the overall decision process. Three approaches to communication are studied based on (1) a cost/benefit analysis of the amount of communication, (2) search in policy space, and (3) transformations of the more tractable centralized policies into decentralized policies. The resulting techniques are evaluated in the context of several realistic applications. This research facilitates a better understanding of the strengths and limitations of existing heuristic approaches to coordination and, more importantly, it includes new approaches based on more formal underpinnings.

Learning to Perform Moderation in Online Forums

Online discussion forums are a valuable resource for people looking to find information, discuss ideas, and get advice on the Internet. The number of forums continues to grow rapidly, covering such topics as politics, technical news and advice, medical issues, and product ratings and opinions. Unfortunately, many forums have too much activity, resulting in information overload. Moderation systems are implemented in some forums as a way to handle this problem, but due to sparsity issues, they are often not sufficient. This project is aimed at automating the moderation process, which currently relies entirely on humans. A framework for learning to perform machine moderation is developed by finding patterns in the moderations made by humans. Four fundamental research challenges are addressed: (1) Identify features that define a good or bad comment and develop methods to extract these features efficiently; (2) Develop classifiers that can be trained to moderate arbitrary comments with high accuracy; (3) Use the knowledge acquired in training on moderated forums in different, possibly unmoderated, forums; (4) Develop a system to combine human and machine moderation effectively. Millions of people already use online forums on a regular basis. This project will produce technology that will improve the quality of service provided to users of online forums and reduce the cost of operation by reducing substantially the amount of human moderation that is needed. The broader impact of the project includes training graduate and undergraduate students at the University of Massachusetts, traditional and non-traditional dissemination effort involving deployment of the resulting technology, and a newly formed alliance with an international research team at INRIA, France.

http://anytime.cs.umass.edu/shlomo/research/MODERATE.html

This is a research project intended to overcome barriers that have limited the usefulness of partially-observable Markov decision process algorithms. In the area of planning under uncertainty, the Markov decision process (MDP) has emerged as a powerful and elegant framework for solving problems in a wide range of application domains such as mobile robot control, machine maintenance, gesture recognition, medical diagnosis and treatment, and policy making. For situations in which the decision maker can fully observe the intermediate state of the domain, there are many effective algorithms that can solve large problems. However, in many applications, it is unrealistic to assume that perfect state information is available. The more general, partially-observable MDP (POMDP) addresses this difficulty, but in this case the computational complexity of planning makes it hard to apply existing solution techniques to practical applications.

This project will study new ways to address the key computational bottlenecks in POMDP algorithms. To achieve this, it will (a) Identify and examine new types of belief-space structures that can be used to accelerate significantly each of the key components of POMDP solution techniques; (b) Evaluate the impact of these improvements on a wide range of exact and approximate algorithms with the goal of demonstrating exponential acceleration; (c) Integrate the new approach with previously identified methods for accelerating MDP and POMDP algorithms using search, symbolic representations, and parallelization; (d) Develop a new set of challenging test problems and benchmarks that are significantly harder than the existing toy problems and perform a rigorous evaluation and comparison of the developed techniques; and (e) Increase the interaction between the artificial intelligence community and other communities that employ POMDP solution techniques such as operations research and management sciences, and exploit the synergy that arises when the best solution techniques from these communities are brought together.

The approach is based on exploring new types of structures in the belief space that make it possible to decompose the main computational components into faster, region-based operations. A theoretical analysis of the new approach and a preliminary implementation show that it can significantly increase the efficiency of both exact and approximate algorithms and thus it can improve the scalability of POMDP algorithms and increase their applicability. The newly designed technique is particularly suitable for parallel implementation on grid computers, offering significant additional opportunities for performance gains.

The technical impact of this project involves fundamental contributions to the understanding of the complexity of planning in stochastic domains as well as the development of efficient planning algorithms that provide exponential savings in computing time. The new approach improves several computational operations that are often used as components of existing algorithms - both exact and approximate. Therefore, the benefits of the approach transfer easily to many existing solution techniques. The broader impact of the project stems from the broad applicability of the resulting technology in several scientific and engineering disciplines, the immediate educational impact at the University of Massachusetts Amherst, an extensive plan for non-traditional dissemination efforts, making the experimental testbed available to the research community, and enhancing an existing alliance between the principal investigator and an international research team at INRIA, France.

A fundamental challenge in artificial intelligence is to achieve intelligent coordination of a group of decision makers in spite of uncertainty and limited information. Decision theory offers a normative framework for optimizing decisions under uncertainty, but due to computational barriers, developing decision-theoretic reasoning algorithms for multi-agent systems is a serious challenge. This project will advance foundational contributions to the understanding of decision-theoretic planning in stochastic multi-agent domains as well as the development of efficient new algorithms that provide exponential savings in memory requirements and computation time. Moving beyond toy problems is a hard computational challenge that has been broadly recognized by the multiagent systems community. Research under this project will transform the ability of researcher and practitioners to apply decision-theoretic planing to a new range of domains.

This project is developing automated methods of artificial intelligence (AI) for creating generalized plans that include loops and branches, can handle unknown quantities of objects, and work for large classes of problem instances. One of the key challenges is to reason about plans with loops and to do so without using automated theorem proving, which tends to be intractable. In particular, research is accomplishing the following goals: (1) develop new theoretical foundations for generalized planning; (2) develop effective abstraction mechanisms and new plan representations to support these new capabilities; (3) develop effective algorithms for plan synthesis as well as generalization of sample plans; (4) develop analysis tools to reason about the applicability, correctness and efficiency of generalized plans; (5) extend the framework to include sensing actions, conditional plans, and domain-specific knowledge in the form of partially specified plans; (6) create a new set of challenging benchmark problems and perform a rigorous evaluation of the approach; and (7) increase the interaction between the AI community and other communities, particularly model checking, that study the abstraction mechanisms and theoretical foundations necessary for generalized planning. This new framework may significantly improve the scope and applicability of automated planning systems.

This award gives travel, housing, and registration-cost support to selected students and other young researchers from U.S. universities for their participation in the International Summer School on Planning and Scheduling, which is affiliated with the 19th International Conference on Automated Planning and Scheduling (ICAPS-09) held September 19-23 in Thessaloniki, Greece. Artificial Intelligence planning and scheduling is relevant to a wide variety of applications such as software engineering, manufacturing, transportation, and robotics. The ICAPS-09 Summer School includes a poster session, where students present their research ideas for commentary by more senior researchers, as well as intensive study of foundational material and the latest research in automated planning and scheduling. The Summer School realizes an integration of research and education in its preparation of emerging scientists.

This project is aimed at developing effective decision-theoretic planning algorithms for multi-agent systems that involve dozens or hundreds of agents. Current approaches to agent coordination that provide rigorous performance guarantees can only handle a few agents. The project addresses this barrier with the following objectives: (1) develop new problem representations that allow planning algorithms to leverage the interaction structure and independence relationships within a domain; (2) develop approximation methods that operate with limited memory and time, and exhibit anytime characteristics; (3) perform rigorous convergence analysis and establish tight error bounds on solution quality; (4) develop techniques that make it easy to exploit parallelization offered by multi-core processors; and (5) create a new set of challenging test problems and perform a rigorous evaluation. The project produces two fundamentally new approaches to planning in multi-agent settings. The first approach offers efficient message-passing planning algorithms based on computational paradigms such as expectation-maximization (EM) and the concave-convex procedure (CCCP). The second approach offers rollout sampling methods for domains that are too large to be explicitly represented. These new methods improve the scalability of existing techniques by several orders of magnitude. The results transform the ability of researchers and practitioners to apply rigorous decision-theoretic planning to multi-agent domains such as sensor networks and mobile robot coordination. The broader impact stems from the wide applicability of the resulting technology, undergraduate and graduate educational activities at UMass, dissemination efforts that make the experimental domain and algorithms publically available, and the development of international collaborations.

Autonomous systems offer transformational impacts on society as they help reduce human labor, decrease risks and costs, and improve productivity and efficiency. They have been deployed in a wide range of domains from household products to space exploration vehicles. In many areas, however, there are still considerable barriers to the deployment of fully autonomous systems. These barriers range from technological to ethical and legal issues. Examples include driving a car, robot deployment in search and rescue operations, automated farming, and robotic surgery. When full autonomy is not feasible, it is often desirable to automate parts of the entire process. This project offers a comprehensive study of planning for semi-autonomous systems -- systems that are capable of autonomous operation under some conditions, but may require manual control in order to complete the task at hand. Planning for semi-autonomous systems is challenging because it must account for the different skills of the human operator and the automated system, the communication between them required to facilitate smooth transfer of control, the uncertainty about human responsiveness, engagement level and readiness to take over control, and the possibility of human error in interpreting or following the plan.

The project takes an interdisciplinary approach that addresses the computational challenges together with the challenges that rise whenever the human is in the loop. With a focus on semi-autonomous driving as the primary domain, research activities include: designing general-purpose graphical models to represent the problem of collaborative control of semi-autonomous systems; developing effective methods to represent and earn competence models of the actors; developing efficient decision-theoretic planning algorithms that exploit heuristic search and reachability analysis to create the shared plan; developing algorithms to compute vital statistics and runtime feedback about the shared plan; developing ways to capture models of situation awareness and human errors, and factor them into the planning process; and creating a set of challenging scenarios and test problems for planning in semi-autonomous systems. Evaluation of the approach is conducted using several testbeds including two realistic driving simulators.

The grant provides travel support for graduate students to attend the 2014 Logic and Computational Complexity Workshop that will take place in Vienna, Austria, on July 12-13, 2014, which is taking place during the Vienna Summer of Logic event, which encompasses the Federated Logic Conferences (FLoC'2014). Funding for student travel has significant broader impacts because of the opportunity it gives the students to become part of their research community, discuss their research with others, listen to and meet with leaders in the field. This workshop is international and provides an international dimension, because students will have experiences relevant to becoming part of a global workforce.

Probabilistic planning is essential for the construction of autonomous systems that can operate robustly in the face of uncertainty---from simple household products to space exploration vehicles. As the range of the tasks performed by such systems grows, so does the complexity of planning. This project studies the foundations of automated planning with reduced models---models that include less detail on the problem at hand and thereby facilitate the development of faster planning algorithms. Renewed interest in planning with reduced models was prompted by the surprising success of determinization, which employs classical planning techniques that ignore uncertainty and creates new plans online whenever the exiting plan fails. The success of such methods at the first international probabilistic planning competition indicated their great potential, but recent works have also revealed significant drawbacks.

The main goal of this project is to exploit the insights offered by successful methods for planning with reduced models, while exposing and addressing their inherent drawbacks. In particular, the project addresses four key challenges: (1) how to plan with a reduced model, yet factor in, to some limited extent, the complete model; (2) how to execute plans constructed for a reduced model, while minimizing the change of reaching a state for which no valid action is available; (3) how to perform planning and execution concurrently, exploiting all the available time to improve the plan; and (4) how to formulate this continual planning paradigm in a way that is amenable to a formal analysis, so that guarantees can be established on the overall performance. The project offers a comprehensive treatment of these challenges by introducing a new planning paradigm that generalizes the concept of determinization and creates a whole spectrum of reduced models that differ from each other along two key dimensions: the number of outcomes per state-action pair that are fully accounted for in the reduced model, and the number of occurrences of the remaining outcomes that are planned for in advance. The project offers fundamental contributions to planning and execution under uncertainty, placing previous works on reduced models in a broader context and shedding light on their effective use in practice. Project outcomes include new planning and plan execution algorithms, training undergraduate and graduate students in this area, and a range of outreach activities.

Building reliable autonomous systems that can construct and execute plans to achieve some assigned goals, without human intervention, has been the hallmark of artificial intelligence and robotics since their inception. Reliable autonomy is becoming increasingly important as it enables innovative new applications in areas such as transportation, health, and sustainable living. Despite substantial progress, there are still considerable barriers to the long-term, large scale deployment of fully autonomous systems such as self-driving cars or mobile service robots. These barriers range from technological and economic constraints to ethical and legal issues. This project offers a comprehensive approach to circumvent these barriers by building semi-autonomous systems that rely on rich forms of human assistance, ranging from advice to constant supervision of the system with the possibility of taking over control. The project develops techniques to assure the safety of such systems when human assistance is delayed and to reduce their reliance on human assistance over time. Additionally, the project contributes to training of undergraduate and graduate students in this interdisciplinary area, mentoring of students with special attention to underrepresented groups, outreach activities to local schools, and strengthening of industrial collaborations.

The project answers fundamental questions about the feasibility, efficiency, and scalability of planning and learning algorithms to support semi-autonomous systems. The main thrusts of the project are (1) develop techniques that can delegate autonomy to a system with some restrictions, and provide strong guarantees that these restrictions will be respected and that the system will maintain a safe state even when human assistance is delayed; (2) develop planning and learning algorithms that are cognizant of the availability of rich forms of human assistance and can effectively factor such assistive actions into the overall plan; (3) handle the high computational complexity of optimizing the interaction with humans under uncertainty and partial observability by creating a hierarchical multi-objective decision model; and (4) leverage human assistance to enable robust and accurate mapping and navigation in new areas, while reducing the reliance on human supervision over time. The project evaluates these capabilities in complex realistic settings involving a campus-scale robot deployment, a driving simulator, and autonomous vehicles in collaboration with Nissan.

Intelligent, interactive, and highly networked machines are a growing part of work and the workplace. Automation is moving from the factory floor to knowledge and service occupations. The potential benefits of technology include increased productivity and more job opportunities. But technology connected to work can also carry substantial social costs. The workshop supported by this award will promote the convergence of education, social and behavioral sciences, computational sciences, and engineering with stakeholders. This diverse group will define key research challenges that focus on the intersection of humans, technology, and work. Convergence is the deep integration of knowledge, theories, methods, and data from multiple fields to form new and expanded frameworks for addressing scientific and societal challenges and opportunities. Two workshops will address the future of work at the human-technology frontier. The workshops will focus on the challenges of shaping emergent technologies that are equitable. They will also consider how the technologies will engage a wider range of people in the workforce of the future. The results of the workshops will include reports, communication materials, and the organization of interdisciplinary panels at professional scientific meetings.

The specific focus of this workshop effort is on understanding the social and technical dimensions of new technologies. The goal is to develop a research agenda that will help us understand the challenges of shaping emergent technologies in ways that result in good jobs for a wide range of U.S. workers. This includes a workshop that will bring together expert scientists to consider (1) how the changing organization of work and technology affects income inequality; (2) how decisions are made in developing artificial intelligence and processes for human-technology partnerships; (3) how to develop methods for assessing emerging technologies in terms of likely work satisfaction and inequality in employment outcomes; and (4) how workforce development and economic systems can help make high-paying stable jobs widely available. The second workshop will include stakeholders and will focus on how to use these ideas at the local level.

Metareasoning is the process by which an intelligent agent monitors and controls its own thought processes so as to produce effective action in a timely manner. Just as people must decide when to stop thinking and take action, AI systems also need to be able to interrupt their decision-making process and commit to an action or plan. While people often use heuristic methods to determine the interruption time, this project offers metareasoning techniques that optimize the value of computation and stop planning when the urgency to take action outweighs the anticipated benefit of continued computation. The project transforms the ability of researchers and practitioners to create responsive planning systems by offering easy-to-use, off-the-shelf adaptive metareasoning techniques to control them. Additional areas of broader impact include mentoring of student researchers with special attention to underrepresented groups, a range of outreach activities to local schools, targeted activities to increase diversity in computer science, and industrial collaborations.

The approach uses planning algorithms that can be interrupted at any time, offering a tradeoff between runtime and quality of results. To take advantage of this tradeoff, novel metareasoning techniques are developed that overcome the drawbacks of existing methods. The key idea is to replace the reliance on extensive offline experiments by creating new ways to predict performance and adapt the prediction quickly to the specific problem instance at hand. The project answers fundamental questions about the feasibility, efficiency, and scalability of optimizing meta-level control with minimal computational overhead. The main contributions are: (1) online performance prediction methods for efficient meta-level control of anytime algorithms that outperform state-of-the-art methods; (2) a novel approach to create and adapt meta-level control policies online using reinforcement learning techniques; (3) extensions of the above methods to control a portfolio of anytime algorithms, allowing transitions from one algorithm to another using shared intermediate solution representations; and (4) extensions of the above methods to control the internal operation of adjustable anytime algorithms. The team evaluates the new metareasoning techniques on complex computational tasks using a range of anytime algorithms based on different programming paradigms and demonstrates ease of use and significant performance gains relative to existing metareasoning techniques.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

The NSF Convergence Accelerator supports team-based, multidisciplinary efforts that address challenges of national importance and show potential for deliverables in the near future.

The broader impact/potential benefit of this Convergence Accelerator Phase I project is to provide a software tool to guide individual workers in the US manufacturing workforce through the process of job selection and upskilling in their entire career. Due to the rapid development of workplace technology, such as robots and computer interfaces to machinery, future jobs require skills that are not taught in schools or standard training programs. Therefore, worker reskilling and retraining as part of the lifelong learning process is critical to the US economy and is a topic of national importance. The investigators will study this problem by collecting and analyzing data from a large partner corporation in the manufacturing industry and interviewing real workers and stakeholders; the proposed approaches will be tested by workers both employed by the partner corporation and recruited by a local partner city government. The investigators will integrate their expertise on computer science, educational technology, and social and economic analyses of the labor market to propose an effective, fair, and scalable software solution that can help a broad segment of workers in the US workforce, in both the manufacturing industry and beyond.

This Convergence Accelerator Phase I project aims at ultimately developing a framework that performs worker profile Diagnosis, training program RECommendation, and intelligent Training platform development (DIRECT) for the purpose of continuous workforce development. DIRECT is an integrated software tool that helps workers identify desirable future jobs, recommends training programs, and guides workers through the process of planning future career paths. It consists of four consecutive and intertwined components: (i) a skill level diagnosis and assessment component that uses cognitive models to assess worker skill levels from on-job data, (ii) a training experience development component that uses intelligent tutoring concepts to help workers acquire new skills, (iii) a skill gap identification component that uses labor market analysis to identify high-demand jobs and the skill gaps between a worker and their desirable job, and (iv) a future job and training program recommendation component that uses predictive artificial intelligence algorithms to connect workers to future jobs and select training programs to acquire the necessary skills. In Phase I of the project, the investigators will work with industry and government partners to formulate concrete research problems, identify data sources, develop prototypes, and conduct pilot studies to ensure that DIRECT is effective and practical.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

Artificial Intelligence (AI) is becoming ubiquitous in our daily lives. This frequent interaction between humans and AI, requires systems to be more cognizant of humans in the environment. This project develops a comprehensive approach for AI decision making in the presence of human observers. Without considering observers, AI systems could behave in a way that confuses, startles, or even threatens others. Humans often change their behavior in the presence of observers in a deliberate way, for example, to make their intention transparent and reassure an observer. Observer-aware behaviors may include explicit communication to convey intentions, for example, using hand gestures or light signals, as well as implicit communication through behavior. The project unifies a wide range of observer-aware behaviors designed to accomplish different goals, including legible behavior that implicitly conveys intentions via the choice of actions, explicable behavior that conforms to observers’ expectations, predictable behaviors that enable observers to predict future actions, as well as behaviors designed reveal the capabilities of the acting agent. These forms of observer-aware behaviors advance a key research priority in contemporary AI; that is, to produce human-centered systems that are easier to understand, predict, and collaborate.<br/><br/>This project introduces a new model to study observer-aware planning called Observer-Aware Markov Decision Process (OAMDP). This model develops novel automated planning techniques that can optimize observer-aware objectives beyond the scope of existing planning techniques. Specific contributions include: (1) analyses of the computational complexity of observer-aware planning under different assumptions and the theoretical and practical differences between OAMDP and existing models; (2) development of both exact and approximate algorithms for efficient observer-aware planning; (3) implementation and evaluation of belief-update methods compatible with how humans perceive AI systems; and (4) extensions of the approach to manage the tradeoffs between observer-related objectives (e.g., improving predictability of intentions) and domain-related objectives (e.g., reducing the completion time of the assigned task) and incorporate explicit communication between the agent and the observer. The overarching goals of this project are to develop a general automated planning approach that can achieve a range of observer-related strategic objectives, analyze the theoretical complexity of these problems, develop efficient algorithms for observer-aware planning, and validate them via experiments with human subjects in realistic settings. The team conducts a comprehensive evaluation of the new planning paradigm and demonstrates experimentally the value of observer-aware planning in realistic settings involving observers interacting with mobile robots and autonomous vehicles, including use cases developed in collaborations with industry partners.<br/><br/>This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.