パスを探す：SATを解く

Question

私たちはn * mのグリッドを与えられています。このグリッドには、ボットの始点と終点のさまざまな場所に障害物があります。タスクは、最初から最後まで衝突のないパスを見つけることです。この問題は、SATの問題としてモデル化されます。

この場合、最適な解決策を得るために何をすべきかを教えてください。

Answer 1

は、が最短を意味します。私はあなたが最初のステップを行うことができますhere説明してきた手法を使用する：

1. はグリッド
2. を定義し、あなたにソルバー戻り、この段階でランダムパスを充足タスク

を策定すべての制約を満たす。重要なことを覚えておいてください - 目標到達に必要なステップ数を定義することができます。k！ですから、k = 0で始まります。 0の行動で目標に到達することは可能ですか？おそらく、エージェントが目標に達するまで、そうではありません。それから、ちょうどインクリメントk = 1。今は可能ですか？そうでない場合は、さらに増やしてください！それを実装する方法は？ kの値をFalseに設定し、各繰り返しごとにこの制限を増やしてください。

上限がわかっている場合は、バイナリ検索を使用して可能な限り最短のパスを見つけることができます。

パスのその他のプロパティを気にする場合は、pseudo-boolean constraintsを使用できます。このアプローチを活用することで、たとえば右折回数を最小限に抑えることができます。 assumptionsを使用して、可能なすべての右折とブールカウンターを作成し、使用可能な回転数を制限します。