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

规划允许智能系统选择旨在实现其目标的行动。然而，传统的规划方法假设世界演变得足够慢，或者需要解决的问题足够简单，所以在规划过程中世界可以被认为是静态的。例如，这种限制意味着大多数当前的计划者无法意识到，快速找到一个次优计划来乘坐即将离开的公交车，而不是仔细考虑最优计划，从而完全错过公交车，可能更好。目前，规划表示和算法都是人工费力地设计的，以确保系统对预期应用的响应足够快，基本上避免了系统在规划时的时间流逝问题。这个项目通过开发新的“情境规划”方法来实现更强大和通用的智能系统，这些方法充分地推理了它们自己的推理，以克服这一限制。该项目将考虑两个情境规划的设置。第一种是传统的批处理设置，在这种设置中，所有决策都是在计划执行开始之前做出的。将解决三个挑战：1)形式化随时间推移的规划模型并分析其计算复杂性；2)充分简化所产生的推理问题，使其在规划过程中可以近似地重复求解，包括识别易处理的子类和贪婪启发式算法；以及3)估计在线进行这种推理所需的信息。第二种设置是增量计划，在这种情况下，行动的执行可以与额外的计划交织在一起。将解决三个额外的挑战：4)将情境规划与行动成本正式化，5)开发一个连续的情境规划器，在计划执行时对其进行改进，以及6)解决在线情境规划，其中可以在找到完整的计划之前调度行动以供执行。解决这些情景计划问题将产生实用而灵活的计划者，他们可以在适当的时候以时间感知的方式在批量和增量之间平滑地插入他们的行为，从而拓宽了智能系统可以解决的应用范围。项目成果将被整合到开源光学规划器和ROSPlan机器人控制框架中。该奖项反映了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.