Sven Koenig - US grants

This is the first year of funding of a 4-year continuing award. Preference models determine which one of several plans to prefer. It is important that planners use the same preference models as human decision makers because planners should make the same decisions as their human users, otherwise the planners are not of much use. The PI will investigate how to build planners that fit the preference models of human decision makers better than current planners, by combining constructive methods from artificial intelligence with more descriptive methods from utility theory in order to take advantage of the strengths of the two decision-making disciplines and to extend the applicability of Al planners. The PI will study optimal vs. good or near-optimal ("satisficing") planning with a variety of preference models. He win explore how to exploit the structure of complex sequential planning tasks to solve them efficiently for realistic preference models suggested by utility theory, with an emphasis on preference models in high-stakes decision situations. To this end, he will focus on representation changes that make use of existing planners from AI by transforming planning tasks with nonlinear utility functions into others that these planning methods can solve, and will study the errors that result for the original planning task when satisficing planning methods are used instead. The research will be performed in the context of managing environmental crisis situations, such as cleaning-up marine oil-spills.

In this Information Technology Research (ITR) research project, a study of the design and use of auction mechanisms for the allocation of scarce resources in complex settings will be performed. The research includes four specific goals: (1) the design and development of appropriate bidding environments, (2) the identification of participants bidding strategies under well defined bidding environments, (3) the development of an understanding of the tradeoffs between computational complexity and "goodness" of solution under various bidding environments, and (4) the development of an educational program and educational tools for teaching the theory and practice of auctions. Amid the wide range of settings where bidding mechanisms are utilized, attention will be focused on four important applications spanning the range of issues that can arise in a bidding environment: (1) simple multi-unit auctions in e-commerce, (2) combinatorial auctions in industrial procurement, (3) coordination and control of multiple robots in uncertain environments, and (4) task allocation on a logistics network for ocean carriers. In essence, an auction is a mechanism by which a set of participants communicates information so as to result in a set of allocations taking place. Information that is communicated by a participant is called a bid. The auction designer strives to design a mechanism that has desirable characteristics, appropriate for the situation at hand. Auctions can particularly benefit environments with the following two characteristics: (1) the absence of complete information about the participants and (2) problems which cannot be solved centrally due to their high computational complexity. While the use of auctions has been applied in numerous market settings, the research in auction theory has severely lagged behind. There is little in the literature to guide bidders on how to "optimally" bid or to aid auctioneers in evaluating the performance of various auction formats. Even the auction consultants will admit that much of their advice is based on logic and past experiences, rather than rooted in analytical findings. It is the goal of this research to close the gap between practice and theory by advancing the state of the knowledge in the design of auction mechanisms for the allocation of scarce resources in complex settings.

The successful completion of this research will broaden the understanding and use of multi-unit auctions as a transaction medium and increase the efficacy of such transactions. Since the researchers will be working closely with industry partners including IBM, Home Depot, Schneider Logistics, and Orient Overseas Container Line (OOCL), the research will be focused on realistic applications. There will also be a significant educational impact in terms of case study development, new course offerings, and the development of classroom bidding games.

This is the first year funding of a three year continuing award. A variety of on-line planning methods are used in artificial intelligence including, for example, real-time search methods such as LRTA*, reinforcement-learning methods such as Q-learning, and robot-navigation methods such as D*. The PIs intend to improve the performance of these and other on-line planning methods substantially so that, for example, future robot-navigation methods will be able to map unknown terrain significantly faster than is now possible, yet have the same advantageous properties as existing on-line planning methods. Many on-line planning methods, either always or most of the time, execute actions that move the agent in the perceived direction of the goal, that is, move the agent so that it reduces the estimates of the goal distances the most. However, the PIs preliminary theoretical results show that executing actions that move the agent in the perceived direction of the goal is usually not a good idea. For example, D* does not reach a goal location in unknown terrain with a minimal travel distance in the worst case. The key to improving the performance of these on-line planning methods then is to exploit the distance estimates that they maintain (or can maintain) in a way that is more directly related to the planning or learning objective. The PIs will study the properties of on-line planning methods both theoretically and experimentally, and will develop improved on-line planning methods that have the same interface as the existing methods, which allows users of these methods to easily substitute the new methods for the ones they are currently using. Side benefits of the proposed research include developing a test-bed for the experimental evaluation of robot navigation methods in unknown terrain, and creating a solid theoretical foundation for understanding robot-navigation methods in unknown terrain, including D*.

