Ramp Junctions

agalbachicar commented 3 years ago

Attached is an xodr and yaml file.

Here is an algorithm to detect a ramp-like Junction

bool IsRampJunction(const ::maliput::api::Junction* junction) {
  const int num_segments = junction->num_segments();
  if (num_segments <= 1) {
    return false;
  }
  std::set<const ::maliput::api::Segment*> entry_segments;
  std::set<const ::maliput::api::Segment*> exit_segments;
  std::set<const ::maliput::api::Segment*> junction_segments;
  for (int i = 0; i < num_segments; ++i) {
    junction_segments.insert(junction->segment(i));
  }
  for (int i = 0; i < num_segments; i++) {
    const auto* segment = junction->segment(i);
    const int num_lanes = segment->num_lanes();
    for (int j = 0; j < num_lanes; j++) {
      const auto* lane = segment->lane(j);
      BOOST_ASSERT(lane);
      // Update entry_segments and exit_segments.
      for (const auto lane_end_type :
           {::maliput::api::LaneEnd::Which::kStart, ::maliput::api::LaneEnd::Which::kFinish}) {
        const ::maliput::api::LaneEnd lane_end(lane, lane_end_type);
        const auto* branch_point = lane->GetBranchPoint(lane_end.end);
        const auto* connected_lane_ends = branch_point->GetOngoingBranches(lane_end);
        for (int i_connection = 0; i_connection < connected_lane_ends->size(); i_connection++) {
          const auto& connected_lane_end = connected_lane_ends->get(i_connection);
          if (junction_segments.find(connected_lane_end.lane->segment()) == junction_segments.end()) {
            if (lane_end_type == ::maliput::api::LaneEnd::Which::kStart) {
              entry_segments.insert(connected_lane_end.lane->segment());
            } else {
              exit_segments.insert(connected_lane_end.lane->segment());
            }
          }
        }
      }
    }
  }
  const int n_connected_segments = entry_segments.size() + exit_segments.size();
  return (n_connected_segments > 2 && (entry_segments.size() == 1 || exit_segments.size() == 1));
}

ramp_junctions.zip

We should:

[ ] Check the behavior of our builder against this map.
[ ] Understand why we are missing to integrate all necessary Segments into the Junction. Is it a bug / limitation in our building process, in the xodr parser or the way that OpenDRIVE specification describes scenarios like this?
[ ] Propose and discuss a solution.
[ ] Implement it!

francocipollone commented 3 years ago

Some Updates

I was able to upload the map (strict build and building non-drivable lanes.)
These are the ramp junctions in the map.
- I've applied the algorithm(shared in the issue description) to verify if the junctions are ramp junctions and the results were ok. Only the junctions 66, 55, 45, 25, 74 and 36 were considered ramp junctions.
- I've printed the information of this 6 junctions performing queries to the api::RoadGeometry: junctions_to_string.zip
- WIP: The information gotten from the built RoadGeometry seems to be consistent with the junctions described in the xodr. I will check the xodr a bit deeper to see if we have missing segments after building it.

agalbachicar commented 3 years ago

Looking at the XODR, Junction 36 holds Road 43 and 37 and they seemed to be properly parsed and built in the RoadGeometry:

  junction: 36
    segment: 37_0
      lane: 37_0_-4
        length: 44.09
        geo positions:
          s_min: (x = -195.345, y = -284.415, z = -6.10352e-05)
          s_max: (x = -195.345, y = -240.375, z = -6.10352e-05)
        to left: 37_0_-3
        to right: 
      lane: 37_0_-3
        length: 44.09
        geo positions:
          s_min: (x = -198.25, y = -284.415, z = -6.10352e-05)
          s_max: (x = -198.25, y = -240.375, z = -6.10352e-05)
        to left: 37_0_-2
        to right: 37_0_-4
      lane: 37_0_-2
        length: 44.09
        geo positions:
          s_min: (x = -201.75, y = -284.415, z = -6.10352e-05)
          s_max: (x = -201.75, y = -240.375, z = -6.10352e-05)
        to left: 37_0_-1
        to right: 37_0_-3
      lane: 37_0_-1
        length: 44.09
        geo positions:
          s_min: (x = -204.471, y = -284.415, z = -6.10352e-05)
          s_max: (x = -204.471, y = -240.375, z = -6.10352e-05)
        to left: 
        to right: 37_0_-2
    segment: 43_0
      lane: 43_0_-1
        length: 45.0012
        geo positions:
          s_min: (x = -198.25, y = -284.415, z = -6.10352e-05)
          s_max: (x = -187.219, y = -241.358, z = 0)
        to left: 
        to right:

