0
0本资料主要探讨在非确定性模型下进行行动和规划的方法。它首先定义了非确定性规划域，引入了策略（policies）的概念及其不同类型（如不安全、安全、无环和循环策略），并详细介绍了寻找这些策略的各种算法。最后，文章讨论了在线规划方法以应对模型近似和大规模问题带来的挑战。
非确定性模型与规划域
- 非确定性模型定义: 非确定性规划域由三元组 (S, A, γ) 组成，其中 S 是状态集，A 是动作集，γ: S × A → 2^S 表示动作在给定状态下可能导致的所有下一个状态。
- 挑战: 非确定性动作的可能结果可能呈组合爆炸式增长，使得传统表示方法效率低下。
- 示例: 以“港口管理”为例，描述了物品从船上卸载到港口内移动的简化过程，展示了
park动作如何导致多个非确定性结果（parking1,parking2,transit1）。
策略及其类型
- 策略定义: 策略 π 是一个函数，将状态映射到可执行的动作 (π : S′ → A)，其中 S′ 是 S 的子集。
- 策略执行:
ActPolicy(π)算法描述了如何根据策略在当前状态下执行动作并观察新状态。 - 解决方案类型:解决方案 (Solution): 只要至少一个执行路径能到达目标状态即可。
安全策略 (Safe Policy): 保证从策略作用域内的任何状态出发，至少有一个执行路径能到达目标状态。
无环安全策略 (Acyclic Safe Policy): 策略图是无环的，且所有叶节点都是目标状态，保证最终到达目标。
循环安全策略 (Cyclic Safe Policy): 策略图可以有循环，但仍保证每个“公平”执行都能到达目标状态。
寻找解决方案的算法
- Find-Solution (查找不安全解决方案): 通过前向搜索找到一个可行的动作序列，不考虑所有可能的结果。
- Find-Acyclic-Solution (查找无环解决方案): 在查找过程中检查并避免循环，以确保找到的策略是无环的。
- Find-Safe-Solution (查找安全解决方案): 类似于
Find-Acyclic-Solution，但需检查并避免“不安全循环”，即无法逃脱的循环。 - Guided-Find-Safe-Solution (引导式查找安全解决方案): 迭代地寻找（可能不安全的）解决方案，并针对未达到目标的叶节点或死胡同进行修正，通过修改动作适用性来解决问题。
- Find-Safe-Solution-by-Determinization (通过确定化查找安全解决方案): 将非确定性动作转换为多个确定性动作（即“确定化”），然后使用经典规划器在确定化域中寻找解决方案，并将其转换回策略。
在线规划方法
- 动机: 规划模型通常是近似的，且非确定性会使规划时间和策略大小呈指数级增长，因此需要在线方法。
- Lookahead-Partial-Plan:
Run-Lazy-Lookahead的变体，执行部分规划，然后根据需要重新规划。 - FS-Replan:
Lookahead-Partial-Plan的特例，调用经典规划器在确定化域中生成计划，执行后若有需要则再次调用。 - Min-Max LRTA*: 在“安全可探索域”中（即从任何状态都能到达目标），通过选择具有最优最坏情况成本的动作并更新启发式函数，保证最终到达目标。