This project will develop incremental heuristic search methods, study their properties analytically and experimentally, and demonstrate their applicability and advantages for different artificial intelligence applications, including symbolic planning problems, reinforcement-learning problems, and control problems. Heuristic search methods are widely used in artificial intelligence. They find shortest paths for graph search problems much faster than uninformed search methods. Incremental search methods, on the other hand, are almost unknown in artificial intelligence. They find shortest paths for series of similar graph search problems much faster than is possible by solving each graph search problem from scratch. Incremental heuristic search methods have four advantageous properties:

1. Incremental heuristic search techniques speed up replanning substantially since they combine two different principles for speeding up the search. They can speed up replanning by one to two orders of magnitude compared to replanning from scratch. This is important because replanning problems are often time critical and have large state spaces.

2. The quality of the plans that result from replanning with incremental heuristic search techniques is as good as the quality of the plans that result from planning from scratch. This property is an important difference to many conventional replanning methods (such as case-based planning, planning by analogy, plan adaptation, transformational planning, planning by solution replay, and repair-based planning) that usually cannot make guarantees about the resulting plan quality.

3. Incremental heuristic search techniques are very versatile and apply, for example, to symbolic planning problems, path-planning problems, reinforcement-learning problems, and control problems.

4. Heuristic incremental search techniques have a solid theoretical foundation and thus well-understood properties. Their simplicity allows one to prove a number of properties about them, including their termination, correctness, efficiency, and similarity to A*, which makes them easy to understand, easy to analyze, easy to program, easy to optimize for efficiency, and easy to extend. Incremental heuristic search methods have the potential to improve a variety of artificial intelligence applications, that might, for example, result in decision-support systems with smaller response times but higher quality plans than is possible today, in crisis situations such as marine oil spills.

The research results will be made available to a broad audience by presenting them at conferences, on web pages, and via tutorials. The project will improve the education of graduate students, undergraduate students, high-school students, and minority students (mostly by volunteering for educational activities). For example, interested undergraduate students will be very actively involved in the research.

Collaborative Research: Coordinating Robot Teams using Market-Based Mechanisms

In the near future, teams of robots will take on tasks in initially unknown environments where human presence is not possible due to safety or cost reasons, including applications where robots have to visit or cover areas in initially unknown terrain, such as mine sweeping and de-mining, search and rescue operations after earthquakes, the exploration of distant planets, and hazardous material cleaning. The efficient and robust coordination of the robots is imperative for all of these scenarios. This project develops and implements methods for the dynamic assignment and re-assignment of tasks to robot teams through the use of combinatorial auctions in the context of exploration tasks in initially unknown environments. Previous work has demonstrated the use of single-item auctions for multi-robot task allocation, in which robots bid on tasks that are auctioned off one at a time. Unfortunately, single-item auctions do not take synergies between tasks into account, which can result in suboptimal task allocations and poor team performance. This project studies more complex auctions, including combinatorial auctions, where robots bid on bundles of tasks. Initial feasibility studies show that combinatorial auctions generally lead to significantly superior team performance compared to single-item auctions, and generate very good results compared to optimal centralized methods. The project focuses on combinatorial bidding strategies which result in team behavior that is efficient, effective, adaptable to dynamic environments, and robust in the presence of error conditions. It also studies alternative winner determination methods for various objective functions, such as minimizing the total travel distance (or energy consumption) and the total time to task completion. This interdisciplinary project between robotics and auction researchers will produce both theoretical and experimental results, in particular, new methods with theoretical analyses of their correctness and efficiency and their demonstration on both simple and complex multi-robot exploration scenarios with real-time requirements. The students involved in this research will learn to work as part of an interdisciplinary team and will deepen their understanding of two usually separate areas of research.