@andrewbest-tri @vladimir-tri @liangfok what are we missing here? I'm sorry but I'm not able to see the problem. Shall we look into some other Junction?

vladimir-wp commented 3 years ago

@agalbachicar Question - is list of detected ramp junctions identical to the list produced by loading XODR using old Malidrive version? If yes - I think, new malidrive works correctly?

liangfok commented 3 years ago

The problem was with the following code:

(entry_segments.size() == 1 || exit_segments.size() == 1)

When non-drivable lanes are included in the road network, entry_segments and exit_segments would each contain more than one segment.

vladimir-wp commented 3 years ago

Yes, as we discussed a few days ago - we would prefer to get a flag for loader to ignore non-drivable lanes (the only exception should be bike lanes which should have special1 type in XODR, if I remember correctly ).

Anyway, IsRampJunction() logic would better not to be changed and produce same list of ramp junctions for this testcase (well, for all testcases, actually), as produced by old Malidrive. This is a goal.

liangfok commented 3 years ago

The flag for the loader to ignore non-drivable lanes was just merged (37aed0fb1ee9c19bd5ef87dd5e82be534e441c25). My initial testing downstream indicates that it did indeed resolve the problem.

francocipollone commented 3 years ago

I've applied the algorithm(shared in the issue description) to verify if the junctions are ramp junctions and the results were ok. Only the junctions 66, 55, 45, 25, 74 and 36 were considered ramp junctions.

Just adding more info to this: I've built the RoadGeometry building also non-drivable lanes (omit_nondrivable_lanes = false) and tried the algorithm and this was the result:

[INFO] junction id: 74 . IsRampJunction?: true
[INFO] junction id: 66 . IsRampJunction?: true
[INFO] junction id: 45 . IsRampJunction?: true
[INFO] junction id: 36 . IsRampJunction?: true
[INFO] junction id: 55 . IsRampJunction?: true
[INFO] junction id: 25 . IsRampJunction?: true
[INFO] junction id: 14_0 . IsRampJunction?: false
[INFO] junction id: 13_0 . IsRampJunction?: false
[INFO] junction id: 10_0 . IsRampJunction?: false
[INFO] junction id: 7_0 . IsRampJunction?: false
[INFO] junction id: 19_0 . IsRampJunction?: false
[INFO] junction id: 15_0 . IsRampJunction?: false
[INFO] junction id: 2_0 . IsRampJunction?: false
[INFO] junction id: 23_0 . IsRampJunction?: false
[INFO] junction id: 9_0 . IsRampJunction?: false
[INFO] junction id: 12_0 . IsRampJunction?: false
[INFO] junction id: 3_0 . IsRampJunction?: false
[INFO] junction id: 11_0 . IsRampJunction?: false
[INFO] junction id: 4_0 . IsRampJunction?: false
[INFO] junction id: 17_0 . IsRampJunction?: false
[INFO] junction id: 18_0 . IsRampJunction?: false
[INFO] junction id: 22_0 . IsRampJunction?: false
[INFO] junction id: 20_0 . IsRampJunction?: false
[INFO] junction id: 21_0 . IsRampJunction?: false
[INFO] junction id: 1_0 . IsRampJunction?: false
[INFO] junction id: 6_0 . IsRampJunction?: false
[INFO] junction id: 8_0 . IsRampJunction?: false
[INFO] junction id: 24_0 . IsRampJunction?: false
[INFO] junction id: 16_0 . IsRampJunction?: false
[INFO] junction id: 5_0 . IsRampJunction?: false
[INFO] junction id: 0_0 . IsRampJunction?: false

So respect to this:

The problem was with the following code: (entry_segments.size() == 1 || exit_segments.size() == 1)

At least for this xodr, it seemed to work correctly.

liangfok commented 3 years ago

Alright, the map that I had a problem with previously was cloverleaf.xodr.

francocipollone commented 3 years ago

