MODIFICATION
A -- REAL-WORLD REASONING (REAL)
- Notice Date
- 7/8/2003
- Notice Type
- Modification
- Contracting Office
- Other Defense Agencies, Defense Advanced Research Projects Agency, Contracts Management Office, 3701 North Fairfax Drive, Arlington, VA, 22203-1714
- ZIP Code
- 22203-1714
- Solicitation Number
- BAA03-34
- Response Due
- 7/6/2004
- Archive Date
- 7/21/2004
- Point of Contact
- Sri Kumar, DARPA Program Manager, Phone 000-000-0000, Fax 703-741-7804,
- E-Mail Address
-
none
- Description
- The DARPA Information Processing Technology Office (IPTO) solicits innovative proposals for a new program on Real-World Reasoning. A principal mission of IPTO, launched at DARPA in 2002, is to create the technologies critical to building practical cognitive information processing systems. Developing innovative machine reasoning technology that can effectively deal with the real world is central to this mission. The objective of the REAL-WORLD REASONING (REAL) program is to explore and develop foundations, technology, and tools to enable effective, practical automated reasoning of the scale and complexity required for computers to perform complex tasks in the real world requiring intelligence. Effective, ?real-world? machine reasoning requires inference in environments that are far more complex in scale and scope than those tackled by current machine reasoning methods. Enduring real-world systems need to deal with vast amounts of knowledge and information, often concerning dynamic and intentional phenomena. In addition, beliefs about the environment are often uncertain and involve plausible but not provable assumptions. The REAL program solicits innovative research efforts that can make fundamental and breakthrough advances in real-world reasoning to deal with these and related problems. Research efforts must implement the algorithms and technology in specific testbeds, and demonstrate novel capabilities for real-world reasoning. Specifically, the program intends to: 1. Develop and demonstrate innovative techniques that push the envelope of performance of reasoning engines, in terms of the scale of the problems that can be dealt with, and the speed and correctness of reasoning. 2. Explore, develop, and demonstrate novel methods that extend the breadth of reasoning to deal with a. Uncertain and dynamic environments where the knowledge base is characterized by uncertain and temporally changing information; and,b.Strategic environments characterized by goals and intentions of many interacting agents and actors, in both cooperative and non-cooperative contexts. 3.Build and demonstrate embedded reasoners for active knowledge bases that recognize the commonalities and similarities among multiple ontologies, and combine and merge them, so as to enable well-informed reasoning through the exploitation of all information in the knowledge base. The program duration is anticipated to be five years. The research plan for this BAA is structured in three phases. The Phase I effort is planned for an 18-month period; Phase II, for 18 months thereafter; and Phase III, for the final 24 months of the program. For each phase, proposals should clearly identify and describe the project?s goals, approaches, milestones, testbeds, demonstrations, and cost. Proposers must structure their proposals to fit into one, two, or all of the three phases. Proposers MUST obtain a copy of the Proposer Information Pamphlet (PIP), and respond to ALL items in the PIP when preparing the proposal. A copy of the PIP may be obtained from: http://www.darpa.mil/ipto/Solicitations/index.html Research is sought in the following three topics: Topic 1: High-performance reasoning techniques Topic 2: Expanding the breadth of reasoning and hybrid methods Topic 3: Embedded reasoners for active knowledge bases Proposals may address one or more of the above topics, but must clearly identify the topics addressed and describe the proposed research for each separately. In the following, the topics are described in detail. Topic 1: High-performance reasoning techniques We seek innovative research efforts that explore and develop methods that push the envelope of performance of reasoning engines. Metrics to measure performance should be clearly specified in the proposal, including the scale of the underlying knowledge bases for the reasoning environment (such as number of entities, variables, rules, etc.), the speed of answering queries (for example, query response time using a 1-GHz processor), and the correctness in answering queries (such as fraction of queries answered correctly in a specified time interval). It is desired that the Phase I research emphasize new high-performance inference methods for propositional knowledge bases. It is suggested that later phases build on the successes of core research in Phase I, and this includes extending the research to further performance improvements in propositional knowledge bases, as well as to high-performance reasoning in other systems such as first-order and higher-order logic, or fragments of such systems. Proposals should clearly specify the performance targets, outline the technical approaches, and clearly present arguments and evidence to establish how the proposed approaches have the potential of reaching the specified target performance. Methods for high performance may be based on any technical approach, but generic applicability to any knowledge base is important, and in particular for any propositional system in Phase I. Of particular interest are approaches based on models of computational complexity that characterize the computational hardness profile, or regimes of different complexities, of a given reasoning situation. Such an approach may exploit the hardness profile of a problem, and the knowledge base structure, to design new reasoning architectures and computationally tractable inference methods to deal with intrinsically high-complexity regimes, via systematic and well-characterized approximations or modifications of the reasoning environment, while minimally compromising other desirable dimensions of performance. Generic learning methods that enable scaling and speed-up of inference in any context are also of interest, as are methods that exploit combinations and interactions of different knowledge representations, and parallel reasoning, to obtain performance gains. Proposals should quantify the performance targets for reasoning methods, in each phase. For example, a target for Phase I may be the ability to perform reasoning in propositional knowledge bases in excess of 10K variables and 40K rules, with 85 percent or higher rate of questions answered correctly, and a query response time of seconds on a 2.5-GHz processor. In Phases II and III, proposals may address methods for further performance scaling of propositional reasoning (for example, Phase II might address methods for improving query response time in a knowledge base ten times the size of knowledge bases considered in Phase I, with a Phase III scaling target of an additional ten times or more), and improved rate of correct answers (for example, in excess of 90%). Extensions to other knowledge bases such as first-order logic and fragments of such systems are also of interest in later phases. While this example is suggestive of the specification of performance targets, bidders are encouraged to propose all key relevant performance targets and methods that push the performance envelope maximally. Proposed new reasoning methods should be demonstrated in a testbed. While performers may adopt their own testbed for developing their ideas for generic high-performance reasoning (which should be described in the proposal), DARPA is interested in testing and evaluating the reasoning methods to be developed in each phase of this topic in a common testbed. Performers will be required to demonstrate their new methods in such a common testbed, which will be made available to the performers. Such a common testbed may be drawn, for example, from the domain of chess, where the reasoning challenge problems may involve answering queries such as whether or not there exists a checkmate in a specified number of moves, starting from a mid-game position with a specified number and types of pieces for each player, within a specified response time window (for example, five seconds on a 2.5-GHz processor), and with associated explanations. Proposers are strongly encouraged to translate their proposed milestones to specific capabilities to be accomplished in the above mid-game chess problem (for example, Phase I target may translate as follows: finding the existence of a checkmate in ten moves with five pieces for each player placed in arbitrary positions on the board). While this common testbed may be drawn from the domain of chess, it should be noted that the program emphasizes generic reasoning methods and not techniques specific to the testbed domain. Topic 2: Expanding the breadth of reasoning and hybrid methods. The goal of research in this topic is to develop foundations and methods that significantly expand the breadth of reasoning critical to practical cognitive information processing systems. This includes developing efficient techniques for reasoning in uncertain, dynamic, and intentional environments, as well as hybrid reasoning methods. Strategic reasoning methods and tools that support reasoning in multi-player contexts are also of interest. This topic comprises three sub-topics: Reasoning in uncertain and dynamic environments: Research is sought in the development of efficient and scalable methods for temporal reasoning under uncertainty for large knowledge bases. Of interest are methods for effectively representing uncertain information and relations among temporally evolving entities, as well as algorithms that support rich query-processing and predictive reasoning. Methods for assessing the states of unobserved entities in partially observed systems are of interest. Fast inference methods that can scale to large knowledge bases are important. Proposals should specify the target knowledge base size, and target query response time (say, on a 1-GHz processor). Approaches may include dynamic Bayesian networks that exploit the inference problem structure, and the use of systematic approximations. Non-monotonic reasoning methods that can effectively deal with dynamic changes to identities of items in the knowledge base, and deontic reasoning to deal with changes to the rules are also of interest. Proposals should clearly identify the metrics and milestones, and describe the testbed and demonstrations for program phases, and how the proposed approaches can potentially meet the milestones. For example, a Phase I target may be to develop and demonstrate the foundations and methods for temporal reasoning under uncertainty in a knowledge base of a certain size (e.g., 10K state variables), target response time on a specified processor (e.g., order of seconds on a 1-GHz processor), and error in state estimation (e.g., less than 10 per cent). Further scaling (e.g., 10X, 100X knowledge base size) and improvements in metrics may be addressed in additional phases. Proposals that address non-monotonic and deontic reasoning should specify the metrics and milestones, capturing the underlying implementation tradeoffs. Hybrid reasoning: The goal in this topic is to develop innovative methods for hybrid reasoning that effectively combine multiple methods of reasoning to exploit advantages provided by different approaches. Example approaches include deductive inference, probabilistic reasoning, temporal reasoning, reasoning by analogy, etc. Methods that combine mental models with logic reasoners to exploit potential advantages of human-like reasoning, as well as methods for combining multiple theories, are also of interest. Hybrid reasoners that act on different partitions of the knowledge base (for example, partitioning by domain, time, and space), and methods for efficient dynamic composition of reasoners, are also solicited. Also of interest are hybrid methods that combine probabilistic and relational reasoning. Proposals must clearly identify approaches to addressing the technical challenges, and describe the metrics, milestones, and testbed for demonstrations, in each phase. An example milestone may be to develop and demonstrate, in Phase I, a hybrid reasoning system with specified types of interacting reasoners in a knowledge base of certain size (e.g., 100K variables), with order of seconds query response time on a 1-GHz processor, and demonstrate performance benefits and new functionality not possible otherwise. It is suggested that research in Phases II and III address combining methods that are successfully developed in Phase I. Strategic Reasoning: The goal of this topic is to develop methods for reasoning in strategic multi-player or multi-agent contexts where agents may be cooperative or non-cooperative. This includes tools for strategic reasoning that a) enhance reasoning ability to support intelligent individual decision-making in multi-player contexts, and b) that support composition of multi-player games to enable simulation-based analysis and reasoning. Interdisciplinary research that exploits and extends game theory for reasoning in dynamic strategic interactions involving many players in a hierarchy is of interest. Interactions may range from coalition-formation to bargaining to bidding and auction games. Strategic reasoning methods, applicable to a broad spectrum of strategic contexts, must address techniques to represent game models compactly, to ascertain best responses, and to predict game outcomes and dynamics. Developing tools for composing dynamic hierarchical games, including the development of a language for the specification and composition of games, is of interest. Proposals must be structured to address novel basic and core research in Phase I, with substantial extensions undertaken in later phases. Proposals should clearly specify the metrics and milestones for each phase. It is desired that in Phase I, proposals emphasize development of methods for compact representation of games, efficient algorithms for computing stable and predictable outcomes in games with large state spaces (target processing time and state space should be specified), and a framework and testbed for composing games for simulation and analysis. The emphases in Phases II and III will be on scaling strategic reasoning tools to game contexts of several hundred agents; incorporating probabilistic, temporal, and hybrid reasoners into individual or agent decision processes; developing rapid game composition capability and distributed play; and demonstrating the value of strategic reasoning in DOD contexts such as logistics and war-gaming. Topic 3: Embedded reasoners for active knowledge bases Research is sought in innovative methods for reasoners that can be embedded in knowledge bases with multiple ontologies to support efficient and well-informed reasoning. Functionally, embedded reasoners should enable the maximal exploitation of information present in the knowledge base for efficient query response. Of interest are methods that reason across multiple large ontologies, and dynamically recognize similarities, overlap, and divergence in the relations and structure of the different ontologies. Methods that rapidly and effectively join, combine, and merge large ontologies are of interest. The technical approaches to developing embedded reasoners should be clearly explained, and these may include, but are not limited to, graph matching and isomorphism algorithms. Proposals should clearly specify the metrics and milestones, and testbed and demonstration plans, for each phase, capturing key dimensions of performance such as time to combine and merge ontologies of given sizes at a given processing speed. For example, a Phase I milestone may be to combine and merge two arbitrary ontologies, each having tens of thousands of entries, within seconds on a 1-GHz processor; and Phases II and III may focus on further scaling, as well combining ontologies with temporal, probabilistic, and other types of information. PROGRAM SCOPE Proposed research should investigate innovative approaches and techniques that lead to or enable revolutionary advances in the state-of-the-art. Proposals are not limited to the specific strategies listed above, and alternative visions will be considered. However, proposals should be for research that substantially contributes towards the goals stated. Research should result in prototype software and/or hardware demonstrating integrated concepts and approaches. In Phase II, DARPA may specify one or more common testbeds for the whole program, and performers are required to integrate and demonstrate their technology in such testbeds. Specifically excluded is research that primarily results in minor evolutionary improvement to the existing state of practice or focuses on special-purpose systems or narrow applications. Integrated solution sets embodying significant technological advances are strongly encouraged over narrowly defined research endeavors. Proposals may involve multiple research groups or industrial cooperation and cost sharing. GENERAL INFORMATION The Defense Advanced Research Projects Agency/Information Processing Technology Office (DARPA/IPTO) requires completion of a Broad Agency Announcement (BAA) Cover Sheet Submission for each Proposal, by accessing the URL below: http://www.dyncorp-is.com/BAA/index.asp?BAAid=03-34 After finalizing the BAA Cover Sheet Submission, the proposer must print the BAA Confirmation Sheet that will automatically appear on the web page. Each proposer is responsible for printing the BAA Confirmation Sheet and attaching it to the "original" and each designated number of copies. The Confirmation Sheet should be the first page of your Proposal. If a proposer intends to submit more than one Proposal, a unique UserId and password should be used in creating each BAA Cover Sheet. Failure to comply with these submission procedures may result in the submission not being evaluated. NEW REQUIREMENTS/PROCEDURES: The Award Document for each proposal selected and funded will contain a mandatory requirement for submission of DARPA/IPTO Quarterly Status Reports and an Annual Project Summary Report. These reports will be electronically submitted via the DARPA/IPTO Technical ? Financial Information Management System (T-FIMS), utilizing the government furnished Uniform Resource Locator (URL) on the World Wide Web (WWW). Further details may be found in the Proposer Information Pamphlet (PIP). Proposers must submit an original and 2 paper copies of the full proposal, and 6 electronic copies in Microsoft Word ?97 for IBM-compatible or PDF format. Each electronic copy must be on a separate disk or CD. Each disk must be clearly labeled with BAA 03-34, proposer organization, proposal title (short title recommended) and ?Copy ___ of 6.? The full proposal (original and designated number of hard and electronic copies) must be submitted in time to reach DARPA by the initial closing deadline of 12:00 NOON (ET) September 4, 2003, to be considered for the initial evaluation phase. However, BAA 03-34, REAL, will remain open until 12:00 NOON (ET) July 6, 2004. While the proposals submitted after September 4, 2003 deadline will be evaluated by the Government, proposers should keep in mind that the likelihood of funding such proposals is less than for those submitted by the initial closing date. DARPA will acknowledge receipt of submissions and assign control numbers that should be used in all further correspondence regarding proposals. Proposers must obtain the BAA 03-34 Proposer Information Pamphlet (PIP), which provides further information on the areas of interest, submission, evaluation, funding processes, and proposal formats. This pamphlet will be posted directly to FedBizOpps.gov and may also be obtained by fax, electronic mail, mail request to the administrative contact address given below, or at URL address http://www.darpa.mil/ipto/Solicitations/index.html. Proposals not meeting the format described in the pamphlet may not be reviewed. This notice, in conjunction with the BAA 03-34 PIP and all references, constitutes the total BAA. No additional information is available, nor will a formal RFP or other solicitation regarding this announcement be issued. Requests for same will be disregarded. The Government reserves the right to select for award all, some, or none of the proposals received. All responsible sources capable of satisfying the Government's needs may submit a proposal that shall be considered by DARPA. Historically Black Colleges and Universities (HBCUs) and Minority Institutions (MIs) are encouraged to submit proposals and join others in submitting proposals. However, no portion of this BAA will be set aside for HBCU and MI participation due to the impracticality of reserving discrete or severable areas of this research for exclusive competition among these entities. Evaluation of proposals will be accomplished through a scientific review of each proposal using the following criteria, which are listed in descending order of relative importance (detailed descriptions of the criteria are contained in the PIP): (1) Overall Scientific and Technical Merit. (2) Innovative Technical Solution to the Problem. (3) Potential Contribution and Relevance to the DARPA. (5) Plans and Capability to Accomplish Technology Transition. (6) Cost Realism. All administrative correspondence and questions on this solicitation, including requests for information on submitting a proposal to this BAA, must be received at one of the administrative addresses below by 12:00 NOON (ET) June 29, 2004; e-mail or fax is preferred. DARPA intends to use electronic mail and fax for some of the correspondence regarding BAA 03-34. Proposals MUST NOT be submitted by fax or e-mail; any so sent will be disregarded. All proposals, administrative correspondence, and questions submitted must be in the English language. Submissions received in other than English shall be rejected. The administrative addresses for this BAA are: Fax: 703-741-7804 Addressed to: DARPA/IPTO, BAA 03-34 Electronic Mail: baa03-34@darpa.mil Electronic File Retrieval: http://www.darpa.mil/ipto/Solicitations/index.html Mail to:DARPA/IPTO ATTN: BAA 03-34 3701 N. Fairfax Drive Arlington, VA 22203-1714
- Record
- SN00366571-W 20030710/030708214141 (fbodaily.com)
- Source
-
FedBizOpps.gov Link to This Notice
(may not be valid after Archive Date)
| FSG Index | This Issue's Index | Today's FBO Daily Index Page |