shootingstar (#18) - route starts off in wrong direction / in direction of first edge (#339) - Message List

route starts off in wrong direction / in direction of first edge

Dear all,

I have a problem that shortest_path_shooting_star / shootingstar_sp takes into account the direction of the first edge even though the edge is not marked as one way and reverse_cost = to_cost.

I made a screen shot of the problem:  http://mobilino.de/umstaendliche_route.png here the route contains a nonsense-circle at the start, the route should have gone strait northwards.

To explain the problem in lyric: you may calculate a route from edge A to edge to Z, which is from north to south: If A's line-string is leading from south to north the route will always start off in that direction. Eventually it does a U-turn at the end of the first edge, or it simply leads you in a big curve to your goal.

However, the correct solution would have been to start directly into the other direction, that is south!

Can anyone confirm this problem and knows of possible solutions?

Best regards, Christof

  • Message #1392

    Hi,

    the route should have gone strait northwards.

    of course I meant southwards...

    Regards, Christof

    • Message #1393

      Indeed this looks not correct. Can you make sure that the network is correct? Sometimes OSM mappers "draw" more than create some valid topology. Does the "loop" consist of only one line feature or more than one?

      • Message #1394

        Hi,

        thanks for your reply.

        This is the SQL and the Result: as .png:  http://mobilino.de/umstaendliche_route_sql.png as .txt:  http://mobilino.de/umstaendliche_route_sql.txt

        I understand that the loop consists of more then one way. (you may see the repetition of the first gid in edge No 8 of the route or compare the street names to the map)

        Can you spot any problem with my data?

        Looking forward to your reply, Christof

        • Message #1395

          Hey Chistof,

          ... sorry, this reply is off-topic but are you from Hamburg/Iserbrook?

          • Message #1396

            Hey Christof,

            I tried to reproduce this routing behavior but with dijkstra instead of shooting* and everything is fine. Another thing is the incorrect osm-tagging of this way, so I hope your converter has segmentized it correctly. Another hint is the bidirectional-parameter in your call. Could it be, that you are starting with the wrong direction?

            Greetings

            Carsten

            • Message #1398

              Hi Carsten,

              thanks a lot for your investigation!

              If I remember correctly a* is also working fine. However, I switched to shooting* as the documentation recommends it for "real road networks".

              Sorry, but what exactly do you mean by "incorrect osm-tagging of this way"? Is my data incorrect / not suitable for shooting*? I produced it using osm2pgrouting, with the patch discussed here http://pgrouting.postlbs.org/discussion/message/1239#1239 (but I don't feel that that patch has anything to do with my current problem)

              Finally, what do you mean by "bidirectional-parameter"? Scanning the documentation for that word did not really help me to understand what you are referring to. All I can say is yes, I'm starting in the wrong direction. But how can I change that?

              I'm looking forward to your point of view. Kind Regards, Christof

              • Message #1399

                I'm living in PI(-Mapper) = Pinneberg, not far from HH where I'm working * guess * as programmer. (Lust auf 'ne Tasse Bier und ueber OSM quatschen?)

                Greetings,

                Carsten

              • Message #1400

                Hi Carsten, thanks a lot for your investigation! If I remember correctly a* is also working fine. However, I switched to shooting* as the documentation recommends it for "real road networks". Sorry, but what exactly do you mean by "incorrect osm-tagging of this way"? Is my data incorrect / not suitable for shooting*? I produced it using osm2pgrouting, with the patch discussed here http://pgrouting.postlbs.org/discussion/message/1239#1239 (but I don't feel that that patch has anything to do with my current problem) Finally, what do you mean by "bidirectional-parameter"? Scanning the documentation for that word did not really help me to understand what you are referring to. All I can say is yes, I'm starting in the wrong direction. But how can I change that?

                As I remember the last but one parameter (..., true, ...) means, you are dealing with a directed graph. If I'm not totally wrong this means your topology should have two entries for each way, each for one direction. So my assumption was, you might have started your virtual car on the wrong hand side of the street. But in the meantime I had another closer look on the data table and I noticed that this cannot be the intrinsic reason.

                I'm looking forward to your point of view. Kind Regards, Christof

                • Message #1402

                  Hi Carsten,

                  As I remember the last but one parameter (..., true, ...) means, you are dealing with a directed graph. If I'm not totally wrong this means your topology should have two entries for each way, each for one direction.

                  Using false instead of true does not change the result :-( But thanks for the idea! As the edge occurs twice in the result  http://mobilino.de/umstaendliche_route_sql.png once in each direction (no. 1 and no. 8) I feel that the reason can't be that it has to occur twice.

                  But in the meantime I had another closer look on the data table and I noticed that this cannot be the intrinsic reason.

                  Are there any other ideas out there?

                  Kind Regards, Christof Ps: @Carsten: gerne! christof_osm bei lahorn.de

                  • Message #1403

                    Hi Carsten,

                    As I remember the last but one parameter (..., true, ...) means, you are dealing with a directed graph. If I'm not totally wrong this means your topology should have two entries for each way, each for one direction.

                    Using false instead of true does not change the result :-( But thanks for the idea! As the edge occurs twice in the result  http://mobilino.de/umstaendliche_route_sql.png once in each direction (no. 1 and no. 8) I feel that the reason can't be that it has to occur twice.

                    But in the meantime I had another closer look on the data table and I noticed that this cannot be the intrinsic reason.

                    Are there any other ideas out there? Kind Regards, Christof Ps: @Carsten: gerne! christof_osm bei lahorn.de

                    you can c o n t a c t me directly via cmindividual(KlammerAffe?)web(Punkt)de

                    In the meantime I tried out shortest_path_shooting_star without wrapper and it works correctly. Ok, I'm still using an old version of pgrouting. The other difference to your data is that I'm using a non directed graph created with my own converter. Furthermore I left the rule and to_cost blank (null). What's driving me crazy at this point is finding a correct join syntax in sql to keep the order of the routing when joining the data_table. Maybe you can help me here.

                    • Message #1404

                      Huh, very long thread here!

                      It's a bit hard to pick the right posts now, but just two comments:

                      • The latest version of shooting_star_smart SQL wrapper might work better. There were some bugs in previous version, which might have been similar to yours. It can become quite tricky to always select the right substring, since you initially don't know where you will go.
                      • At least in trunk version you should be able to sort by "id" attribute to get the right order ... I think it was called "id"

                      As you said you used your own script to create the topology, so it is possible that something went wrong there. I haven't had problems with shooting_star_smart wrapper. The difference between Shooting Star and the Dijkstra/A-Star is, that it takes road links as start and end, not nodes.

                      • Message #1405

                        Hey Daniel,

                        yes it's confusing here. But to sort things a bit: The problem seems to occur with Christofs shooting*. I'm getting correct results but with an old unwrapped version of shooting*. Christof uses the standard osm2pgrouting, I don't. But the latter doesn't seem to be the reason. It was only a first assumption.

                      • Message #1406

                        Huh, very long thread here! It's a bit hard to pick the right posts now, but just two comments: * The latest version of shooting_star_smart SQL wrapper might work better. There were some bugs in previous version, which might have been similar to yours. It can become quite tricky to always select the right substring, since you initially don't know where you will go. * At least in trunk version you should be able to sort by "id" attribute to get the right order ... I think it was called "id"

                        If you should have any influence on this, please don't call such a parameter "id". What about "pos" or "sorter"

                        As you said you used your own script to create the topology, so it is possible that something went wrong there. I haven't had problems with shooting_star_smart wrapper. The difference between Shooting Star and the Dijkstra/A-Star is, that it takes road links as start and end, not nodes.

                        • Message #1407

                          If you should have any influence on this, please don't call such a parameter "id". What about "pos" or "sorter"

                          Good point! I will nag Anton ;-)

                          • Message #1410

                            Hi everyone,

                            thanks for your ideas!

                            What I tried was leaving the wrapper alone and just executing the following:

                            SELECT *
                            FROM shortest_path_shooting_star(
                               'SELECT gid as id, source, target, length as cost, x1, y1, x2, y2, null as rule, null as to_cost FROM m_ways_car', '7103' , '183051' , 'false', 'false' ), m_ways_car
                             where edge_id = gid
                            

                            however, without more luck. Even though I updated to the latest trunk version.

                            @daniel: where can I find shooting_star_smart? http://pgrouting.postlbs.org/svn/pgrouting/trunk/core/sql/routing_core_wrappers.sql does not include it.

                            I don't really know what else to change. I could try to post a relevant pg_dump. It would be great if one of you could look into that then?

                            Kind regards, Christof

                            • Message #1411

                              Try this one: http://pgrouting.postlbs.org/svn/pgrouting/sandbox/wrappers/routing_core_smart.sql

                              It's just a pl/pgpsql script, so not officially in pgRouting, but we used it for splitting the substrings at the right side.

                              If you use the script you also need to run the

                              SELECT add_network_info(<table>);
                              

                              function once to retrieve some network statistics.

                              • Message #1421

                                Try this one: http://pgrouting.postlbs.org/svn/pgrouting/sandbox/wrappers/routing_core_smart.sql It's just a pl/pgpsql script, so not officially in pgRouting, but we used it for splitting the substrings at the right side.

                                I played around a bit little with this. And I must admit the idea is interesting!

                                I feel it chooses that road first that leads in the direction of the destination. However, that does not always work - as you may see from this screen shot.  http://www.mobilino.de/shootingstar_sp_smart.png
                                (Made using the Data I posted below)

                                Consequently my impression is that -at least form this angle- shootingstar_sp_smart is somewhat of a workaround for the problem that shooting* is not choosing the best direction/way to begin the route itself. It would be just perfect if one could tell shooting* that a U-Turn before the first edge is totally ok :-)

                                Regards, Christof

                                • Message #1423

                                  Thanks for looking into it! Yes, if you see some places for improvements or some cases, when it wouldn't work as expected, we would appreciate to hear about.

                                  We first always tried to solve this problem within applications, but got tired of it, so Anton wrote that wrapper and it has worked so far. But maybe the usage wasn't too much sophisticated so far. This demo uses the "smart" wrapper funtion:  http://wrs.postlbs.org/foss4g/ (It has been down often recently, but seems to work at the moment). I haven't seen a problem there yet, but I must admit that it's simple OSM data without U-turns, etc.

                                  Btw, if this thread is going to become a bit long, we might want to change to the mailing list. The forum is only checked by a few people, who give answers, the mailing list delivers your question right into everyones mailbox ;-)

                                  pgRouting is currently in progress of creating some project steering committee to get various things done better. It would be nice to have some more documentation and user reciepies about what we talk here, I think. So I'm very glad about this kind of discussion. Thanks a lot for that!

                                  • Message #1429

                                    Hi Daniel,

                                    thanks! :-)

                                    That demo you posted does actually work... Strange that this problem doesn't occur there.

                                    I feel that for the moment we need to get our application up and running (using a* as an alternative) but in less then a few month I'll be back on the mailing list in order to seek for a working version of shooting* :-)

                            • Message #1413

                              Upload your dump and I'll have a look.

                              • Message #1416

                                Hi,

                                I uploaded the table def here:  http://www.mobilino.de/create.sql
                                and the data there:  http://www.mobilino.de/db_m_ways_demo.sql.gzip
                                (import it using "gunzip -c db_m_ways_demo.sql.gzip | psql gis")
                                thanks in advance, Carsten!

                                @Daniel: thanks for the link!
                                I imported the script and made my first request using shootingstar_sp_smart. From the first glance it looks like it also heads off in the not optimal direction but I need to test that a bit more.

                                • Message #1418

                                  Yes, as I have expected ... your

                                  SELECT * FROM shortest_path_shooting_star(
                                  SELECT gid as id, source, target, length as cost,
                                  x1, y1, x2, y2, null as rule, null as to_cost
                                  FROM m_ways_car', '7103' , '183051' , 'false', 'false' ),
                                  m_ways_car where edge_id = gid
                                  

                                  (see above) ... does not work correctly because this kind of SQL doesn't maintain the order.

                                  So I removed the join:

                                  SELECT * FROM shortest_path_shooting_star(
                                  'SELECT gid as id, source, target, length as cost, x1, y1, x2, y2,
                                  reverse_cost, null as rule, null as to_cost FROM m_ways_demo',
                                  7103 , 183051 , false, true);
                                  

                                  (with reverse_cost)

                                  and everything is fine!

                                  If I use "true, true" a directed graph is needed. But your data doesn't seem to be directed. Try this SQL. I expected at least two rows. (including Gid7103) But the result is empty.

                                  SELECT t1.gid, t2.gid, t1.x1, t1.y1, t2.x2, t2.y2
                                  FROM m_ways_demo AS t1, m_ways_demo AS t2
                                  WHERE t1.name = 'Am Botterbarg'
                                  AND t1.x1 = t2.x2 AND t1.y1 = t2.y2
                                  AND t1.x2 = t2.x1 AND t1.y2 = t2.y1;
                                  

                                  Regards,

                                  Carsten

                                  • Message #1419

                                    Another idea:

                                    If I remember the docu correctly they say in case of more than one restriction you'll have to provide your rows with same GIDs. This of course conflicts with your primary key on this attribute. I don't really know what osm2pgrouting expects (as I mentioned before, I'm using my own converter) but if they are using same GIDs for each direction for one way this may be the reason. Have you seen any import conflicts while pumping up your DB?

                                    Regards,

                                    Carsten

                                    • Message #1420

                                      Hi!

                                      thanks for importing my data!

                                      Your last sql confirms that every road is only once in my database. However, I just realized that I didn't know how one-way roads are marked. I found the solution in the route given in my first post: there is a one-way street (Sülldorfer Landstraße). In the corresponding link to the data in my second post one can note the exceptionally high "reverse cost". Obviously this is what hinders pgrouting to enter the street in the wrong direction (if has-reverse-cost = true is set)

                                      | and everything is fine!

                                      Executing your sql still gives me 24 result lines; where line 1 and 8 of the result are equal. I understand that you got less - say 17 lines?
                                      That would mean that something is wrong with either my database itself or with my version of pgrouting?!

                                      One difference I noticed between our databases is that - in contrast to your database - mine does not change the order in the join statement. But that can't be the reason for my problem, can it?

                                      Concerning the GIDs: they are unique and I didn't encounter any problems during import. And as everything except the direction shooting* is heading off works fine I don't feel that the problem should be solved by doubling every way. I still hope there is a better solution. :-)

                                      Regards,

                                      Christof

                                      • Message #1422

                                        Hi! thanks for importing my data! Your last sql confirms that every road is only once in my database. However, I just realized that I didn't know how one-way roads are marked. I found the solution in the route given in my first post: there is a one-way street (Sülldorfer Landstraße). In the corresponding link to the data in my second post one can note the exceptionally high "reverse cost". Obviously this is what hinders pgrouting to enter the street in the wrong direction (if has-reverse-cost = true is set)

                                        correct! a very high reverse_cost marks the street as one-way. but don't forget to set the second parameter to "true"

                                        | and everything is fine! Executing your sql still gives me 24 result lines; where line 1 and 8 of the result are equal. I understand that you got less - say 17 lines?

                                        round about 20. I checked the data with QGis. No double entries. Everything looked great.

                                        That would mean that something is wrong with either my database itself or with my version of pgrouting?!

                                        puhhh! casino?

                                        One difference I noticed between our databases is that - in contrast to your database - mine does not change the order in the join statement. But that can't be the reason for my problem, can it?

                                        I don't think so. Usually the order of joins is not predictable. It depends on what the query planner plans. Maybe yours gave you another plan.

                                        Concerning the GIDs: they are unique and I didn't encounter any problems during import. And as everything except the direction shooting* is heading off works fine I don't feel that the problem should be solved by doubling every way. I still hope there is a better solution. :-)

                                        Look at this docu. It comes from http://pgrouting.postlbs.org/wiki/ShootingStar

                                         gid | source | target | cost | x1 | y1 | x2 | y2 | to_cost | rule
                                        -----+--------+--------+------+----+----+----+----+---------+------
                                          11 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 4
                                          11 |      3 |     10 |    2 |  4 |  3 |  4 |  5 |    1000 | 12
                                        

                                        Regards, Christof

                                        • Message #1430

                                          Hej,

                                          round about 20. I checked the data with QGis. No double entries. Everything looked great.

                                          That means that something is wrong with my installation. Currently I don't really have a clue how to fix that but I'll try. However, there are some release dates to reach, consequently I have to use a* for the moment. However, I'll be back. :-)

                                          Thanks again for your help!!

                                          Regards, Christof

          • Message #1397

            Hi Pimapper,

            not directly, I live more central, next to the city park. May I ask for the reason of your question?

  • Message #1427

    I was doing some testing in my map and found similar behavior. I check using a small data set found here.

     http://cartosig.upv.es/es/recursos-sig/pgrouting-shooting-star-usage-example-turn-restriction

    There is the sql script to create a small road. Also an image showing the route in the pdf.

    The problem is when you make a route from link 7 to 12 the route go back to the round about before go back to the correct route

    SELECT * from shortest_path_shooting_star('SELECT gid as id, source::int4,target::int4,

    cost::double precision as cost, reverse_cost::double precision as reverse_cost, x1, y1, x2, y2 , rule, to_cost

    FROM wr',7,12, true, true);

    So is this the same case and i need to use the smart algorithm or im missing something else.

    • Message #1434

      I've come across similar anomalies using shortest_path_shooting_star. In testing I'm seeing numerous reverse direction routings over one way roads when using osm data for a major city.

      In general it appears that reverse_cost is not being considered for the bulk of these cases, and not just the start/end edges.

      To confirm this behavior with a smaller data set, I tried the davidgis test/demo data suggested by Juan [  http://cartosig.upv.es/es/recursos-sig/pgrouting-shooting-star-usage-example-turn-restriction ]. Here is the sql used and result:

      SELECT * FROM shortest_path_shooting_star('SELECT gid as id, source, target, cost, x1, y1, x2, y2, reverse_cost, rule, to_cost FROM wr', 20, 8 , true, true);

      vertex_id;edge_id;cost

      15;20;48.3246366252935 16;18;38.0005743220152 13;17;39.2224758594282 14;15;39.4286821133412 11;16;29.9822270236865 12;13;38.6094358307609 10;12;25.9044654619518 8;11;60 2;9;40 1;7;53.8753258085636 4;6;12.8311604873812 29;5;10.6864968606796 27;4;14.2572101668807 6;8;62.5380849791951

      In the davidgis demo, the correct transition should be from edge 20 to edge 19 (not edge 18 as above), and so on.

      My platform is Win XP, Postgres 8.4, Postgis 1.4, pgRouting-1.03_pg-8.4.2 binaries.

      • Message #1435

        Hi, my test for route 20-8 use edge 19. Same as the pdf document include it on the sample page.

        I'm going to move my post to a new topic, because i think this sample can help new users get started on the shooting* function. Also as Daniel mention, is hard to read a topic so long.

        My platform is: Windows Server 2003, PostgreSQL 8.3, Postgis 1.4, pgRouting-1.03_pg-8.3.7

        • Message #1436

          I agree - I'll move this to a new thread.