The project kick-starts an international symposium series on the topic of heuristic search. Currently, work in this area appears scattered across many conferences in several fields. The intellectual merit of this project stems from the sharing of new results, ideas, and problems across the many areas in AI and robotics where heuristic search is used. Broad impact comes not only from this intermixing but from having a single locus of activity for efforts in heuristic search, one that we expect to become known in the wider community as the place to look when one wants a snapshot of the latest developments in the area. The first symposium will be held as a AAAI workshop in 2008. NSF funding supports student participation and invited speakers, and there is the expectation that the symposium series will be self-sustaining by 2010.

The project is the second in an international symposium series on the topic of combinatorial search. Currently, work in this area appears scattered across many conferences in several fields. The intellectual merit of this project stems from the sharing of new results, ideas, and problems across the many areas in AI and robotics where combinatorial search is used. Broad impact comes not only from this intermixing but from having a single locus of activity for efforts in combinatorial search, one that we expect to become known in the wider community as the place to look when one wants a snapshot of the latest developments in the area. The first symposium will be held as a AAAI workshop in 2008. This second meeting in the series is held just before and in the vicinity of the International Joint Conference for Artificial Intelligence in 2009. NSF funding supports authors of oral and poster presentations, as well as invited speakers.

In this project, the PI studies any-angle search methods. Any-angle search methods are variants of the heuristic search method A* that interleave the search with path optimizations by propagating information only along grid edges (to achieve small runtimes) but without constraining the paths to grid edges (to find short "any-angle" paths, namely paths whose headings can change by any angle). The objective of this project is to broaden any-angle search from a few isolated search methods to a well-understood framework and to extend its applicability. To this end, the PI is developing new any-angle search methods and analyzing their properties, which is complicated by the fact that even base properties often do not transfer from A* to them. The team will also evaluate all new and existing any-angle search methods against each other and against alternative search methods, for example, to understand how they trade off among runtime, path length and memory consumption.

Any-angle search is a recent search paradigm that promises to result in a new class of powerful path-planning methods for mobile robots, including underwater and aerial vehicles. The project includes dissemination activities to raise awareness of any-angle search in artificial intelligence and robotics (such as via tutorials, open-source code and web applets) and offers research opportunities to both graduate and undergraduate students.

Planning is one of the key technologies in robotics. Yet, robots are deployed in only a small number of niche areas, and most deployed robots have very minimal planning capability. This workshop discusses how the field of robot planning should progress to make robots deployable more widely, performing more novel tasks and relying less on human supervision. It brings together researchers from robotics, artificial intelligence, and related research disciplines to discuss the state of the art in planning, its use in various robotic applications and current research challenges. By studying planning research across different applications, analyzing planning challenges as part of complete robot architectures, and discussing the interaction of planning with other robot modules (such as perception, control, and user interfaces), the workshop participants will gain new insights into how planning can help robots become more robust and efficient. The workshop consists of invited talks, breakout sessions, panels and a final discussion aiming to converge on the roadmap for the field of robot planning that will be summarized in a report. The report and all presentations will be posted on the workshop website. The workshop is expected to stimulate future research towards robot planning in the real world and have strong potential to enable advances in all areas of robotics, from home assistance to medicine to exploration to manufacturing.

Robots need to improve their behavior over time, yet produce consistent behavior in order to allow humans to predict their actions, which is necessary to develop trust in their behavior or even cooperate with them. Furthermore, many tasks repeat, such as opening drawers. This project develops technology that addresses these issues by viewing planning as a lifelong process and exploiting the structure of human environments for efficiency, for example that drawers typically open in similar ways.

This research collaboration is developing a framework for lifelong planning based on experience graphs that aims to improve performance of planning over time by exploiting past experiences when solving similar planning tasks. The concept is novel because experiences are used to guide the heuristic search as opposed to be used for mere replay or adaptation. The idea that makes this possible is a novel heuristic search-based framework that can take advantage of prior experiences and still provide rigorous guarantees on completeness and path quality. The team studies how experiences can be utilized effectively during planning, how planning should gather experiences, how it should prune redundant experiences and how it can obtain experiences from demonstrations. Applications include everyday household tasks and low-volume manufacturing tasks. The software developed in this collaborative research is being integrated into the SBPL library, one of the core libraries in ROS. The project also incorporates educational activities as well as activities that help to bridge the research communities in robotics and artificial intelligence, two separate communities despite their common interest in autonomous systems.

