Generating Plan Graph

[Samcheok]

Hi,

I've been struggling with time for computing esterel plan graph since I posted the question #118 last July.

The flow is Generated plan =>..=> createGraph() -> addIntererenceEdge() -> getBounds() => ...

The trouble spot taking for a while is getBounds() function, below is time for generating graph for MapAnalyzer domain from IPC.

Could you please let let me know the algorithm for addIntererenceEdge() -> getBounds()?

Presuming that it may be easier to figure out the reason for duration, if I know the algorithm.

Thanks in advance!

[m312z]

Hello Kyeongseok,

Definitely the algorithm needs to be improved in the plan parser. The function of the algorithm is to (1) check for mutual exclusions between nodes to generate the partial ordering, and then (2) to calculate the lower and upper duration bounds for each ordering.

We've not run into the same behaviour with our plans of similar sizes. Having seen your plan PDFs, I wonder if part of the issue is the concurrency that appears in your plans. Are you able to send us your domain and problem files for testing?

Thanks, Michael

Note for assignee: I referenced this as well in my reply to #142 and I'll close #141 (where other details are provided).

[jqs7328]

Hi, Michael,

Here are the cases you requested --

Some test results are attached including domain file, problem files, and plans from temporal track in IPC 2014. LPG_td planner is used to generate plans, thus so plans are concurrent plans.

MapAnalyzer_result.zip

Thanks in advance!

[Samcheok]

Hello Michael,

Wondering if you have looked at the time table with mapAnalyzer domain, which was posted a week ago.

You said that you haven't experienced such a case of taking long time to make a plan graph, but I presume that you get the same elapsed time with the domain. So, have you figured it out and can sort it out?

I am very anxious to know how you think about the problem and there is any possibility to fix it easily.

Any comments would be appreciated very much.

-- Kyeongseok Kim

[m312z]

Hello Kyeongseok Kim,

I've had a look at them now. The problems are large enough that I cannot solve them on my laptop (I am away from my main PC at the moment). Using the plans you sent, I do get the same long time for parsing.

The issue is the efficiency of the code. The implementation to generate the causal and interference edges is very straightforward and does not cache as much as it could. The issue is added to our to-do list on the project board, and we'll try to fix it soon.

Michael

[Samcheok]

Hello Michael,

Because of this problem, we've been considering other platform, leaving ROSPlan.

Happy to hear you are about to fix it soon. Looking forward to it !

-- Kyeongseok Kim

[oscar-lima]

Removing getBounds function:

After internal discussion at KCL with Michael, we saw that getBounds function could potentially be removed with the following advantages/consequences (pros and cons):

1. Con: in addInterferenceEdges function we would now check for interference edges in all iterations.

2. Pro: Esterel plan graph is generated faster. e.g. problem P10-10-10-1-1 you get a reduction in time from 2 hour 25 min to 1 min 22 sec.

3. Con: Esterel rqt cannot visualize the graph: Is just too big! even if you save the graph to a file and try to open with xdot, it crashes.

4. Con? : It produces a different esterel plan with more (redundant?) edges, the question is if those esterel plans are equivalent. e.g. see image below

[donghosong]

Hi Oscar-Lima,

Thank you for your discussion on how to improve the estral graph based on the analysis of pros and cons.

From my perspective,

1. The visualized graph might be required for the purposes of debugging and displaying progress status info. So, visualizing the graph is necessary for me. As far as the graph is generated correctly within a reasonable elapsed time by your revised codes I appreciate for that. As you mentioned earlier, if size of a graph is too big to be handled by xdot that issue will be sorted out separately.

2. It is OK taking up to 5 min. elapsed time to generate a BIG graph if you can make it

3. Regarding #4, the two attached graphs would work the same in functional point of view but the original graph looks better, isn't it? Since esterel plan graphs are being used for visualization purposes, I would prefer the left graph which get rid of redundant edges.

Looking forward to have your updated codes soon.

Dongho

[m312z]

Hello Oscar, Dongho,

Let's do the following:

1. Open up a PR now with the fix. As you say, this will drastically reduce the time taken to parse the plan, at the cost of some redundant edges in the graph. I think it is important for people to get this as soon as possible.
2. We can then prune these edges in a post-processing step for a second PR afterwards.

Michael

[oscar-lima]

TODO: Implement efficient algorithm to prune extra edges.

If interference edge candidate "c" (in blue) pretends to connect nodes A and B (A being source node and B being sink node) then candidate can be discarded if it exists an alternative path connecting A and B (e.g. ax1, x1x2, x2x3, x3b)

[oscar-lima]

Implemented already efficient algorithm to prune extra edges. See #161

[bilal9876]

the output data is not correct.

rostopic echo /rosplan_plan_dispatcher/plan_graph data: "digraph plan {\n0[ label=\"plan_start\",style=filled,fillcolor=black,fontcolor=white];\n\ 1[ label=\"undock_start\n(kenny,wp0)\"];\n2[ label=\"undock_end\n(kenny,wp0)\"];\n\ 3[ label=\"localise_start\n(kenny)\"];\n4[ label=\"localise_end\n(kenny)\"];\n5[\ \ label=\"goto_waypoint_start\n(kenny,wp0,wp0)\"];\n6[ label=\"goto_waypoint_end\n\ (kenny,wp0,wp0)\"];\n7[ label=\"goto_waypoint_start\n(kenny,wp0,wp1)\"];\n8[ label=\"\ goto_waypoint_end\n(kenny,wp0,wp1)\"];\n9[ label=\"goto_waypoint_start\n(kenny,wp1,wp0)\"\

[m312z]

Depending upon where the message is printed, you may want to add the "-p" flag to rostopic echo.

[bilal9876]

Depending upon where the message is printed, you may want to add the "-p" flag to rostopic echo.

thank you. it is solved and the output is correct now.