Filter a graph by dynamic conditions / constraints

user_356538 0
Viewed 54

I am researching for a graph structure which can plan bidirectional for robots.
But not only bidirectional, so it can go from A to B and B to A, also taking the orientation into account. So in some scenarios the robot is only allowed to move backwards oriented along the edge.

See this example: example

Starting at 4, I can go forwards oriented to 1.
But starting at 1 and going to 4, I need to take path 1>2>3>4, where 3 is a node where I can change direction. Like a car going backwards in a one-way and using a parking lot to turn the car around.

So I have the constraints that

  • I can turn only on specific nodes
  • The robots orientation needs to be taken into account when planning to a node ( node has a orientation )

One idea is to filter the graph before planning by using the robot's current orientation and the target's orientation. But I am not yet sure if this is possible.

And my other idea is to not filter, and plan over the whole graph.

But I am generally not sure if my planner ( right now Dijkstra ) can handle it, when during planning the robot's orientation can change, like in Node 3.

I would be glad if someone could give me some general hints if this is a good idea or if you could push me in the right direction.

boost-graph graph-theory c++
1 Answers

I would say that you need to split your graph into two, one with all the forward links and one with all the backward links. These two graphs can then be joined at the nodes where turning is possible, with a zero cost link.

From your sample graph:

Forward links

1F - 2F
2F - 4F
4F - 3F

Backwards links

1B - 2B
2B - 3B

Turning links

3F - 3B

Starting at 1F and aiming for 3F OR 3B, Dijsktra will find

1F - 2F - 4F - 3F - 3B

which can finally be simplified to

1 - 2 - 4 - 3

Sample output when robot starts at 1 facing forwards and heading for 4 ( the robot can get there directly via 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 ->

Sample output when starts at 1 facing backwards and heading for 4 ( The robot needs to go via node 3, the only place it can turn around )

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 ->

The code that generates this output is at https://github.com/JamesBremner/unirobot

user_165820
Related