The proposal requests travel, housing funding and conference registration for US-based doctoral students selected to participate in the Doctoral Consortium (DC). The DC is co-located with The 25th International Conference on Automated Planning and Scheduling (ICAPS), which will be held in Jerusalem in May 4-8, 2015. ICAPS is the main international conference on automated planning. The ICAPS DC aims at broadening the participating of US-based PhD students into the planning area as well as improving the retention of these students.

How can multi-robot teams maneuver in tight and cluttered environments when "no plan survives contact" with reality? Traditional approaches plan for idealized situations and must patch up maneuvers when sensors or actuators are imprecise, making them neither robust nor safe. This project, a collaboration of PIs from artificial intelligence and robotics, will investigate fundamental research to capture and use timing and uncertainty constraints in large robot navigation and coordination problems. The target applications are just-in-time manufacturing and automated warehousing, but the results will extend beyond to many applications of smart and autonomous systems that need reliable and safe planning.

The project will study Multi-Agent Path Finding (MAPF), which is an NP-hard planning problem that belongs to a class of important planning problems, namely multi-agent navigation problems with temporal and spatial constraints. The research will relax simplifying assumptions typically made by MAPF solvers, namely that plan execution is perfect and stops once all robots have reached their goal locations. Many AI planning methods that have been developed are not used on robots, since planning/scheduling uses idealized models of the environment and plan execution is never perfect, and there is often insufficient time for re-planning if execution deviates from the plan. This project will develop well-founded planning and plan-execution methods, based on probabilistic and temporal reasoning, that fuse ideas from robotics and artificial intelligence. In particular, the PIs will combine advances in planning algorithms from the AI community, namely Simple Temporal Networks (STN), and adapt them to the robotics domain by adding timely execution constraints, as well as sensor, actuator, and model uncertainties. They will make project results (such as papers, videos and code) available on their web pages, present tutorials on their research results to the artificial intelligence and robotics research communities, develop teaching material for multi-robot planning, and integrate undergraduate students into their research activities.

Good algorithmic foundations for flight planning on the scale required for managing dense urban drone traffic we can expect to see in the future are currently still missing. This project provides prototype algorithms for managing this dense drone traffic. The project develops a concept for a coordination system that is able to find collision-free paths for a large number of flying unmanned air vehicles of different size and capability. It uses a hierarchical approach, combining centralized and local coordination, to manage complexity for a large-scale problem. The approach developed here can scale up to handle thousands of drones and lead to conflict free flight. It demonstrates the concept using mixed-reality simulations and using existing helicopter-like robots on a smaller scale.

Current multi-robot trajectory-planning algorithms typically operate on a single level (which limits their scalability) and assume holonomic robots that can hover motionlessly (which limits their applicability). The core of the project is the development of a novel hierarchical system that addresses these limitations, combining centralized methods with a divide-and-conquer approach. The hierarchical approach allows the system to negotiate collision-free trajectories on a local level, while ensuring that robots complete their tasks on the global level. Additional research integrates several speed-up techniques into the hierarchical system and generalizes its functionality, for example, to accommodate robots of different priorities (such as drones that deliver blood to hospitals). The research involves not only graduate but also undergraduate students and trains them in cross-disciplinary research.

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.

With the increased use of automated vehicles in manufacturing, warehousing, and other environments, it is important to ensure that the plans taken by the automated agents controlling these vehicles are both efficient and safe. That is, we want to minimize the cost of travel while ensuring that agents will not collide with each other or the environment. This project will focus particularly on approaches for planning in environments where the number of agents is limited, but the cost of failure is high. For instance, in an airport there are relatively few airplanes moving on the tarmac at any one time, but the cost of collisions is large. The project will develop efficient and robust approaches that can be used to control agents in these environments. When these approaches are complete, this will enable new applications for the deployment of automated agents that can reduce the cost and pollution of current systems while increasing their efficiency and safety.

