c++ - 按动态条件/约束过滤图
问题描述
我正在研究一种可以为机器人进行双向规划的图形结构。
但不仅是双向的,所以它可以从 A 到 B 和 B 到 A,还考虑到方向。所以在某些情况下,机器人只被允许沿着边缘向后移动。
从 4 开始,我可以朝着 1 前进。
但是从 1 开始到 4,我需要走路径 1>2>3>4,其中 3 是我可以改变方向的节点。就像一辆汽车单向倒退,并使用停车场将汽车掉头。
所以我有限制
- 我只能打开特定节点
- 规划节点时需要考虑机器人方向(节点有方向)
一种想法是在规划之前通过使用机器人的当前方向和目标的方向来过滤图形。但我还不确定这是否可能。
我的另一个想法是不过滤,并计划整个图表。
但是我通常不确定我的计划者(现在是 Dijkstra )是否可以处理它,而在计划期间机器人的方向可能会发生变化,例如在节点 3 中。
如果这是一个好主意,或者如果你能把我推向正确的方向,我会很高兴有人能给我一些一般性的提示。
解决方案
我会说您需要将图表分成两部分,一张包含所有前向链接,另一张包含所有后向链接。然后可以在可以转弯的节点处将这两个图连接起来,并且具有零成本链接。
从您的示例图中:
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
推荐阅读
- excel - 条件格式,如果不包含 x 或 y 则格式化?
- javascript - 从文件中解析js表
- sql - 通过表和其他表执行搜索与 SQL Server 中的外键连接的内容以及如何对数据进行排序
- python - PyGObject 是 Windows 和 Linux 上 Tk 的良好替代品吗?
- symfony - Symfony 4 使实体重新生成:没有变化
- python - 将 argparse 帮助发送到其他地方
- node.js - mongodb:虽然它在 shell 中工作,但不能将属性设置为 null
- ios - 如何使用swift同时模糊多个对象
- javascript - 如何以正确的纵横比显示响应式 5 扑克牌图像?
- c# - 如何获取通过类库项目中的服务引用引用的 XML 格式的 wcf 响应