Alright, the map that I had a problem with previously was cloverleaf.xodr.

Great, thanks for clarifying, I will take a look to see if this is causing odd behavior when building the junctions

francocipollone commented 3 years ago

cloverleaf.zip -- Shared on slack I've tried cloverleaf. There are many things that are worth it to comment about it.

Before jumping straight to the ramp junctions analysis I would like to take the chance to mention a difference between both backends because of omitting the non-drivable lanes building.

Cloverleaf

To note: Both highways have non-drivable lanes in the center of them.

General comparisons between backends

maliput_malidrive backend

1 - Building non-drivable lanes.

The new backend implementation parses the non-drivable lanes and are correctly built. ( The non-drivable lanes have the same mesh material than the drivable ones, making a differentiation in the mesh material would improve a lot the visualization)

cloverleaf_malidrive2_all_lanes

2 - Omitting non-drivable lanes building.

Given that there are some non-drivable lanes that are described in the inner part of the Road, when the omit_nondrivable_lane flag is set those non-built lanes cause a difference in the lane offset with respect to the fully built RoadNetwork. That's why in this case in fact there are some ramp roads that don't visually connect to the highway.

cloverleaf_malidrive2_omit_nondrivable_lane

OpenDriveSdk-based backend:

The old backend implementation(opendrivesdk based) skips the building of non-drivable lanes. In the visualizer it can be seen: The location where the non-drivable lane should appear is simply empty.

cloverleaf_malidrive1 For road 183, lanes from 4 to -1 are non-drivable lanes, and then they aren't shown.

These are the ramp junctions in the map: 18 48 106 77 135 163

cloverleaf_malidrive2_ramps

Note: As can be seen in the picture, Junctions 106 and 163 contain two ramps.

Analyzing junctions

Configuration used:

maliput_malidrive backend
linear_tolerance: 0.15
omit_nondrivable_lanes: true

Applying the aforementioned algorithm to detect the ramp junctions gives as result:

Junction Id	Is Ramp Junction?	Reason
18	True
77	True
135	True
106	False	Has 2 ramps
163	False	Has 2 ramps
48	False	Bug in algorithm See comment

TODO: Analyze the case of junction 48 to see why isn't considered a ramp junction.

agalbachicar commented 3 years ago

Thanks a lot for the report @francocipollone !

francocipollone commented 3 years ago

Analyzing junctions

Junction 48

Cloverleaf-Junction 18

When running the IsRampJunction algorithm it fails because the number of entry segments(2) and exit segments(2) are equal and they are 4 in total. So the last condition isn't met.

  const int n_connected_segments = entry_segments.size() + exit_segments.size();
  return (n_connected_segments > 2 && (entry_segments.size() == 1 || exit_segments.size() == 1));

If we check which segments are considered entry and exit we see:

[INFO] |___  Number of entry_segments: 2
[INFO]  |___  entry_segment: 0_0
[INFO]  |___  entry_segment: 7_0
[INFO] |___  Number of exit_segments: 2
[INFO]  |___  exit_segment: 7_0
[INFO]  |___  exit_segment: 8_0

7_0 segment is acting like entry and exit segment at the same time. It isn't the desired behavior.

The method/algorithm IsRampJunction makes an implicit assumption that is that the road that acts as a ramp has the same travel direction as the ones that belongs to the highway. And in this case. Road 68 has one direction and the Road 49 has the opposite direction.

It causes that the exit segment obtained from analyzing road 49 is segment 7_0 and the entry segment of road 68 is also segment 7_0. So the algorithm has a limitation here.

In order to talk about entry segments and exit segments, probably the algorithm should take into account the rule information about the real travel direction (DirectionUsageRule) that is expected to have on the roads.

francocipollone commented 3 years ago

@liangfok I finished analyzing Cloverleaf. Hope it is helpful!

liangfok commented 3 years ago

Thank you for the fantastic analysis. I filed an internal TRI ticket to track the work of updating IsRampJunction() to use DirectionUsageRules.

vladimir-wp commented 3 years ago

@francocipollone Thanks a lot, indeed, IsRampJunction assumes the same direction for all segments related to the junction. Let me fix this.

The only question I have - how did it work with old Malidrive? I mean, did it invert segment direction for this problematic "Road 49" segment?

francocipollone commented 3 years ago