Existing algorithms for centralized control of agents have three drawbacks. First, they often make restrictive assumptions about the environment, such as axis-aligned movement with unit-cost actions. Second, the optimal approaches do not scale to large numbers of agents and the fastest algorithms have poor solution quality. Third, these algorithms are only well-defined in fixed scenarios where there is a clear distinction between plan formation and execution. This project will address these limitations by developing new algorithms. These approaches will handle more realistic agent models, such as robotic movement on a state lattice, they will compute near-optimal solutions to ensure that they scale to significantly larger scenarios, and they will be adapted to run on online problems where agents can enter or exit the world and where plan execution is imprecise and must be adapted based on real-world restrictions.

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.

This project will contribute to the national need for well-educated engineers and technicians in production engineering, specifically in advanced manufacturing. Advanced manufacturing is key to keeping U. S. manufacturers competitive by reducing cost, improving quality, and producing innovative products based on new technologies. The project will support the design, deployment, and evaluation of an advanced manufacturing curriculum that integrates advanced systems engineering concepts. This curriculum will consist of a set of modular, online courses designed to serve working professionals, as well as students at two-year and four-year colleges or universities. To ensure industry and community college participation, the project will be conducted by the University of Southern California in collaboration with East Los Angeles Community College, Los Angeles City College, Santa Monica College, Los Angeles Trade Technical College, and the Industry Advisory Board for the USC Viterbi Center for Advanced Manufacturing. An innovative aspect of the curriculum is its use of telepresence and simulation technologies to provide students with virtual design and testing experiences when they do not have access to physical laboratories. As a result, the project has the potential to provide important results about the effectiveness of virtual laboratory experiences as substitutes or enhancements for hands-on experiences. In addition, because the curriculum will allow students to learn course content remotely and is easily scalable, it has the potential to reach thousands of students across the globe.

The overall goal of this project is to design, develop, and deploy online curricula to accelerate training of the U. S. workforce in the critical systems engineering skills area and its application to advanced manufacturing. The first aim is to identify the required competencies in the systems engineering-related areas that are needed for the workforce in advanced manufacturing enterprises. Second, the project plans to develop modular courses that integrate relevant simulation-based and telepresence-based experiments to improve comprehension and retention of content during online delivery. Third, the project will conduct a research-based assessment of the courses. Specifically, it will investigate the effectiveness of a challenge-based, guided experiential learning pedagogical approach in an online context at the two-year college, four-year college, and professional settings. The research will be grounded in social cognitive and socio-constructivist learning theories, using guided experiential learning as its instructional framework. The project will use grounded assessments including multidimensional challenge-focused rubrics, checklists and student concept inventories and questionnaires to measure faculty use of guided experiential learning pedagogy and students' subject mastery and attitudes. This project will be evaluated using a formative and summative mixed methods approach, using information from an independent advisory group, students, and faculty via surveys and focus groups. Results of this project will be delivered as open educational resources using a web-based repository.

This project is funded by NSF's EHR Core Research: Production Engineering Education and Research (ECR: PEER) program, which seeks to improve the education of future and current professionals in production engineering. It also aims to study the effectiveness of the innovative educational strategies adopted by these projects.

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.

This project develops faster search algorithms for route-planning problems where multiple cost measures are used to determine the best solutions. For example, when transporting hazardous goods it is important to consider both the duration and safety of a route. Other applications include planning power-transmission lines, inspection and manipulation planning in robotics, scheduling satellites, and routing packets in computer networks. These bi- and multi-objective search algorithms work by maintaining many paths from the given start location to each location encountered during the search. This approach currently prevents them from solving realistically sized problems in real-time. This project both investigates techniques for speeding them up to realistic problem sizes and develops new benchmark instances for evaluating their performance. It is part of an international collaboration that also includes the exchange of personnel and the development of educational material.

Bi-objective (and multi-objective) search algorithms allow the cost of every graph edge to be quantified by two (or more) real values. They essentially assume that one wants to find the set of all paths, called the Pareto frontier, such that each path in the set is better than all other paths from a given start vertex to a given goal vertex with respect to the sum of at least one cost component of its edges (or equally good with respect to all cost components). The researchers of this project work on finding synergies between ideas from existing bi-objective search algorithms and recent algorithmic developments in the artificial intelligence search community to develop the next generation of optimal and approximately-optimal bi-objective search algorithms. They are also working on generalizing their bi-objective search algorithms to multi-objective search algorithms and applying them in the context of transportation and robotics.

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.