NSF-BSF: RI: Small: Planning and Acting While Time Passes

规划允许智能系统选择旨在实现其目标的行动。 然而，传统的规划方法假设世界发展得足够慢，或者要解决的问题足够简单，在规划过程中世界可以被认为是静态的。 这种局限性意味着大多数当前的规划者都不能，例如，意识到快速找到一个次优计划来乘坐即将离开的公共汽车可能会更好，而不是仔细考虑最优计划，从而完全错过公共汽车。目前，规划表示和算法是费力地手动设计的，以确保系统对预期应用的响应足够快，基本上回避了系统规划时时间流逝的问题。 本项目通过开发新的“情境规划”方法，使其能够实现更强大和通用的智能系统，这些方法能够充分利用自己的推理来克服这一限制。 第一种是传统的批处理设置，在这种设置中，所有决策都在计划执行开始之前做出。 将解决三个挑战：1）形式化的规划模型，而时间的推移，并分析其计算复杂性，2）简化所产生的“推理推理”的问题，它可以近似重复解决在规划过程中，包括识别易处理的子类和贪婪算法，和3）估计所需的信息进行在线推理。第二种设置是增量计划，其中操作的执行可以与额外的计划交错。 将应对另外三个挑战：4）用行动成本形式化情境规划，5）开发一个持续的情境规划器，在执行计划时改进计划，6）解决在线情境规划，在那里，行动可以在一个完整的计划被发现之前被分派执行。解决这些情境计划问题将导致实际和灵活的计划者，可以顺利地插入在批量和增量之间以时间感知的方式适当地调整它们的行为，从而扩大智能系统可以解决的应用范围。 该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Planning allows intelligent systems to select actions aimed towards achieving their goals. However, traditional planning methods assume that the world evolves slowly enough, or that the problems to be solved are sufficiently simple, that the world can be considered static during planning. This limitation means that most current planners are unable, for example, to realize that it might be better to quickly find a suboptimal plan to take the bus that is about to leave, rather than to carefully deliberate about optimal plans and thereby miss the bus altogether. Currently, planning representations and algorithms are laboriously manually engineered to ensure that the system responds quickly enough for the intended application, essentially ducking the issue of the passage of time while the system is planning. This project enables more robust and general-purpose intelligent systems by developing new "situated planning" methods that reason about their own reasoning enough to overcome this limitation.The project will consider two settings for situated planning. The first is the traditional batch setting, in which all decisions are made before plan execution begins. Three challenges will be addressed: 1) Formalizing a model of planning while time passes and analyzing its computational complexity, 2) Simplifying the resulting "reasoning about reasoning" problem enough that it can be approximately solved repeatedly during the planning process, including identifying tractable subclasses and greedy heuristics, and 3) Estimating the information needed for doing this reasoning on-line. The second setting is incremental planning, where execution of actions can be interleaved with additional planning. Three additional challenges will be addressed: 4) Formalizing situated planning with action costs , 5) Developing a continual situated planner that improves a plan while it is being executed, and 6) Addressing online situated planning, where actions can be dispatched for execution before a complete plan has been found. Solving these situated planning problems will result in practical and flexible planners that can smoothly interpolate their behavior in a time-aware way between batch and incremental as appropriate, thereby broadening the range of applications that can be addressed by intelligent systems. Project results will be integrated into the open source OPTIC planner and ROSPlan robot control framework.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.