@francocipollone Thanks a lot, indeed, IsRampJunction assumes the same direction for all segments related to the junction. Let me fix this.

The only question I have - how did it work with old Malidrive? I mean, did it invert segment direction for this problematic "Road 49" segment?

I've just run it with the old malidrive and the result I got is exactly the same.

Are we using a different cloverleaf.xodr file?

The one I used to run the analysis was shared with us on Slack on May21st (Check here). It is also shared at the top of the report.

I used that because I supposed it was the one that you were using.

vladimir-wp commented 3 years ago

@francocipollone Thanks a lot, indeed, IsRampJunction assumes the same direction for all segments related to the junction. Let me fix this. The only question I have - how did it work with old Malidrive? I mean, did it invert segment direction for this problematic "Road 49" segment?

I've just run it with the old malidrive and the result I got is exactly the same.

Are we using a different cloverleaf.xodr file?

The one I used to run the analysis was shared with us on Slack on May21st (Check here). It is also shared at the top of the report.

I used that because I supposed it was the one that you were using.

Got it, thank you very much for very detailed analysis. I am working on the fix for IsRampJunction logic.

vladimir-wp commented 3 years ago

Are we using a different cloverleaf.xodr file? No, it looks like nobody noticed this problem for cloverleaf testcase so far.

vladimir-wp commented 3 years ago

@francocipollone I have implemented support for segment direction, but Junction 18 is still detected as "non ramp". I am currently using old malidrive ( which is using odrManager ). The issue is - there is one more segment (67) in junction 18 which is breaking everything and it is not clear where it comes from, I cannot see it in odrViewer (or it is colored as green ) and on your screenshot it is also not there. Do you have any idea what is this segment? Maybe, I need to switch to Malidrive 2.0 to get rid of it while loading road network?

vladimir-wp commented 3 years ago

Just cherry-picked @liangfok 's PR to switch to Malidrive 2.0, still getting problem with this "Road 67" segment.

vladimir-wp commented 3 years ago

Oh, it looks like Road 67 actually corresponds to opposite side of the road, so, if it is there in the junction, it is correct to say that this junction cannot be qualified as a ramp junction?

francocipollone commented 3 years ago

I have implemented support for segment direction, but Junction 18 is still detected as "non ramp".

I had no issues with Junction 18 when doing this analysis, it was Junction 48 the "problematic" one. (for both backends) Assuming that Junction 18 is the one you are referring to and given that I had no issue with that junction before (IsRampJunction returns true) probably I would like to double-check that we are using the same cloverleaf map.

Before upgrading the IsRampJunction algorithm did you have troubles with Junction 18? And what about Junction 48? Just to see that we both got the same results.

The issue is - there is one more segment (67) in junction 18 which is breaking everything and it is not clear where it comes from,

Just to clarify nomenclature, I guess that you refer to Road 67 that technically is part of Junction 18 right? Oh I see I guess that you are talking about the Junction 48 because Road 67 is part of junction 48.

Oh, it looks like Road 67 actually corresponds to opposite side of the road, so, if it is there in the junction, it is correct to say that this junction cannot be qualified as a ramp junction?

That's right, Road 67 is part of junction 48 but corresponds to the opposite side of the road.

if it is there in the junction, it is correct to say that this junction cannot be qualified as a ramp junction?

I understand that Road67 could be problematic now to the new algorithm because let's say that its DirectionUsageRule is AgainstS however I don't know what are the requirements you have to label a junction as a ramp junction.

vladimir-wp commented 3 years ago

Oh, sorry, I was talking about Junction 48, not 18. Yes, ramp junction must include 2 parts - straight road (segment) and fork/merge segments. No opposite segment must be in the road (unless we would like to change the criteria in the future). So, our final analysis results are correct and that means there are no ramp junctions in cloverleaf.xodr.

francocipollone commented 3 years ago

@vladimir-tri @liangfok Feel free to close the issue if it is considered solved.

liangfok commented 3 years ago

Will close for now and re-open if I later find it to be problematic.

maliput / maliput_malidrive

Ramp Junctions #83

Cloverleaf

General comparisons between backends

maliput_malidrive backend

OpenDriveSdk-based backend:

Ramp junctions

Analyzing junctions

Analyzing junctions

Junction 48