1

我目前正在开发一个答案集编程问题，包括一个机器人，该机器人需要覆盖一个房间以避免障碍物并在所有房间都被覆盖时到达目标点。我的想法是将房间地图转换为 asp 谓词，以 room/3 的形式，作为参数：

  • X:x 坐标
  • Y:y 坐标
  • V：房间内点的值，分别为0（初始点），1（覆盖点），2（障碍物），3（目标点）

程序必须满足的标准之一是覆盖值为 1 的每个点，这可以通过约束来实现，但我不知道如何对机器人运动进行建模。我的想法是使用 move/1 形式的谓词，向上、向下、向左或向右。

任何人都可以帮助我指导我如何建模这个问题吗？

    void map_to_asp(std::ofstream& file,std::vector<std::vector<char>>& room)
{
  std::cout << room.size() << "," << room[0].size() << std::endl;
  for(int i = 0; i < room.size(); i++)
  {
    for(int j = 0;j < room[0].size(); j++)
    {
      switch(room[i][j])
      {
        case '@':
        file << "initial(" << i+1 << "," << j+1 << ").\n";
        break;
        case '.':
        file << "toClean(" << i+1 << "," << j+1 << ").\n";
        break;
        case '#':
        file << "obstacle(" << i+1 << "," << j+1 << ").\n";
        break;
        case 'X':
        file << "goal(" << i+1 << "," << j+1 << ").\n";
        break;
      }
    }
  }
}

先感谢您。

4

1 回答 1

0

如果您的目标是为每个可能的路径建立一个模型，一个简单的方法是在图中进行迭代。

我们首先需要定义我们可以移动的所有位置（我们实际上是在解决任何问题之前构建一个图表）：

position(X,Y,S):- room(X,Y,S) ; not S=2.

现在我们决定我们可以从任何位置（图的边缘）去哪里：

edge((X,Y),(I,J)):- position(X,Y,_) ; position(I,J,_) ; |X-I|=0..1 ; |Y-J|=0..1 ; |X-I|+|Y-J|=1..2 .

请注意，我们认为该图是无向的（例如，如果您的房间里有幻灯片，则不一定正确）。让我们定义一些常量：

#const start_pos=(1,1).
#const goal=(5,5).
#const path_maxlen=100.

我们显然是从起点开始的：

path(1,start_pos).

现在，我们递归地指出下一条路要走，有一个限制，以避免太无用的解决方案。

0{path(N+1,E): path(N,S), edge(S,E), S!=goal}1:- path(N,_) ; N<path_maxlen.

我们必须避免所有无用的路径。

% a path that do not join the end is illegal.
:- path(N,E) ; not path(N+1,_) ; not E=goal.

% a path must go by all milestone (example of milestone: milestone(2,14)).
:- not path(_,(X,Y)): milestone(X,Y).

我们想要最短路径：

last_step(N):- path(N,_) ; not path(N+1,_).
#minimize{N: last_step(N)}.

完整代码可在此处获得。

作为旁注：

  • 由于我们不使用它们，您可以（应该）摆脱所有描述障碍物的房间/3。
  • 你也可以让你的目标点是人造的（在房间外面，但真正的目标是与之相连的），以便让你的路径通过真正的目标，而不会停下来。使用它，您可以实现对多个目标的支持。
于 2018-04-29T13:56:38.950 回答