Graphplan

Rust 中 Graphplan 规划算法和 Plangraph 数据结构的实现。

原始论文：由 Avrim L. Blum 和 Merrick L. Furst 撰写的《通过规划图分析进行快速规划》: Fast Planning Through Planning Graph Analysis

示例

以下是一个使用 Graphplan 组成的示例计划。我们描述了 'morning' 领域作为初始状态（称为 'propositions'），动作（具有前提条件和改变状态的效应）以及目标状态。

let p1 = Proposition::from("tired");
let not_p1 = p1.negate();

let p2 = Proposition::from("dog needs to pee");
let not_p2 = p2.negate();

let p3 = Proposition::from("at work");
let p4 = p3.negate();

let a1 = Action::new(
    "drink coffee",
    hashset!{&p1},
    hashset!{&not_p1}
);

let a2 = Action::new(
    "walk dog",
    hashset!{&p2, &not_p1},
    hashset!{&not_p2},
);

let a3 = Action::new(
    "go to work",
    hashset!{&not_p1, &not_p2},
    hashset!{&p3},
);

let domain = GraphPlan::create_domain(
    hashset!{&p1, &p2, &p4},
    hashset!{&not_p1, &not_p2, &p3},
    hashset!{&a1, &a2, &a3}
);
let mut pg = GraphPlan::from_domain(&domain);

println!("Plan:");

for step in pg.search::<SimpleSolver>().unwrap() {
    for action in step {
        println!("- {:?}", action.id);
    }
}

高级用法

有限动作

有时你希望有一组可以静态检查的动作。为了做到这一点，你可以使用自己的 ActionId，它将用于唯一标识一个 Action。例如

#[derive(Debug, Clone, Hash, PartialEq, Eq, Ord, PartialOrd)]
pub enum MyAction {
    Drink,
    Eat,
}

let p1 = Proposition::from("hungry");
let p2 = p1.negate();
let p3 = Proposition::from("thirsty");
let p4 = p3.negate();

let a1 = Action::new(
  MyAction::Eat,
  hashset!{&p1},
  hashset!{&p2},
);

let a2 = Action::new(
  MyAction::Drink,
  hashset!{&p3},
  hashset!{&p4},
);

现在我们的规划器知道将只有 MyAction 集的动作。这在你需要迭代计划并希望从中获得穷举性检查的好处时特别有用。当你添加新动作时，你会得到一个编译时错误，表明你忘记了处理你的新动作。

在动作中嵌入数据

有时我们还想附加一些与 GraphPlan 无关但方便传递的数据。为此，你可以使用枚举变体的关联数据。

#[derive(Debug, Clone, Hash, PartialEq, Eq, Ord, PartialOrd)]
pub struct LocationId(String);

#[derive(Debug, Clone, Hash, PartialEq, Eq, Ord, PartialOrd)]
pub enum MyAction {
    Move(LocationId),
}

let p1 = Proposition::from("location1");

let a1 = Action::new(
  MyAction::Move(LocationId(String::from("1"))),
  hashset!{},
  hashset!{&p1},
);

现在调用者可以在处理返回的计划时访问动作的关联数据（这特定于你的程序）。这避免了大量的样板代码，因为它防止了在 GraphPlan 之外包装以将动作映射到你的程序的需要。

有限命题

同样，你也可以使用自己的类型作为 Proposition 的标识符。

例如

#[derive(PartialEq, Clone, Hash, Eq)]
enum MyPropositions {
    A,
    B,
}

impl From<MyPropositions> for Proposition<MyPropositions> {
    fn from(prop: MyPropositions) -> Self {
        Self::new(prop, false)
    }
}

let p1 = Proposition::from(Props::A);
let p2 = Proposition::from(Props::B);

// We can now use it with an action
let action = Action::new(
  "my action ID",
  hashset!{&p1},
  hashset!{&p2},
);

运行基准测试

使用 criterion 的基准测试可以在 benches 目录中找到。要运行它们

cargo bench --features toml
open target/criterion/report/index.html

运行示例

cargo run --example morning

许可证

版权（c）Alex Kehayias。保留所有权利。此软件的使用和分发条款受 Eclipse 公共许可证 1.0（http://opensource.org/licenses/eclipse-1.0.php）的约束。通过以任何方式使用此软件，您同意受此许可证条款的约束。您不得从该软件中移除此通知或任何其他通知。