按动态条件/约束过滤图形
Filter a graph by dynamic conditions / constraints
我正在研究一种可以为机器人进行双向规划的图结构。
但不仅是双向的，所以它可以从 A 到 B，从 B 到 A，同时还要考虑方向。所以在某些场景下，机器人只允许沿边缘向后移动。
看这个例子：
从 4 开始，我可以向 1 前进。
但是从 1 开始到 4，我需要走路径 1>2>3>4，其中 3 是我可以改变方向的节点。就像一辆车单向倒退，利用停车场掉头。
所以我有
的约束
- 我只能打开特定节点
- 规划节点时需要考虑机器人方向（节点有方向）
一个想法是在规划之前通过使用机器人的当前方向和目标的方向来过滤图形。但我还不确定这是否可能。
我的另一个想法是不过滤，而是对整个图进行规划。
但我通常不确定我的规划器（现在是 Dijkstra）是否可以处理它，因为在规划期间机器人的方向可以改变，就像在节点 3 中一样。
如果有人能给我一些一般性的提示，如果这是个好主意，或者如果你能推动我朝着正确的方向前进，我会很高兴。
我会说你需要将你的图表分成两份，一份包含所有前向 link，一份包含所有后向 link。然后可以在可以转弯的节点处连接这两个图，成本为零 link.
来自您的示例图表：
Forward links
1F - 2F
2F - 4F
4F - 3F
Backwards links
1B - 2B
2B - 3B
Turning links
3F - 3B
从 1F 开始，目标是 3F 或 3B，Dijsktra 会找到
1F - 2F - 4F - 3F - 3B
最终可以简化为
1 - 2 - 4 - 3
当机器人从 1 开始面向前方并朝向 4 时的示例输出（机器人可以直接通过 2 到达那里）
C:\Users\James\code\unirobot\bin>unirobot.exe inforward.txt
unirobot
l 1 2 0
l 2 3 2
l 2 4 1
l 4 3 1
t 3
s 1 f
g 4
4 bidirectional links input
Forward links
1f - 2f
2f - 4f
4f - 3f
Back links
1b - 2b
2b - 3b
Turning Links
3f - 3b
Combined graph links
(1f,2f) (2f,1f) (2f,4f) (4f,2f) (4f,3f) (3f,4f) (3f,3b) (1b,2b) (2b,1b) (2b,3b) (3b,2b) (3b,3f)
Path: 1f -> 2f -> 4f ->
从 1 开始面向后向 4 时的示例输出（机器人需要经过节点 3，这是它唯一可以转身的地方）
C:\Users\James\code\unirobot\bin>unirobot.exe inbackward.txt
unirobot
l 1 2 0
l 2 3 2
l 2 4 1
l 4 3 1
t 3
s 1 b
g 4
4 bidirectional links input
Forward links
1f - 2f
2f - 4f
4f - 3f
Back links
1b - 2b
2b - 3b
Turning Links
3f - 3b
Combined graph links
(1f,2f) (2f,1f) (2f,4f) (4f,2f) (4f,3f) (3f,4f) (3f,3b) (1b,2b) (2b,1b) (2b,3b) (3b,2b) (3b,3f)
Path: 1b -> 2b -> 3b -> 3f -> 4f ->
生成此输出的代码位于 https://github.com/JamesBremner/unirobot
我正在研究一种可以为机器人进行双向规划的图结构。
但不仅是双向的，所以它可以从 A 到 B，从 B 到 A，同时还要考虑方向。所以在某些场景下，机器人只允许沿边缘向后移动。
看这个例子：
从 4 开始，我可以向 1 前进。
但是从 1 开始到 4，我需要走路径 1>2>3>4，其中 3 是我可以改变方向的节点。就像一辆车单向倒退，利用停车场掉头。
所以我有
的约束- 我只能打开特定节点
- 规划节点时需要考虑机器人方向（节点有方向）
一个想法是在规划之前通过使用机器人的当前方向和目标的方向来过滤图形。但我还不确定这是否可能。
我的另一个想法是不过滤，而是对整个图进行规划。
但我通常不确定我的规划器（现在是 Dijkstra）是否可以处理它，因为在规划期间机器人的方向可以改变，就像在节点 3 中一样。
如果有人能给我一些一般性的提示，如果这是个好主意，或者如果你能推动我朝着正确的方向前进，我会很高兴。
我会说你需要将你的图表分成两份，一份包含所有前向 link，一份包含所有后向 link。然后可以在可以转弯的节点处连接这两个图，成本为零 link.
来自您的示例图表：
Forward links
1F - 2F
2F - 4F
4F - 3F
Backwards links
1B - 2B
2B - 3B
Turning links
3F - 3B
从 1F 开始，目标是 3F 或 3B，Dijsktra 会找到
1F - 2F - 4F - 3F - 3B
最终可以简化为
1 - 2 - 4 - 3
当机器人从 1 开始面向前方并朝向 4 时的示例输出（机器人可以直接通过 2 到达那里）
C:\Users\James\code\unirobot\bin>unirobot.exe inforward.txt
unirobot
l 1 2 0
l 2 3 2
l 2 4 1
l 4 3 1
t 3
s 1 f
g 4
4 bidirectional links input
Forward links
1f - 2f
2f - 4f
4f - 3f
Back links
1b - 2b
2b - 3b
Turning Links
3f - 3b
Combined graph links
(1f,2f) (2f,1f) (2f,4f) (4f,2f) (4f,3f) (3f,4f) (3f,3b) (1b,2b) (2b,1b) (2b,3b) (3b,2b) (3b,3f)
Path: 1f -> 2f -> 4f ->
从 1 开始面向后向 4 时的示例输出（机器人需要经过节点 3，这是它唯一可以转身的地方）
C:\Users\James\code\unirobot\bin>unirobot.exe inbackward.txt
unirobot
l 1 2 0
l 2 3 2
l 2 4 1
l 4 3 1
t 3
s 1 b
g 4
4 bidirectional links input
Forward links
1f - 2f
2f - 4f
4f - 3f
Back links
1b - 2b
2b - 3b
Turning Links
3f - 3b
Combined graph links
(1f,2f) (2f,1f) (2f,4f) (4f,2f) (4f,3f) (3f,4f) (3f,3b) (1b,2b) (2b,1b) (2b,3b) (3b,2b) (3b,3f)
Path: 1b -> 2b -> 3b -> 3f -> 4f ->
生成此输出的代码位于 https://github.com/JamesBremner/unirobot