========================================= S P A C E - T I M E A S S I S T A N T : R E S P O N S E T O R F I ========================================= -------- 1. ADMIN -------- 1.1 WHO IS CURRENTLY IN YOUR TEAM? The Space-Time group includes the following members: Faculty: Jaime G. Carbonell (regular faculty), 15% Stephen F. Smith (research faculty), 10% Eugene Fink (systems faculty), 100% Graduate students: Ulas Bardak (Ph.D.), 100% Konstantin Salomatin (M.S.), 100% Steven Gardiner (M.S.), 100% Technical staff: Matt Jennings (research programmer), 100% Chia-chi Chuang (research programmer), 100% Undergraduate students: Vijay Prakash, 40% Franklin Ho, 40% 1.2 IF YOU HAVE UNFILLED POSITIONS, BY WHEN DO YOU EXPECT TO FILL THEM? The Space-Time Group does not have unfilled full-time positions, but it has two unfilled positions for part-time undergraduate assistants. We currently do not have suitable candidates for these positions, and we hope to fill them in the beginning of the Spring 2007 semester. ------------------------------------------------ 2. COMPONENT DESCRIPTION AND ENGINEERING PROCESS ------------------------------------------------ 2.1 WHAT IS THE FUNCTION OF YOUR COMPONENTS? Space-Time Module performs the following functions: () Constructs conference schedules and selects appropriate vendor orders based on the available uncertain data. () Supports optional collaboration between the user and automated scheduler. () Identifies critical missing data and generates related questions. 2.2 WHAT OTHER COMPONENTS USE DATA PROVIDED BY YOUR COMPONENT? Currently, the only component that uses data from Space-Time Module is Space-Time GUI, which allows the user to view and edit the schedule. 2.3 WHAT OTHER COMPONENTS PROVIDE DATA TO YOUR COMPONENT? Space-Time Module uses services of four other components: () It imports the world model from the database developed by Anthony Tomasic. () It accepts changes to the world model from GUI. () It imports the list of current vendor orders from the related NL-processing component, developed by Bob Frederking. () It calls CMRadar to obtain additional time slots. 2.4 WHAT FEATURES OF YOUR COMPONENT ARE PLANNED FOR Y3? The following features have been added during Year 3, and will be available for the use in the Y3 tests: () A new scheduling algorithm, which is about ten times faster than the Y2 algorithm. () An algorithm for selection of appropriate vendor orders. () A new algorithm for identifying critical missing data, which is significantly more accurate than the Y2 algorithm. () A new representation of conference events, which allows the specification of related constraints through intuitive event properties rather than through complex functions. () A library of common-sense assumptions about resources and constraints, and a basic mechanism for learning new assumptions. () An API for accessing the Space-Time data from other applications. The following features described in SOW will not be available for the use in the Y3 tests: () A "contingency scheduling" mechanism, which constructs alternative schedules for multiple hypothetical scenarios. () A mechanism for learning to collaborate with the user. () Opportunistic learning techniques. 2.5 WHAT FEATURES ARE IN THE DEVELOPMENT BUT WILL NOT BE READY UNTIL Y4? We are currently working on the following new features: () Construction of contingency schedules for different possible situations. () An advanced mechanism for learning common-sense assumptions. 2.6 WHAT DEVELOPMENT PROCESSES DO YOU HAVE IN PLACE FOR QUALITY ASSURANCE AND TO ENSURE ADHERENCE TO THE Y3 DEVELOPMENT SCHEDULE? We release an updated version of the system every one or two weeks, and one of the full-time group members (Blaze Iliev) is responsible for testing of each new version. Before each major release, we assign an additional group member to the testing. We keep a list of known bugs and missing features (www.cs.cmu.edu/~eugene/Radar/bugs.txt and www.cs.cmu.edu/~eugene/Radar/tasks.txt), and we re-test the system after each bug fix. We keep old versions of the source code in a SourceSafe version control. 2.7. WHAT DOES YOUR GROUP'S Y3 EFFORT DEPEND ON FOR SUCCESS? The Space-Time group depends on the GUI group for implementing the GUI extensions required to support new features of Space-Time Module. Since we already have a reasonably stable version of the system with most Year 3 features, and GUI supports all these features, the related risks seem low. The potential problems may also include unexpected major bugs and difficulties involved in integrating Space-Time Module into Radar; however, we believe that these problems are unlikely. ------ IMPACT ------ 3.1 HOW WILL YOUR CURRENT WORK IMPACT THE Y3 TEST? The main improvements implemented during Year 3 are as follows: () The system selects appropriate vendor orders, and learns additional data about vendors through the elicitation. This feature helps the users to place the right orders, which should lead to a significant increase of schedule quality. () The system learns common-sense assumptions about missing data, which also leads to increase of schedule quality. () The time of automated scheduling has been reduced from about sixty seconds to about six seconds. Since the user may need to invoke the scheduler multiple times, this improvement may lead to a noticeable time saving. We expect that it will improve the user experience, and allow the user to spend more time on other tasks. 3.2 HOW WILL YOUR CURRENT WORK IMPACT THE RADAR USER EXPERIENCE DIFFERENTLY AT THE END OF Y3 THAN AT THE END OF Y2? The system will help the user to select appropriate vendor orders. Also, the Y3 efficiency improvements will significantly reduce the waiting time. 3.3 WHAT DISTINGUISHES YOUR APPROACH AS COMPARED TO SIMILAR RESEARCH EFFORTS OR AVAILABLE PRODUCTS? We are not aware of off-the-shelf systems that provide any of the Space-Time functionality, such as optimization under uncertainty, elicitation, learning of common-sense assumptions, or related collaboration with the user. The main advantage over other research systems for representing uncertainty is that Space-Time Module allows fast optimization without sacrificing the expressiveness of the uncertainty representation. The main advantage over other research systems for elicitation is that Space-Time Module integrates the elicitation with optimizer, which allows the selection of questions that lead to the greatest expected increase of the schedule quality. Furthermore, the representation of uncertain data is more general than in other elicitation systems. In particular, it allows uncertainty in both resources and constraints, and supports continuous uncertain values and uncertain functions. 3.4 WHAT PLANS DO YOU HAVE TO IMPACT A MILITARY CUSTOMER? We expect that the developed techniques are applicable to reasoning about military logistics tasks; that is, we can use them to represent uncertain information about military resources and optimize the use of these resources. We have not yet analyzed specific military problems. 3.5 WHAT WOULD CONSTITUTE A "HOME RUN" FOR YOUR RESEARCH EFFORT? We will consider the Space-Time work a success if it leads to the following results: () The algorithms for automated scheduling and vendor-order selection are more effective than the best-performing human subjects. () The elicitation leads to a significant improvement of the results. () The learning of common-sense rules improves the performance, and gives better results than hand-coded rules. () The subjects report overall positive experience with the system. 3.6 IF YOU HAD TWICE AS MUCH MONEY IN Y4 AS YOU HAVE NOW, WHAT MORE COULD YOU DO? HOW ABOUT 3 OR 4 TIMES AS MUCH? If we had twice as much money, we would address the following problems during Year 4: () An advanced learning mechanism for improving the collaboration between Space-Time Module and human users, by learning strengths, weaknesses, and preferences of specific users. () An advanced mechanism for learning high-level planning and optimization strategies. () An advanced mechanism for learning new strategies involved in constructing contingency schedules. () Theoretical foundations of reasoning under uncertainty, and integration of theoretical and applied results. If we had even more resources, we would address the following problems: () Developing a library of multiple optimization and elicitation algorithms, and designing a top-level control for the co-ordination of these algorithms. () Developing techniques for learning of top-level control strategies. 3.7 IF YOU COULD DEFINE A DARPA PROGRAM TO FOLLOW-ON, WHAT WOULD IT BE? I feel that a "perfect" follow-up program would be continuation of the Radar project for several more years. I think that we have not fully investigated the main problems of reasoning under uncertainty, and the continuation of the Space-Time research may lead to significant new results. In particular, we may investigate new learning algorithms for reasoning under uncertainty, develop intelligent top-level control for the co-ordination of available modules, apply the system to other domains, and propose a formal theory of handling uncertain and surprising data.