[Routing] Initial public API proposal.

[agalbachicar]

🎉 Initial public API proposal for routing

Part of #543

Summary

Provides the main API proposal which is expected to remain immutable or easier to extend with minimal impact.
This PR aims to:

• Validate the API is expressive enough and can be extended to satisfy the use cases we try to implement.
• Provide later on a set of base functionality for the different implementations.

Please take a look at this gist for a basic initial consumption of this API. I need to expand on how the agents should consume the route once computed. There I would require more input from the reviewers.

Test it

Via gtest.

• To be implemented.

Checklist

• Signed all commits for DCO
• Added tests
• Added example and/or tutorial
• Updated documentation (as needed)
• Updated migration guide (as needed)
• Consider updating Python bindings (if it affects the public API)

Note to maintainers: Remember to use Squash-Merge and edit the commit message to match the pull request summary while retaining Signed-off-by messages.

---

This change is 

[francocipollone]

It looks good! I left a couple of comments and discussions

[francocipollone]

I wonder if this makes sense. The rule api is rather extensive. Rules, Rule states, Rule state currently applying. Rule Types. How do you decide up to which point cover the api?

Having the LaneSRange should be sufficient to go directly to the Rule API that maliput provides and query what the agent needs.

[agalbachicar]

Before making any change to the code, I'd like to iterate a bit over this.
I think it's a fair point. Having proxies to other queries is complicated to maintain and leaves things out of the table. On the other side, it allows agent behavior to quickly accessing the data it requires to navigate.

I am not a big fan of these methods, but I definitely see the positive flip side.

[agalbachicar]

@liangfok @stonier wdyt?

[liangfok]

I lean towards not providing this method for the reasons mentioned above. It'll be better to keep a method like this within the general rules API. The router should internally consider rules when determining a route, e.g., do not route going down the wrong direction of a one-way lane, but should not be responsible for enabling agents to query rule information.

[stonier]

I tend to agree. If there's other ways to get the rules, then it makes this redundant ... unless there is e.g. caching / fast lookup considerations?

[francocipollone]

It could be easier to consume yeah.

I am also thinking, what about atomizing the route even more. Within RoutePhase we have LaneSRanges.
What about creating an abstaction to represent a LaneSRange in a RoutePhase. In a way that we can (similarly to what we have with Segment and Lanes) provide to_left and to_right methods for moving around the adjacent LaneSRanges in the RoutePhase. From an agent's point of view could be useful.

[agalbachicar]

That could be a Path type, something like:

class Path {
 public:
  const maliput::api::LaneSRange& lane_s_range() const;
  std::optional<Path> to_left_path() const;
  std::optional<Path> to_right_path() const;
  std::optional<Path> preceding_path() const;
  std::optional<Path> succeeding_path() const;
};

The only thing that I see with this type is that we are duplicating the functionality of the Lane type without being able to capture multiple preceding and succeeding Lanes. If we decided to not offer a proxy for rules, then I would like to follow the same spirit.

[agalbachicar]

Please take a look to the proposed solution. It is not in line with my previous comment but I think it offers a simplified version and probably more scalable than the one I proposed.
As a next step, we can provide a std::vector<maliput::api::LaneSRange> FindLaneSRanges(const maliput::api::LaneSRange lane_s_range, LaneSRangeRelation relation) const;. That should offer the two way identification of relation between LaneSRanges (for a pair of ranges, and give a range and the relation find those that match the requirement). WDYT?

[francocipollone]

Is it expected to also provide constraints for the rules or only geometric constraints?

[agalbachicar]

I am not so sure about it. I would prefer to constraint that when building the Router.

[liangfok]

First pass at route.h. Sorry haven't had time to review the other files yet. Will get to them ASAP.

[liangfok]

I assume "falls into" means there must be an exact match. That is, inertial_position must be within the returned RoutePhase and not "close enough" in a manner similar to RoadGeometry::ToRoadPosition(). I wonder whether it would be useful to support semantics akin to RoadGeometry::ToRoadPosition() where users can provide a tolerance and a returned RoutePhase may not actually include inertial_position but is within tolerance of it. Thoughts?

[agalbachicar]

I think it makes sense to be consistent and use the same criteria as in RoadGeometry::ToRoadPosition(). However, I also think it is not the intended use because while querying the Route, being able to distinguish if a coordinate falls into or not the Route allows the agent behavior to trigger a new plan or to fail (when there is no recovery path).

If we decided to answer a RoutePhase that minimizes the distance to the inertial_position we would be able to query any coordinate, and still map a RoutePhase. Would it be useful for the agent behavior?

[liangfok]

Here's a situation where this might be useful: Suppose an agent is an off-road-capable vehicle like a Toyota TRD 4Runner. On occasion, it might adventure off-road but later wish to get back to a well-traveled on-road path. In such an application, it might wish to get the closest RoutePhase even if doesn't overlap with the agent's current position. In general, there are many reasons why an agent's inertial position may end up off road, and allowing for them to still query for a route seems potentially useful.

[francocipollone]

As example. Despite the differences of the use, Google maps behave similarly to @liangfok proposal and it may be useful to be that way. It makes me think that information on distances to the start of the route should be provided as well when querying the route as well.

[andrewbest-tri]

I agree that we need to provide the closest route position in this case. Taking a simpler example of a controller we're trying to train, the car will fall off the pavement here and there so we want a notion of when to get back it. Furthermore the decision to re-route may be made by an agent based on the distance from a point on the route. "I am far enough away, better re-route"

[agalbachicar]

Alright! I'll work on the changes.

[agalbachicar]

PTAL to the new types and semantics introduced.

[liangfok]

I see that an alias to this pointer is maintained as a member variable. Thus, should document the lifetime requirements of this parameter. Something like: "The lifetime of this pointer must exceed that of this object."

[agalbachicar]

Done.

[liangfok]

No change?

[agalbachicar]

I think it is solved now.

[liangfok]

Typo: coordinage

[agalbachicar]

Done.

[liangfok]

Can delete "the RoutePhase".

[agalbachicar]

Done.

[liangfok]

Here's a situation where this might be useful: Suppose an agent is an off-road-capable vehicle like a Toyota TRD 4Runner. On occasion, it might adventure off-road but later wish to get back to a well-traveled on-road path. In such an application, it might wish to get the closest RoutePhase even if doesn't overlap with the agent's current position. In general, there are many reasons why an agent's inertial position may end up off road, and allowing for them to still query for a route seems potentially useful.

[andrewbest-tri]

I agree that we need to provide the closest route position in this case. Taking a simpler example of a controller we're trying to train, the car will fall off the pavement here and there so we want a notion of when to get back it. Furthermore the decision to re-route may be made by an agent based on the distance from a point on the route. "I am far enough away, better re-route"

[andrewbest-tri]

I see an omission in the API that @stonier and I struggled with in the past. The RoutePhase does not reflect which lanes the vehicle MUST occupy to meet the next transition and whether that lane is the same as the entry lane. Take, for example, a 4-lane highway where the road splits at a junction. I've attached a VERY crude drawing. If an agent enters from the south-west and wants to travel north (taking the "left" split assuming the highway goes left to right) either lane is acceptable for the agent. Lane by lane routing will assign a lane to be preferred and the agent will dive towards the preferred lane (at least a dummy agent would). Similarly, all the lanes in the range would be listed as alternate paths, even though two of them imply a failure to route further because the agent will take the wrong fork if it is in either of the two bottom lanes. Maybe we don't care about this yet, but we may want some notion of which of the alternate LaneSRanges actually connect to the next junction on the route to give the agent better information on which lanes are actually okay.

Also, we allow lane changes, but how do we represent them semantically? This was a challenge as well. Lane-by-lane routing might choose to artificially sub-divide a RoutePhase s.t. each split sub-phase has the new target lane set as the primary LaneSRange. In this case, all agents along the route may choose to as-quickly-as-possible dive towards the new preferred lane. Not splitting, but specifying only the final lane may cause them to dive upon entering the highway.

There's no strict right answer, but we should probably augment the information at-least with which lanes will actually continue the route in each segment.

One more comment I have to make here since my wifi just died. We should keep a notion of progress along a RoutePhase so the agent can estimate how far they are from a decision point. For example, I may choose to take an alternate lane as long as I know i've got 1km to get back into this lane until my next step. That kind of sugar method will make route following easier.

[agalbachicar]

This is a good point. We discussed it and saw what other routing APIs offer. Here are some comments to your comment to share my research and initial study of the situation.

The RoutePhase does not reflect which lanes the vehicle MUST occupy to meet the next transition and whether that lane is the same as the entry lane.

This is good evidence that the API does not reflect my intention. I was not going to provide that as implementation. In my head, the Route will contain RoutePhases which would allow an agent to go from A to B. That imposes a constraint on the LaneSRanges that each RoutePhase can have. Let me present your example again:

The blue arrow represents the agent, the red square represents the target destination, each line is a Lane and each circle is a BranchPoint. The traffic flow is from West to East.

What I want to get as an answer in the Route is the following sequence of RoutePhases:

I also see how this could work too:

But in this case we are constraining the maneuver beyond what the agent can actually do and it may end up generating congestion later on. Still, I think it is a valid response.

The following constrains further the ability of the agent to arrive to the destiny. It reduces the freedom of the trajectory potentially introducing more congestion in the traffic flow.

I don't expect to have any of the following responses:

Also, we allow lane changes, but how do we represent them semantically? This was a challenge as well. Lane-by-lane routing might choose to artificially sub-divide a RoutePhase s.t. each split sub-phase has the new target lane set as the primary LaneSRange. In this case, all agents along the route may choose to as-quickly-as-possible dive towards the new preferred lane. Not splitting, but specifying only the final lane may cause them to dive upon entering the highway.

I think there is a bit of the answer here. I don't know a good semantic paradigm that does not constrain behavior development. This is part of the API decision actually. I think that by providing a specifc set of RoutePhases with LaneSRanges in them is also an API decision that constrains the behavior development. The agent needs to compute trajectories based on rules, traffic, kinematic and dynamic constraints, response of other agents, etc etc. I think a good choice is to provide the information and let the sophistication of the behavior implementation to decide what to consume.

There's no strict right answer, but we should probably augment the information at-least with which lanes will actually continue the route in each segment.

Are the above pictures enough to cover the cases that you found? Do you think the expected response is good enough? What about the others?

One more comment I have to make here since my wifi just died. We should keep a notion of progress along a RoutePhase so the agent can estimate how far they are from a decision point. For example, I may choose to take an alternate lane as long as I know i've got 1km to get back into this lane until my next step. That kind of sugar method will make route following easier.

Super interesting point. I wonder though if this should be part of the Route or be a different entity? Like a cursor or pointer that advances as the vehicle does.

Also, a preliminary question, what would it be or how would we define a decision point? I ask it because I am not sure the same definition yields for different vehicles or agents the same point in a Route or in a simulation with different sorrounding agents in the same Route.

Thanks for these comments @andrewbest-tri

[andrewbest-tri]

Just getting back (as I saw the ping). Yes your pictures above do answer some of my concerns, assuming that they are directed graphs. There is a piece not captured though, your graph implies that there are branch points within a straight contiguous segment of road. This is often not the case, especially in roads build in RoadRunner. You may have a long straight segment without artificial branch points in the middle in which an agent must change lanes to proceed. I can't draw right now, but simply imagine your much nicer graph without branch points in the middle of contiguous straight lanes to see my point.

[agalbachicar]

This is an interesting case that we verbally discussed with @stonier and @liangfok in a weekly.

I think that we can capture the breakdown of a physical road into pieces that reflect each RoutePhase if the Router has some kind of knowledge about the geometric, kinematic and dynamic constraints of the vehicle. That still could not be enough to deal with the traffic congestion situation or other state specific conditions in which the vehicle should be immersed in to determine which is the right range for lane switching and performing this maneuver.

Thinking of the API, I still think the proposal is valid. This set of classes and responsibilities can adapt to various levels of sophistication in the Router. As the Router becomes omniscient and omnipresent (i.e. knows the complete and exact state of all the agents in the road at any present and past time, and their capabilities and constraints) the Route definition can include the partitioning of a RoutePhase into multiple RoutePhases that provide a more accurate representation of what the vehicle needs or can do. Moving in the opposite direction works as well I think. A simple Router that only knows about connectivity should offer a simple Route description that makes sense considering the connectivity graph.

One aspect of the Route that I could not capture but I think it is not relevant at the moment is how the dynamics of the rules and traffic can make a Route no longer cost effective as it is traversed. For example, as a traffic jam becomes more and more dense, the cost of a specific route is bigger than an alternative and you may want to diverge. This is clearly solved by an agent behavior feature that polls the Router but you don't the asynchronous notification.

[stonier]

Excellent graphs, thanks @agalbachicar. They really help drive the discussion.

There is a piece not captured though, your graph implies that there are branch points within a straight contiguous segment of road.....but simply imagine your much nicer graph without branch points in the middle of contiguous straight lanes to see my point.

This is a good example. What is the expected response for this situation? If I were to draw graphs like you have above but without the middle branch points, I don't see how you can avoid a wrong response.

[stonier]

Just for reference, the final proposal (in code - see the comments at the top of route.h) handles the situation by capturing more or less of lanes, lane start and lane end position.

• If it's got a lane and lane start, but no lane end, then the agent knows it needs to be off the lane by lane end.

[liangfok]

Completed a pass at r5.

Reviewed 2 of 4 files at r3, 6 of 6 files at r5, all commit messages.
Reviewable status: all files reviewed, 45 unresolved discussions (waiting on @agalbachicar, @andrewbest-tri, @francocipollone, and @stonier)

---

include/maliput/routing/lane_s_range_relation.h line 50 at r5 (raw file):

/// In the diagram above:
/// - `x` indicates the beginning or the end of a maliput::api::LaneSRange.
/// - `>` indicates the direction of travel of the maliput::api::LaneSRange.

What is the relationship between the direction of travel and the lane's positive S direction? Does it depend on lane_s_range.s_range().WithS()? For example, if lane_s_range.s_range().WithS() is positive, the direction of travel is in the +S direction, whereas if lane_s_range.s_range().WithS() if false, the direction of travel is in the -S direction?

---

include/maliput/routing/lane_s_range_relation.h line 69 at r5 (raw file):

/// not found in the Route.
enum class LaneSRangeRelation {
  kAdjacentToTheLeft,

To reduce verbosity while maintaining clarity, I recommend removing "ToThe" from all these names.

---

include/maliput/routing/lane_s_range_relation.h line 72 at r5 (raw file):

  kAdjacentToTheRight,
  kToTheLeft,
  kToRightLeft,

These two are unique in that the two LaneSRanges are not in physical contact. I wonder whether they are necessary since they could be inferred via the transitive relationship of multiple kAdjacentToTheLeft/kAdjacentToTheRight relations.

---

include/maliput/routing/route.h line 44 at r3 (raw file):

/// Describes the sequence of paths to go from one RoadPosition to another.
/// It is sequenced by RoutePhases which contain default and adjacent

Can the RoutePhase abstraction be hidden as an internal implementation detail? Do agents really need to know that the route is broken into multiple phases? It might be easier for agents if they could treat a Route as a monolitic object and to directly obtain the relevant LaneSRanges based on where they currently are rather than needing to go through the RoutePhase intermediary.

RoutePhase and Route have very similar API, which indicates to me that perhaps RoutePhase need not be directly used by agents.

---

include/maliput/routing/route.h line 67 at r3 (raw file):

  /// @param route_phases The sequence of RoutePhases. It must not be empty.
  /// RoutePhases must be connected end to end.
  /// @param road_network The maliput::api::RoadNetwork pointer. It must not be

I am hesistant to include a RoadNetwork within a Route because I think Route should be a passive store of data. If there are certain operations that require a RoadNetwork, those operations could be implemented in a standalone manner that takes as input both a Route and a RoadNetwork. Are there reasons in which a Route must have a RoadNetwork?

---

include/maliput/routing/route.h line 83 at r3 (raw file):
Let's name this method "size()" since it could be considered an accessor and to be consistent with line 89 in r5.

Accessors and mutators (get and set functions) may be named like variables. These often correspond to actual member variables, but this is not required. For example, int count() and void set_count(int count).

https://google.github.io/styleguide/cppguide.html#Function_Names

---

include/maliput/routing/route.h line 93 at r3 (raw file):

  const RoutePhase& Get(int index) const { return route_phases_.at(index); }

  /// @return The start maliput::api::RoadPosition of this Route.

BTW, consider deleting "maliput::api::RoadPosition " since that is implicit based on the method's return value.

Ditto for docstring of EndRoadPosition below.

---

include/maliput/routing/route.h line 44 at r5 (raw file):

namespace routing {

/// Describes the sequence of paths to go from one RoadPosition to another.

"to go from" should be "that go from".

---

include/maliput/routing/route.h line 57 at r5 (raw file):

/// Route. The last RoutePhase end road position identifies the ending of the
/// Route. The sequence of RoutePhases form a continuous route where the end of
/// one RoutePhase exactly matches the begining of the next RoutePhase in the

"begining" should be "beginning".

---

include/maliput/routing/route.h line 75 at r5 (raw file):

  /// @p road_network.
  /// @throws maliput::common::assertion_error When @p road_network is nullptr.
  Route(const std::vector<RoutePhase>& route_phases, const maliput::api::RoadNetwork* road_network)

Should remove "maliput::" since this is already in the "maliput" namespace. Ditto below.

---

include/maliput/routing/route.h line 132 at r5 (raw file):

  /// Frame are evaluated there as well.
  ///
  /// @param road_position A road position expressed into the LANE-Frame

I recommend deleting "expressed into the LANE-Frame position" since there is no other way in which a RoadPosition can be expressed.

---

include/maliput/routing/route.h line 141 at r5 (raw file):

  }

  /// Finds the relationship between @p lane_s_range_a and @p lane_s_range_b.

Since ordering matters, we should specify which one is fixed and which one is relative. In this case, I assume 'a' is fixed and 'b' is relative, meaning this should be:

/// Finds the relation of @p lane_s_range_b with respect to @p lane_s_range_a.

---

include/maliput/routing/route_phase.h line 56 at r3 (raw file):

///
/// (To be discussed): we can attach the start and / or end road_positions to
/// the default_lane_s_range as a precondition.

Would specifying start/end road_positions be redundant to default_lane_s_range? That is, the beginning of the route is the beginning of default_lane_s_range and the end of the route is the end of default_lane_s_range.

---

include/maliput/routing/route_phase.h line 72 at r3 (raw file):

  /// Constructs a RoutePhase.
  ///
  /// @param index The index at the parent Route. It must be non-negative.

There shouldn't be a need for this. A RoutePhase object shouldn't need to know how many other RoutePhases exist before or after it.

---

include/maliput/routing/route_phase.h line 69 at r5 (raw file):

  ///
  /// @param index The index at the parent Route. It must be non-negative.
  /// @param start_road_position The start maliput::api::RoadPosition of this

I recommend renaming "start_road_position" to be "start" and "end_road_position" to be "end". It will be less verbose and should maintain clarity based on the data type.

---

include/maliput/routing/route_phase.h line 71 at r5 (raw file):

  /// @param start_road_position The start maliput::api::RoadPosition of this
  /// RoutePhase. `start_road_position.lane` must not be nullptr and it must be
  /// in either the @p default_lane_s_range or @p adjacent_lane_s_ranges.

What is the use case for having start_road_position be in an adjacent LaneSRange? Wouldn't it be more clear if it was always the start of the default_lane_s_range, in which case start_road_position wouldn't even be necessary?

Ditto for end_road_position. Couldn't be eliminate this parameter and enforce that the end of default_lane_s_range always be the end road position?

Another thought: What is the reason for having to define a start and end? Why not simply provide a set of adjacent LaneSRanges and allow the agent to decide for itself where the start and end are?

---

include/maliput/routing/route_phase.h line 75 at r5 (raw file):

  /// RoutePhase. `end_road_position.lane` must not be nullptr and it must be
  /// in either the @p default_lane_s_range or @p adjacent_lane_s_ranges.
  /// @param lane_s_range_tolerance Tolerance to compare maliput::api::LaneSRanges.

Should order the parameter descriptions the same as they are in the method signature. In this case, lane_s_range_tolerance is the 2nd parameter in the method's signature.

---

include/maliput/routing/route_phase.h line 77 at r5 (raw file):

  /// @param lane_s_range_tolerance Tolerance to compare maliput::api::LaneSRanges.
  /// It must be non-negative.
  /// @param default_lane_s_range The default maliput::api::LaneSRanges of this phase.

Instead of providing separate default_lane_s_range and adjacent_lane_s_range, consider providing a single const std::vector<maliput::api::LaneSRange>& lane_s_ranges parameter and an index into this vector specifying the default.

---

include/maliput/routing/route_phase.h line 78 at r5 (raw file):

  /// It must be non-negative.
  /// @param default_lane_s_range The default maliput::api::LaneSRanges of this phase.
  /// @param adjancent_lane_s_ranges List of adjacent maliput::api::LaneSRanges.

"adjancent" should be "adjacent".

---

include/maliput/routing/route_phase.h line 79 at r5 (raw file):

  /// @param default_lane_s_range The default maliput::api::LaneSRanges of this phase.
  /// @param adjancent_lane_s_ranges List of adjacent maliput::api::LaneSRanges.
  /// @param road_network The pointer to the maliput::api::RoadNetwork. It must

See other comment about not including a RoadNetwork inside a RoutePhase for separation-of-concerns purposes.

---

include/maliput/routing/route_phase.h line 86 at r5 (raw file):

  /// negative.
  /// @throws maliput::common::assertion_error When @p road_network is nullptr.
  RoutePhase(int index, double lane_s_range_tolerance, const maliput::api::RoadPosition& start_road_position,

Can omit "maliput::" since this is already in the "maliput" namespace.

---

include/maliput/routing/route_phase.h line 166 at r5 (raw file):

 private:
  int index_{};
  maliput::api::RoadPosition start_road_position_{};

Can omit {} for all non-primitive types.

---

include/maliput/routing/route_position_result.h line 37 at r5 (raw file):

/// Maps a position in the LANE and INERTIAL Frames within a RoutePhase.
struct RoutePhasePositionResult {

See other comment about whether we could treat RoutePhase as an internal implementation detail. If so, this could be named "RoutePositionResult" or even just "PositionResult", which should still be clear given that it is in the "routing" namespace.

We could also omit "RoutePositionResult" below since that's an internal implementation detail.

---

include/maliput/routing/route_position_result.h line 40 at r5 (raw file):

  /// The maliput::api::LaneSRange within the RoutePhase where this position
  /// is located.
  maliput::api::LaneSRange lane_s_range;

Should remove "maliput::" since this is already in the "maliput" namespace.

---

include/maliput/routing/route_position_result.h line 42 at r5 (raw file):

  maliput::api::LaneSRange lane_s_range;
  /// The LANE-Frame position within the `lane_s_range`.
  maliput::api::LanePosition lane_position{};

Can omit {} here and on line 44 since these are not primitive types.

---

include/maliput/routing/router.h line 59 at r3 (raw file):

  MALIPUT_NO_COPY_NO_MOVE_NO_ASSIGN(Router);

  /// Computes the Route that joins @p start_road_postion to

Typo: "start_road_postion" should be "start_road_position"

---

include/maliput/routing/router.h line 89 at r3 (raw file):

  // nullptr. The lifetime of this pointer must exceed that of this object.
  // @throws maliput::common::assertion_error When @p road_network is nullptr.
  explicit Router(const maliput::api::RoadNetwork* road_network) : road_network_(road_network) {

I recommend removing this constructor, road_network(), and road_network_ since derivative classes can do it for themselves should they need a RoadNetwork. This top-level class can simply specify a standard ComputeRoute() method. How that route is actually computed, and whether having access to a RoadNetwork (or just a RoadGeometry) is necessary, is an implementation detail that derivative classes can handle.

---

include/maliput/routing/router.h line 32 at r5 (raw file):

#include <optional>
#include <vector>

Unused.

---

include/maliput/routing/router.h line 62 at r5 (raw file):

  /// @p end_road_position under @p routing_constraints.
  ///
  /// @param start_road_position The start point in the maliput::api::RoadGeometry.

Per other comment, I recommend naming this parameter "start" for brevity.

Similarly, I recommend renaming "end_road_position" to be "end".

---

include/maliput/routing/router.h line 73 at r5 (raw file):

  /// @throws maliput::common::assertion_error When @p end_road_position is not valid.
  /// @throws maliput::common::assertion_error When @p routing_constraints is not valid.
  std::optional<Route> ComputeRoute(const maliput::api::RoadPosition& start_road_position,

Should remove "maliput::" since this is already in the "maliput" namespace.

---

include/maliput/routing/routing_constraints.h line 43 at r3 (raw file):

Previously, agalbachicar (Agustin Alba Chicar) wrote…

This is an interesting case that we verbally discussed with @stonier and @liangfok in a weekly.

I think that we can capture the breakdown of a physical road into pieces that reflect each RoutePhase if the Router has some kind of knowledge about the geometric, kinematic and dynamic constraints of the vehicle. That still could not be enough to deal with the traffic congestion situation or other state specific conditions in which the vehicle should be immersed in to determine which is the right range for lane switching and performing this maneuver.

Thinking of the API, I still think the proposal is valid. This set of classes and responsibilities can adapt to various levels of sophistication in the Router. As the Router becomes omniscient and omnipresent (i.e. knows the complete and exact state of all the agents in the road at any present and past time, and their capabilities and constraints) the Route definition can include the partitioning of a RoutePhase into multiple RoutePhases that provide a more accurate representation of what the vehicle needs or can do. Moving in the opposite direction works as well I think. A simple Router that only knows about connectivity should offer a simple Route description that makes sense considering the connectivity graph.

One aspect of the Route that I could not capture but I think it is not relevant at the moment is how the dynamics of the rules and traffic can make a Route no longer cost effective as it is traversed. For example, as a traffic jam becomes more and more dense, the cost of a specific route is bigger than an alternative and you may want to diverge. This is clearly solved by an agent behavior feature that polls the Router but you don't the asynchronous notification.

Yeah I think sophsticated behaviors that account for dynamic situations should be done within the agent via polling and re-routing rather than captured within a particular route specification itself. I view the Route as a passive and static data structure that captures viable options at the time the route is computed. Over time, a Route may no longer be optimal or even viable, at which point a new Route must be computed, which is okay.

In general, I recommend keeping the Route as simple as possible for the agent, to the point of not even requiring that agents interact with RoutePhases.

---

include/maliput/routing/routing_constraints.h line 32 at r5 (raw file):

#include <optional>
#include <string>

Unused.

---

include/maliput/routing/routing_constraints.h line 33 at r5 (raw file):

#include <optional>
#include <string>
#include <unordered_map>

Unused.

---

include/maliput/routing/routing_constraints.h line 39 at r5 (raw file):

/// Holds the constraints that can be applied to the Router when computing a
/// Route.

This docstring can be a single line.

---

include/maliput/routing/routing_constraints.h line 41 at r5 (raw file):

/// Route.
struct RoutingConstraints {
  /// Allows maliput::api::Lane switchs within a RoutePhase when computing the

"switchs" should be "switches".

---

include/maliput/routing/routing_constraints.h line 42 at r5 (raw file):

struct RoutingConstraints {
  /// Allows maliput::api::Lane switchs within a RoutePhase when computing the
  /// Route.

This docstring can be a single line.

---

include/maliput/routing/routing_constraints.h line 44 at r5 (raw file):

  /// Route.
  bool allow_lane_switch{true};
  /// Defines the maximum cost cost of a RoutePhase. When set, it must be

"cost cost" should be "cost".

---

include/maliput/routing/routing_constraints.h line 44 at r5 (raw file):

  /// Route.
  bool allow_lane_switch{true};
  /// Defines the maximum cost cost of a RoutePhase. When set, it must be

What does "cost" mean in this context? What are its units?

---

include/maliput/routing/routing_constraints.h line 51 at r5 (raw file):

/// Validates the constraints of each parameter of @p routing_constraints.
/// @param routing_constraints A RoutingConstraints to validate.
/// @throw maliput::common::assertion_error When one of the preconditions of @p routing_constraints are violated.

I wonder whether throwing an exception may be too extreme. Returning a Boolean and allowing the caller to decide what to do would be more flexible.

[liangfok]

Reviewable status: all files reviewed, 45 unresolved discussions (waiting on @agalbachicar, @andrewbest-tri, @francocipollone, and @stonier)

---

include/maliput/routing/route.h line 44 at r3 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Can the RoutePhase abstraction be hidden as an internal implementation detail? Do agents really need to know that the route is broken into multiple phases? It might be easier for agents if they could treat a Route as a monolitic object and to directly obtain the relevant LaneSRanges based on where they currently are rather than needing to go through the RoutePhase intermediary.

RoutePhase and Route have very similar API, which indicates to me that perhaps RoutePhase need not be directly used by agents.

Thinking about this some more, the current levels of abstraction are: Route ==> RoutePhase ==> vector of LaneSRanges. This triple-layer abstraction seems more than necessary from an agent's perspective, and also is limited to a single set of LaneSRanges in terms of informing agents of the ongoing route. I wonder whether using Route ==> vector of LaneSRoutes would be more useful / informative. That would enable agents to look further ahead.

[stonier]

A driving set of golden examples would be really useful to have.

[stonier]

Excellent graphs, thanks @agalbachicar. They really help drive the discussion.

There is a piece not captured though, your graph implies that there are branch points within a straight contiguous segment of road.....but simply imagine your much nicer graph without branch points in the middle of contiguous straight lanes to see my point.

This is a good example. What is the expected response for this situation? If I were to draw graphs like you have above but without the middle branch points, I don't see how you can avoid a wrong response.

[stonier]

end_road_position?

[stonier]

Does this go out to include more than the directly left/right lane? e.g. four lane highway with on-ramp and exit 1km apart and just one segment connecting them (no branch points in the middle of the highway.

  ------x------A>-------x------
  ------x------B>-------x------
  ------x------C>-------x------
  ------x------D>-------x------
  --E--/                       \----F ---

Would it only include C & D?

[stonier]

A driving set of golden examples would be really useful to have.

[stonier]

A driving set of golden examples would be really useful to have.

[andrewbest-tri]

Reviewable status: all files reviewed, 47 unresolved discussions (waiting on @agalbachicar, @francocipollone, @liangfok, and @stonier)

---

include/maliput/routing/route.h line 44 at r3 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Thinking about this some more, the current levels of abstraction are: Route ==> RoutePhase ==> vector of LaneSRanges. This triple-layer abstraction seems more than necessary from an agent's perspective, and also is limited to a single set of LaneSRanges in terms of informing agents of the ongoing route. I wonder whether using Route ==> vector of LaneSRoutes would be more useful / informative. That would enable agents to look further ahead.

I disagree FWIW. Our prior route abstraction hid the phasing and made it hard for agents to re-plan, analyze alternative, or to do work based on the underlying road network. I.e., if we lose access to specific routing information it will be harder to make decisions about rules re: what lane I am actually on. I think the agents will want access to the alternatives if possible

[andrewbest-tri]

Reviewable status: all files reviewed, 47 unresolved discussions (waiting on @agalbachicar, @francocipollone, @liangfok, and @stonier)

---

include/maliput/routing/route_phase.h line 72 at r3 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

There shouldn't be a need for this. A RoutePhase object shouldn't need to know how many other RoutePhases exist before or after it.

I disagree. depending on what the agent has access to, lookahead is easier the routephase can provide a helper to lookahead.

---

include/maliput/routing/route_phase.h line 79 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

See other comment about not including a RoadNetwork inside a RoutePhase for separation-of-concerns purposes.

disagree here again. RoadNetwork is required to do anything at all with the phase. this makes user-land way easier since my methods don't need to take a network pointer AND a phase just so i can do anything

[liangfok]

Reviewable status: all files reviewed, 47 unresolved discussions (waiting on @agalbachicar, @andrewbest-tri, and @francocipollone)

---

include/maliput/routing/route_phase.h line 72 at r3 (raw file):

Previously, andrewbest-tri wrote…

I disagree. depending on what the agent has access to, lookahead is easier the routephase can provide a helper to lookahead.

This could be moot given the other threads on eliminating RoutePhase in favor of LaneSRoutes. If agents are provide a set of LaneSRoute objects, all of which are viable paths from where the agent is (or was) to where it wants to go, it will have the max possible lookahead information.

[agalbachicar]

A driving set of golden examples would be really useful to have.

Here are some. Please open those with draw.io

routing_golden_examples.drawio.zip

[agalbachicar]

I've address most of the comments in caa93a0. Reviewers should expect a new API based on our conversation on May 30th. I'll let you know as soon as I have it ready for review.

Reviewable status: all files reviewed, 44 unresolved discussions (waiting on @andrewbest-tri, @francocipollone, @liangfok, and @stonier)

---

include/maliput/routing/lane_s_range_relation.h line 50 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

What is the relationship between the direction of travel and the lane's positive S direction? Does it depend on lane_s_range.s_range().WithS()? For example, if lane_s_range.s_range().WithS() is positive, the direction of travel is in the +S direction, whereas if lane_s_range.s_range().WithS() if false, the direction of travel is in the -S direction?

The RoadGeometry on its own does provide infomration about the direction of travel. We need to look into the RoadRulebook. The Route and RoutePhases are built out of a directed graph which considers the direction of travel of Lanes. Thus, SRange::WithS() serves as a proxy of SRange::s1() > SRange::s0() but not strictly attached to the direction of travel.

I must say that this is not expected, but it is not guaranteed at the moment nor we have proper documentation to state it.

---

include/maliput/routing/lane_s_range_relation.h line 69 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

To reduce verbosity while maintaining clarity, I recommend removing "ToThe" from all these names.

Done.

---

include/maliput/routing/lane_s_range_relation.h line 72 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

These two are unique in that the two LaneSRanges are not in physical contact. I wonder whether they are necessary since they could be inferred via the transitive relationship of multiple kAdjacentToTheLeft/kAdjacentToTheRight relations.

I think it adds value because it reduces the need of navigating through the hierarchy of LaneSRanges. I suggest we keep them.

---

include/maliput/routing/route.h line 82 at r1 (raw file):

Previously, francocipollone (Franco Cipollone) wrote…

nit:

  std::size_t Size() const { route_phases_.size(); }

or

  int Size() const { static_cast<int>(route_phases_.size()); }

I think this is solved now.

---

include/maliput/routing/route.h line 44 at r3 (raw file):

Previously, andrewbest-tri wrote…

I disagree FWIW. Our prior route abstraction hid the phasing and made it hard for agents to re-plan, analyze alternative, or to do work based on the underlying road network. I.e., if we lose access to specific routing information it will be harder to make decisions about rules re: what lane I am actually on. I think the agents will want access to the alternatives if possible

Per meeting on May 9th, I think the competing ideas are:

• Route and RoutePhases as it is presented in this PR.
• Expose a flat graph of LaneSRanges rather than a sequenced Route with RoutePhases.
• Instead of using LaneSRanges, use a waypoints in the LANE-Frame to define the perimeter of the route.

We should evaluate a set of golden examples and which is the expected result with each one.

Per meeting on May 30th, we agreed to keep the Route with the graph of LaneSRanges and the RoutePhases as a proxy to reduce the result space of all the possible paths between the start and the end within the Route.

I don't expect this to be the definite API. I'll keep you posted once I've introduced the changes.

---

include/maliput/routing/route.h line 67 at r3 (raw file):

/// TODO(#453): Validate end to end connection of the RoutePhases.

That is required. It can be argued that I only need the RoadGeometry. I suggest we keep the RoadNetwork for future flexibility.

---

include/maliput/routing/route.h line 83 at r3 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Let's name this method "size()" since it could be considered an accessor and to be consistent with line 89 in r5.

Accessors and mutators (get and set functions) may be named like variables. These often correspond to actual member variables, but this is not required. For example, int count() and void set_count(int count).

https://google.github.io/styleguide/cppguide.html#Function_Names

Done.

---

include/maliput/routing/route.h line 44 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

"to go from" should be "that go from".

Done.

---

include/maliput/routing/route.h line 57 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

"begining" should be "beginning".

Done.

---

include/maliput/routing/route.h line 75 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Should remove "maliput::" since this is already in the "maliput" namespace. Ditto below.

Done.

---

include/maliput/routing/route.h line 132 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

I recommend deleting "expressed into the LANE-Frame position" since there is no other way in which a RoadPosition can be expressed.

Done.

---

include/maliput/routing/route.h line 141 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Since ordering matters, we should specify which one is fixed and which one is relative. In this case, I assume 'a' is fixed and 'b' is relative, meaning this should be:

/// Finds the relation of @p lane_s_range_b with respect to @p lane_s_range_a.

Thanks! Great suggestion! I thought of it and I missed it when writing it.

---

include/maliput/routing/route_phase.h line 50 at r1 (raw file):

Previously, agalbachicar (Agustin Alba Chicar) wrote…

Please take a look to the proposed solution. It is not in line with my previous comment but I think it offers a simplified version and probably more scalable than the one I proposed.
As a next step, we can provide a std::vector<maliput::api::LaneSRange> FindLaneSRanges(const maliput::api::LaneSRange lane_s_range, LaneSRangeRelation relation) const;. That should offer the two way identification of relation between LaneSRanges (for a pair of ranges, and give a range and the relation find those that match the requirement). WDYT?

Solving this comment per new type introduced: LaneSRangeRelation.

---

include/maliput/routing/route_phase.h line 145 at r1 (raw file):

Previously, stonier (Daniel Stonier) wrote…

I tend to agree. If there's other ways to get the rules, then it makes this redundant ... unless there is e.g. caching / fast lookup considerations?

Caching and fast lookup are important in large RoadNetworks. Also, there is convenient filtering for the position result space that focuses in the set of api::LaneSRanges that only belongs to this RoutePhase. Doing that outside of the RoutePhase is possible but it will require implementation at the agent level multiple times.

---

include/maliput/routing/route_phase.h line 56 at r3 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Would specifying start/end road_positions be redundant to default_lane_s_range? That is, the beginning of the route is the beginning of default_lane_s_range and the end of the route is the end of default_lane_s_range.

Great question. In my opinion the answer is no because the start and end lane may not be the same. By deciding which is the default_lane_s_range, we should pick one or the other, or another criteria (based on the routing cost for example).

---

include/maliput/routing/route_phase.h line 72 at r3 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

This could be moot given the other threads on eliminating RoutePhase in favor of LaneSRoutes. If agents are provide a set of LaneSRoute objects, all of which are viable paths from where the agent is (or was) to where it wants to go, it will have the max possible lookahead information.

Per meeting on May 30th, we agreed to keep this class.

---

include/maliput/routing/route_phase.h line 47 at r5 (raw file):

Previously, stonier (Daniel Stonier) wrote…

Does this go out to include more than the directly left/right lane? e.g. four lane highway with on-ramp and exit 1km apart and just one segment connecting them (no branch points in the middle of the highway.

  ------x------A>-------x------
  ------x------B>-------x------
  ------x------C>-------x------
  ------x------D>-------x------
  --E--/                       \----F ---

Would it only include C & D?

Per meeting on May 30th, we decided that we should provide A, B, C and D. It is up to the agent responsibility to consider a viable maneuver going up to A to then leave the highway in F.

---

include/maliput/routing/route_phase.h line 69 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

I recommend renaming "start_road_position" to be "start" and "end_road_position" to be "end". It will be less verbose and should maintain clarity based on the data type.

Not solving for now, but just leaving a comment that this will mutate to a set (a std::vector) of api::RoadPositions for both the start and end positions.

---

include/maliput/routing/route_phase.h line 71 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

What is the use case for having start_road_position be in an adjacent LaneSRange? Wouldn't it be more clear if it was always the start of the default_lane_s_range, in which case start_road_position wouldn't even be necessary?

Ditto for end_road_position. Couldn't be eliminate this parameter and enforce that the end of default_lane_s_range always be the end road position?

Another thought: What is the reason for having to define a start and end? Why not simply provide a set of adjacent LaneSRanges and allow the agent to decide for itself where the start and end are?

Per meeting on May 30th, we agreed to:

• Convert the start and road position to a set of positions that represent the possible points at which you could end or leave the RoutePhase.
• It is possible that either the start and end road position sets have less points than the number of LaneSRanges. That is an indication of which are the LaneSRanges which allow you to continue moving through Phases using the BranchPoint logic. Otherwise, agents must perform a lane switch.
• There is more work to be done about which is the default_lane_s_range in intermediate phases. I agree it must be the one that an agent should prioritize to enter the RoutePhase but it is not clear to me yet for intermediate RoutePhases how we will select those. Thus, if agreed, I suggest we remove the default for now.

---

include/maliput/routing/route_phase.h line 75 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Should order the parameter descriptions the same as they are in the method signature. In this case, lane_s_range_tolerance is the 2nd parameter in the method's signature.

Done.

---

include/maliput/routing/route_phase.h line 77 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Instead of providing separate default_lane_s_range and adjacent_lane_s_range, consider providing a single const std::vector<maliput::api::LaneSRange>& lane_s_ranges parameter and an index into this vector specifying the default.

Done.

---

include/maliput/routing/route_phase.h line 78 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

"adjancent" should be "adjacent".

Done.

---

include/maliput/routing/route_phase.h line 79 at r5 (raw file):

// TODO(#543): Validate that lane_s_ranges_ are effectively adjacent one to another.

// TODO(#543): Validate api::LaneSRanges are in the RoadNetwork.

I think these two should be proof of the need, also the APIs to get a RoutePhasePositionResult require the RoadNetwork (or the RoadGeometry to be precise).

---

include/maliput/routing/route_phase.h line 86 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Can omit "maliput::" since this is already in the "maliput" namespace.

Done.

---

include/maliput/routing/route_phase.h line 102 at r5 (raw file):

Previously, stonier (Daniel Stonier) wrote…

end_road_position?

Done.

---

include/maliput/routing/route_phase.h line 166 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Can omit {} for all non-primitive types.

Done.

---

include/maliput/routing/route_position_result.h line 37 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

See other comment about whether we could treat RoutePhase as an internal implementation detail. If so, this could be named "RoutePositionResult" or even just "PositionResult", which should still be clear given that it is in the "routing" namespace.

We could also omit "RoutePositionResult" below since that's an internal implementation detail.

I agree. I left only RoutePositionResult which has two indices to the RoutePhase and the api::LaneSRange of it.

---

include/maliput/routing/route_position_result.h line 40 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Should remove "maliput::" since this is already in the "maliput" namespace.

Done.

---

include/maliput/routing/route_position_result.h line 42 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Can omit {} here and on line 44 since these are not primitive types.

Done.

---

include/maliput/routing/router.h line 89 at r3 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

I recommend removing this constructor, road_network(), and road_network_ since derivative classes can do it for themselves should they need a RoadNetwork. This top-level class can simply specify a standard ComputeRoute() method. How that route is actually computed, and whether having access to a RoadNetwork (or just a RoadGeometry) is necessary, is an implementation detail that derivative classes can handle.

Done.

---

include/maliput/routing/router.h line 32 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Unused.

Done.

---

include/maliput/routing/router.h line 62 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Per other comment, I recommend naming this parameter "start" for brevity.

Similarly, I recommend renaming "end_road_position" to be "end".

Done.

---

include/maliput/routing/router.h line 73 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Should remove "maliput::" since this is already in the "maliput" namespace.

Done.

---

include/maliput/routing/routing_constraints.h line 43 at r3 (raw file):

Previously, stonier (Daniel Stonier) wrote…

Excellent graphs, thanks @agalbachicar. They really help drive the discussion.

There is a piece not captured though, your graph implies that there are branch points within a straight contiguous segment of road.....but simply imagine your much nicer graph without branch points in the middle of contiguous straight lanes to see my point.

This is a good example. What is the expected response for this situation? If I were to draw graphs like you have above but without the middle branch points, I don't see how you can avoid a wrong response.

Per meeting on May 30th, we agreed to keep in that case the extra api::LaneSRanges that lead the agent nowhere. However, the end point of those api::LaneSRanges will not belong to the end RoutePhase point set. That is the piece of information that allows the agent to know which api::LaneSRanges can be used or not to continue driving through the Route. We can provide this information via a convenient method or the agent can derive it on its own.

---

include/maliput/routing/routing_constraints.h line 32 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Unused.

Done.

---

include/maliput/routing/routing_constraints.h line 33 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Unused.

Done.

---

include/maliput/routing/routing_constraints.h line 39 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

This docstring can be a single line.

Done.

---

include/maliput/routing/routing_constraints.h line 41 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

"switchs" should be "switches".

Done.

---

include/maliput/routing/routing_constraints.h line 42 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

This docstring can be a single line.

Done.

---

include/maliput/routing/routing_constraints.h line 44 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

"cost cost" should be "cost".

Done.

---

include/maliput/routing/routing_constraints.h line 44 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

What does "cost" mean in this context? What are its units?

Cost is a router implementation detail. Any routing algorithm has some notion of cost which can be expressed in money, units, distance, time, or any other magnitude that helps to account of a cost metric. It must be the same for the entire RoadGeometry but not necessarily constant Router to Router.

---

include/maliput/routing/routing_constraints.h line 51 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

I wonder whether throwing an exception may be too extreme. Returning a Boolean and allowing the caller to decide what to do would be more flexible.

The entire API is built around throwing exceptions. The caller can decide to catch it and do something else. We don't expect these exceptions to happen at runtime in production code.

[agalbachicar]

@liangfok @stonier @andrewbest-tri @francocipollone it's ready for another review .
I'd appreciate your comments over this new revision.

Reviewable status: 0 of 7 files reviewed, 44 unresolved discussions (waiting on @andrewbest-tri, @francocipollone, @liangfok, and @stonier)

[liangfok]

Completed first pass.

Reviewed 6 of 7 files at r6, 1 of 1 files at r7, all commit messages.
Reviewable status: all files reviewed, 36 unresolved discussions (waiting on @agalbachicar, @andrewbest-tri, @francocipollone, and @stonier)

---

-- commits line 1 at r7:
Prior to merge, let's be sure to squash this into a single commit with a good summary & description.

---

include/maliput/routing/lane_s_range_relation.h line 50 at r5 (raw file):
To avoid confusion, let's replace:

direction of travel of the api::LaneSRange.

with:

direction of travel of the route.

This is to reduce the liklihood that readers will think the direction of travel is the same as api::LaneSRange().s_range().WithS().

---

include/maliput/routing/lane_s_range_relation.h line 81 at r7 (raw file):

  kUnrelated,
  kUnknown,
};

For debugging purposes, it would be nice to include a to-string mapper and a std::ostream operator<< override:

inline std::map<LaneSRangeRelation, const char*> LaneSRangeRelationMapper() {
  return {
    {LaneSRangeRelation::kAdjacentLeft, "kAdjacentLeft"},
    {LaneSRangeRelation::kAdjacentRight, "kAdjacentRight"},
    {LaneSRangeRelation::kLeft, "kLeft"},
    {LaneSRangeRelation::kRight, "kRight"},
    {LaneSRangeRelation::kSucceedingStraight, "kSucceedingStraight"},
    {LaneSRangeRelation::kSucceedingLeft, "kSucceedingLeft"},
    {LaneSRangeRelation::kSucceedingRight, ""kSucceedingRight},
    {LaneSRangeRelation::kPreceedingStraight, "kPreceedingStraight"},
    {LaneSRangeRelation::kPreceedingLeft, "kPreceedingLeft"},
    {LaneSRangeRelation::kPreceedingRight, "kPreceedingRight"},
    {LaneSRangeRelation::kUnrelated, "kUnrelated"},
    {LaneSRangeRelation::kUnknown, "kUnknown"},
  };
}

inline std::ostream& operator<<(std::ostream& os, const LaneSRangeRelation& relation) {
  os << LaneSRangeRelationMapper().at(relation);
  return os;
}

---

include/maliput/routing/route.h line 44 at r3 (raw file):

Previously, agalbachicar (Agustin Alba Chicar) wrote…

Per meeting on May 9th, I think the competing ideas are:

• Route and RoutePhases as it is presented in this PR.
• Expose a flat graph of LaneSRanges rather than a sequenced Route with RoutePhases.
• Instead of using LaneSRanges, use a waypoints in the LANE-Frame to define the perimeter of the route.

We should evaluate a set of golden examples and which is the expected result with each one.

Per meeting on May 30th, we agreed to keep the Route with the graph of LaneSRanges and the RoutePhases as a proxy to reduce the result space of all the possible paths between the start and the end within the Route.

I don't expect this to be the definite API. I'll keep you posted once I've introduced the changes.

I agree that phases are useful for long routes, like those that traverse multiple cities, states, or countries. I'm less sure they are necessary for shorter routes. For those I am afraid phases will uncessarily add complexity & confusion.

Here is a potential compromise: Keep RoutePhase but make it have a single start position and end position. That would make the API less confusing since users currently need to treat RoutePhase::start_positions().at(0) and RoutePhase::end_positions().at(0) different since those may correspond to the actual initial and goal locations of the overall Route. It would also emphasize the fact that that phases are intended to increase scalability, are mini-routes, and a Route could very well consist of a single phase.

Not going to block this PR though. We can merge this PR as-is and maybe revisit after gaining more usage experience. Just something to keep in mind.

---

include/maliput/routing/route.h line 48 at r7 (raw file):
I suggest replacing:

The graph is represented by a sequence of RoutePhases.

with:

For scalability, the route is divided into a sequence of RoutePhases.

This is to further emphasize the motivation for providing a phasing abstraction, and to hint that short routes may only have a single phase.

---

include/maliput/routing/route.h line 50 at r7 (raw file):

/// graph for agent navigation. The graph is represented by a sequence of
/// RoutePhases. These entities allow agents to reduce the path search space
/// by constraining the lookup towards the end api::RoadPosition.

This paragraph ends with "end api::RoadPosition" whereas the next paragraph ends with "end goal". Let's make them consistent. I lean towards "end goal" since I feel that is more colloquial and less technical but would be fine either way.

---

include/maliput/routing/route.h line 57 at r7 (raw file):
Let's replace:

The first RoutePhase start road position

with:

The first RoutePhase's first start position

since a RoutePhase can have multiple start positions.

---

include/maliput/routing/route.h line 58 at r7 (raw file):
Ditto. Replace:

The last RoutePhase end road position

with:

The last RoutePhase's first end position

since a RoutePhase can have multiple end positions.

---

include/maliput/routing/route.h line 62 at r7 (raw file):

/// one RoutePhase exactly matches the beginning of the next RoutePhase in the
/// sequence.
///

Let's move the "Where:" section that's defined below here since readers must first know the meaning of the symbols before looking a the ASCII art.

/// Let:
/// - `s` indicates the start of the Route.
/// - `e` indicates the end of the Route.
/// - `x` indicates the start of end of an api::LaneSRange.
/// - `*` indicates the start of end of RoutingPhase.
/// - `-` indicates the path of an api::LaneSRange.
/// - `_` indicates the path of an api::LaneSRange within a RoutingPhase.
/// - `S0`, `S1`, ...: are api::Segments.
/// - `L0`, `L1`, ...: are api::Lanes.
///

---

include/maliput/routing/route.h line 64 at r7 (raw file):

///
/// A valid representation of this routing request for this geometry (starting
/// `s` and ending at `e`):

For increased clarity, let's replace:

/// A valid representation of this routing request for this geometry (starting
/// `s` and ending at `e`):

with:

/// Consider the following road geometry and routing request:

---

include/maliput/routing/route.h line 81 at r7 (raw file):

/// </pre>
///
/// And yields the following route:

Let's replace:

/// And yields the following route:

with:

/// A valid Route could be:

---

include/maliput/routing/route.h line 110 at r7 (raw file):

/// Depending on where queried, different api::LaneSRoutes are returned, for
/// example, if queried from `s`, the returned sequence will be:
/// {S0:L0, S2:L2, S2:L1, S2:L0, S3:L0, S4:L0}

Shouldn't this also include S3:L1 and S4:L1? An agent could switch lanes from S4:L1 to S4:L0 while in S4 right?

---

include/maliput/routing/route.h line 112 at r7 (raw file):

/// {S0:L0, S2:L2, S2:L1, S2:L0, S3:L0, S4:L0}
///
/// And if queried at any point in S3:L2: {S3:L2, S3:L1, S3:L0, S4:L0}.

Ditto: Shouldn't this include S4:L1?

---

include/maliput/routing/route.h line 146 at r7 (raw file):

  const RoutePhase& Get(int index) const { return route_phases_.at(index); }

  /// @return The start of this Route.

Let's clarify that this is just a convenience method for information can be obtained via other API:

/// Returns the start of this Route. This is a convenience method for Get(0).start_positions().front().

Ditto for end_route_position() below.

---

include/maliput/routing/route.h line 204 at r7 (raw file):

  }

  /// Computes an api::LaneSRoute from @p start_position towards

"towards" indicates that it might not actually reach end_route_position(). Yet the @return line of the docstring below says "connecting @p start_position and end_route_position()," which indicates that end_route_position() is definitely reached. Let's clarify whether end_route_position() is actually reached.

---

include/maliput/routing/route.h line 216 at r7 (raw file):

  /// valid.
  /// @return The api::LaneSRoute connecting @p start_position and
  /// end_route_position().

Could the returned api::LaneSRoute span multiple phases?

Does this violate the abstraction barriers between a Route and Router, and between a Route and RoutePhase?

Seems like this method is implementing a router within a route, which is odd.

Also seems like, with this method, agents don't need to know about phases.

---

include/maliput/routing/route_phase.h line 72 at r3 (raw file):

Previously, agalbachicar (Agustin Alba Chicar) wrote…

Per meeting on May 30th, we agreed to keep this class.

Regarding my original comment, I meant it is odd for a RoutePhase to know its own index within the overall Route since that is clearly state that resides outside of the RoutePhase class.

Happy to unblock this thread and allow PR to be merged though. We can always iterate.

---

include/maliput/routing/route_phase.h line 79 at r5 (raw file):

Previously, agalbachicar (Agustin Alba Chicar) wrote…

// TODO(#543): Validate that lane_s_ranges_ are effectively adjacent one to another.

// TODO(#543): Validate api::LaneSRanges are in the RoadNetwork.

I think these two should be proof of the need, also the APIs to get a RoutePhasePositionResult require the RoadNetwork (or the RoadGeometry to be precise).

The validation could be done via a standalone method that takes as input a RoutePhase and a RoadNetwork. Arguably, restricting the validation to only occur at time of construction is less flexible than being able to validate it anytime after construction.

Imagine a user having multiple overlapping RoadNetwork objects, like one for the whole Tokyo and another for a portion of Tokyo like Odaiba. If we had a standalone validation method, we could validate a given RoutePhase against both RoadNetworks.

Similarly, having standalone FindRoutePhasePosition methods would enable users to decide which RoadNetwork object to use. The user could then do some optimizations like using the Odaiba RoadNetwork when the agent is in Odaiba and using the Tokyo RoadNetwork when the agent is elsewhere within Tokyo.

(Not blocking this PR though...feel free to merge as is.)

---

include/maliput/routing/route_phase.h line 43 at r7 (raw file):

namespace routing {

/// Manages a phase in a Route, towards the its end.

Should delete "the".

---

include/maliput/routing/route_phase.h line 46 at r7 (raw file):

///
/// It is composed of a set of api::LaneSRanges. All these api::LaneSRanges
/// are adjacent one to the other and present different alternative path

Should delete "one to the other" for brevity / clarity.

---

include/maliput/routing/route_phase.h line 47 at r7 (raw file):

/// It is composed of a set of api::LaneSRanges. All these api::LaneSRanges
/// are adjacent one to the other and present different alternative path
/// segments towards the end of the Route. This is a convinient entity to reduce

Typo: convinient, should be "convenient".

---

include/maliput/routing/route_phase.h line 51 at r7 (raw file):

/// paths within the Route.
///
/// All the initial api::RoadPositions consitute the set of start positions of

Typo: consitute, should be "constitute".

---

include/maliput/routing/route_phase.h line 58 at r7 (raw file):

/// agents to maneuver in. At least one api::RoadPosition in both the start and
/// end sets must be equal or overlapping in the INERTIAL-Frame another
/// api::RoadPosition in the preceeding and succeeding RoutePhase respectively.

Typo: preceeding, should be "preceding".

---

include/maliput/routing/route_phase.h line 155 at r7 (raw file):

  /// @param inertial_position The INERTIAL-Frame position.
  /// @return A RoutePositionResult.
  RoutePositionResult FindRoutePhasePositionBy(const api::InertialPosition& inertial_position) const {

BTW, consider removing the "By" in this method and the one below since that should be clear based on the parameter's type and it will be more concise.

---

include/maliput/routing/route_phase.h line 155 at r7 (raw file):

  /// @param inertial_position The INERTIAL-Frame position.
  /// @return A RoutePositionResult.
  RoutePositionResult FindRoutePhasePositionBy(const api::InertialPosition& inertial_position) const {

To avoid mixing Route and RoutePhase abstractions, I recommend that this method and the one below return a PhasePositionResult with the following definition

/// The result of a position query on a Phase.
struct PhasePositionResult {
  /// The index of the api::LaneSRange within the RoutePhase.
  int lane_s_range_index{};
  /// The LANE-Frame position within the `lane_s_range`.
  api::LanePosition lane_position;
  /// The INERTIAL-Frame position of `lane_position`.
  api::InertialPosition inertial_position;
  /// The Euclidean distance between the point used for querying and
  /// `inertial_position`.
  double distance{};
};

The definition of RoutePositionResult could then make use of PhasePositionResult:

/// The result of a position query on a Route.
struct RoutePositionResult {
  /// The index of the RoutePhase in the Route.
  int route_phase_index{};

  /// The position within the Phase.
  PhasePositionResult phase_position_result;
};

---

include/maliput/routing/route_position_result.h line 36 at r7 (raw file):

namespace routing {

/// Maps a position in the LANE and INERTIAL Frames within a Route.

BTW, should probably replace "Maps" with "Contains" or "Holds" since the data structure isn't actually a map with keys / values.

---

include/maliput/routing/route_position_result.h line 42 at r7 (raw file):

  /// The index of the api::LaneSRange within the RoutePhase.
  int lane_s_range_index{};
  /// The LANE-Frame position within the `lane_s_range`.

`lane_s_range`

This should be "LaneSRange" since there is no lane_s_range member variable.

---

include/maliput/routing/router.h line 45 at r7 (raw file):

/// Computes Routes that join one point with another in the
/// api::RoadGeometry.

I recommend simplifying this to be:

/// Computes Routes within an api::RoadNetwork.

There are several other references to "api::RoadGeometry" below. I recommend either removing them or switching to "api::RoadNetwork".

---

include/maliput/routing/router.h line 58 at r7 (raw file):

  MALIPUT_NO_COPY_NO_MOVE_NO_ASSIGN(Router);

  /// Computes the Route that joins @p start_road_position to

"@p start_road_position" should be "@p start".

---

include/maliput/routing/router.h line 59 at r7 (raw file):

  /// Computes the Route that joins @p start_road_position to
  /// @p end_road_position under @p routing_constraints.

"@p end_road_position" should be "@p end".

---

include/maliput/routing/router.h line 72 at r7 (raw file):

  /// @throws common::assertion_error When @p end is not valid.
  /// @throws common::assertion_error When @p routing_constraints is not valid.
  std::optional<Route> ComputeRoute(const api::RoadPosition& start, const api::RoadPosition& end,

This method can only return at most one Route. It would be more flexible if Router could return multiple Routes. I can definitely think of scenarios where mutiiple routes are possible, especially as the distance betweenstart and end increases. This method could return a std::vector<Route> that could contain zero or more Route objects. The user can decide study the various routes and pick-and-choose which one to follow.

[agalbachicar]

Thanks @liangfok for revisiting this. Comments were addressed, PTAL.

Reviewable status: 2 of 7 files reviewed, 30 unresolved discussions (waiting on @andrewbest-tri, @francocipollone, @liangfok, @p, and @stonier)

---

-- commits line 1 at r7:

Previously, liangfok (Chien-Liang Fok) wrote…

Prior to merge, let's be sure to squash this into a single commit with a good summary & description.

Ack!

---

include/maliput/routing/lane_s_range_relation.h line 50 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

To avoid confusion, let's replace:

direction of travel of the api::LaneSRange.

with:

direction of travel of the route.

This is to reduce the liklihood that readers will think the direction of travel is the same as api::LaneSRange().s_range().WithS().

Done.

---

include/maliput/routing/lane_s_range_relation.h line 81 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

For debugging purposes, it would be nice to include a to-string mapper and a std::ostream operator<< override:

inline std::map<LaneSRangeRelation, const char*> LaneSRangeRelationMapper() {
  return {
    {LaneSRangeRelation::kAdjacentLeft, "kAdjacentLeft"},
    {LaneSRangeRelation::kAdjacentRight, "kAdjacentRight"},
    {LaneSRangeRelation::kLeft, "kLeft"},
    {LaneSRangeRelation::kRight, "kRight"},
    {LaneSRangeRelation::kSucceedingStraight, "kSucceedingStraight"},
    {LaneSRangeRelation::kSucceedingLeft, "kSucceedingLeft"},
    {LaneSRangeRelation::kSucceedingRight, ""kSucceedingRight},
    {LaneSRangeRelation::kPreceedingStraight, "kPreceedingStraight"},
    {LaneSRangeRelation::kPreceedingLeft, "kPreceedingLeft"},
    {LaneSRangeRelation::kPreceedingRight, "kPreceedingRight"},
    {LaneSRangeRelation::kUnrelated, "kUnrelated"},
    {LaneSRangeRelation::kUnknown, "kUnknown"},
  };
}

inline std::ostream& operator<<(std::ostream& os, const LaneSRangeRelation& relation) {
  os << LaneSRangeRelationMapper().at(relation);
  return os;
}

Done.

---

include/maliput/routing/route.h line 48 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

I suggest replacing:

The graph is represented by a sequence of RoutePhases.

with:

For scalability, the route is divided into a sequence of RoutePhases.

This is to further emphasize the motivation for providing a phasing abstraction, and to hint that short routes may only have a single phase.

Done.

---

include/maliput/routing/route.h line 50 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

This paragraph ends with "end api::RoadPosition" whereas the next paragraph ends with "end goal". Let's make them consistent. I lean towards "end goal" since I feel that is more colloquial and less technical but would be fine either way.

Done.

---

include/maliput/routing/route.h line 57 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Let's replace:

The first RoutePhase start road position

with:

The first RoutePhase's first start position

since a RoutePhase can have multiple start positions.

Done.

---

include/maliput/routing/route.h line 58 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Ditto. Replace:

The last RoutePhase end road position

with:

The last RoutePhase's first end position

since a RoutePhase can have multiple end positions.

Done.

---

include/maliput/routing/route.h line 62 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Let's move the "Where:" section that's defined below here since readers must first know the meaning of the symbols before looking a the ASCII art.

/// Let:
/// - `s` indicates the start of the Route.
/// - `e` indicates the end of the Route.
/// - `x` indicates the start of end of an api::LaneSRange.
/// - `*` indicates the start of end of RoutingPhase.
/// - `-` indicates the path of an api::LaneSRange.
/// - `_` indicates the path of an api::LaneSRange within a RoutingPhase.
/// - `S0`, `S1`, ...: are api::Segments.
/// - `L0`, `L1`, ...: are api::Lanes.
///

Done.

---

include/maliput/routing/route.h line 64 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

For increased clarity, let's replace:

/// A valid representation of this routing request for this geometry (starting
/// `s` and ending at `e`):

with:

/// Consider the following road geometry and routing request:

Done.

---

include/maliput/routing/route.h line 81 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Let's replace:

/// And yields the following route:

with:

/// A valid Route could be:

Done.

---

include/maliput/routing/route.h line 110 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Shouldn't this also include S3:L1 and S4:L1? An agent could switch lanes from S4:L1 to S4:L0 while in S4 right?

Done.

Actually based on the conversation I think we should include all the lanes in the segment.

---

include/maliput/routing/route.h line 112 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Ditto: Shouldn't this include S4:L1?

Done.

Actually based on the conversation I think we should include all the lanes in the segment.

---

include/maliput/routing/route.h line 146 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Let's clarify that this is just a convenience method for information can be obtained via other API:

/// Returns the start of this Route. This is a convenience method for Get(0).start_positions().front().

Ditto for end_route_position() below.

Done.

---

include/maliput/routing/route.h line 204 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

"towards" indicates that it might not actually reach end_route_position(). Yet the @return line of the docstring below says "connecting @p start_position and end_route_position()," which indicates that end_route_position() is definitely reached. Let's clarify whether end_route_position() is actually reached.

Done.

---

include/maliput/routing/route.h line 216 at r7 (raw file):

Could the returned api::LaneSRoute span multiple phases?

Yes, it could. Actually, that's expected in the general case.

Does this violate the abstraction barriers between a Route and Router, and between a Route and RoutePhase?

I don't think so. In my opinion these are different levels of abstraction that don't overlap when explained all together with a short description. Let me expand a bit later.

Seems like this method is implementing a router within a route, which is odd.

In a sense, it might be true. But I think it is not that odd once you have a bit more of context. We may be lacking more documentation somewhere else. I suggest we leave a todo and reference to this discussion to better complete it in a future PR. Here is my rationale:

There are potentially multiple routes that connect two positions in a RoadGeometry. A Router would compute one Route based on certain request criteria and implementation. Within a Route, there are multiple paths which are represented with LaneSRoutes right now. Then, you can create trajectories out of a LaneSRoute to have a sequence of poses that the agent needs to follow.

Using mobile robotics navigation stack abstractions to help with the above, we can distinguish the global planner and the local planner. The global planner is well represented as the Router in this abstraction whereas the local planner comprehends the low-level trajectory planning that we get with LaneSRoutes and the final sampling of one of those.

Agents would use more or less information at the Route level or at the LaneSRoute level to later define which is the set of poses to follow.

Also seems like, with this method, agents don't need to know about phases.

I agree with the fact that agents don't need to know about phases. That said, agents don't need to know about LaneSRoutes (a LANE-Frame path) because they only care about the sequence of poses and not the LANE Frame abstraction. It is expected to be just a helper class to represent a measure of progress and reduce the mapping overhead within the Route.

---

What do you think about adding a preamble in the routing namespace to introduce the different levels of granularity that agents would be benefited from considering based on their sophistication level and the requirements to explode their complexity? I think it would be required before proceeding to actually explore the full potential of this abstraction. We can leave it as a TODO and complete it once we have played with some different agents in different circumstances.

---

include/maliput/routing/route_phase.h line 43 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Should delete "the".

Done.

---

include/maliput/routing/route_phase.h line 46 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Should delete "one to the other" for brevity / clarity.

Done.

---

include/maliput/routing/route_phase.h line 155 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

To avoid mixing Route and RoutePhase abstractions, I recommend that this method and the one below return a PhasePositionResult with the following definition

/// The result of a position query on a Phase.
struct PhasePositionResult {
  /// The index of the api::LaneSRange within the RoutePhase.
  int lane_s_range_index{};
  /// The LANE-Frame position within the `lane_s_range`.
  api::LanePosition lane_position;
  /// The INERTIAL-Frame position of `lane_position`.
  api::InertialPosition inertial_position;
  /// The Euclidean distance between the point used for querying and
  /// `inertial_position`.
  double distance{};
};

The definition of RoutePositionResult could then make use of PhasePositionResult:

/// The result of a position query on a Route.
struct RoutePositionResult {
  /// The index of the RoutePhase in the Route.
  int route_phase_index{};

  /// The position within the Phase.
  PhasePositionResult phase_position_result;
};

Done.

---

include/maliput/routing/route_position_result.h line 36 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

BTW, should probably replace "Maps" with "Contains" or "Holds" since the data structure isn't actually a map with keys / values.

Note that this changed based on your previous suggestion.

---

include/maliput/routing/route_position_result.h line 42 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

`lane_s_range`

This should be "LaneSRange" since there is no lane_s_range member variable.

Done.

---

include/maliput/routing/router.h line 45 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

I recommend simplifying this to be:

/// Computes Routes within an api::RoadNetwork.

There are several other references to "api::RoadGeometry" below. I recommend either removing them or switching to "api::RoadNetwork".

Done.

---

include/maliput/routing/router.h line 58 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

"@p start_road_position" should be "@p start".

Done.

---

include/maliput/routing/router.h line 59 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

"@p end_road_position" should be "@p end".

Done.

---

include/maliput/routing/router.h line 72 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

This method can only return at most one Route. It would be more flexible if Router could return multiple Routes. I can definitely think of scenarios where mutiiple routes are possible, especially as the distance betweenstart and end increases. This method could return a std::vector<Route> that could contain zero or more Route objects. The user can decide study the various routes and pick-and-choose which one to follow.

I think that it should be a different method, not the same one. That method will be able to return Routes based on a cost criteria rather than the one that minimizes it. Do you think something like:

std::vector<Route> ComputeRoutes(const api::RoadPosition& start, const api::RoadPosition& end, const RoutingConstraints& routing_constraints, const double max_cost = std::numeric_limits<double>::max()) const;

would work?

---

include/maliput/routing/routing_constraints.h line 43 at r3 (raw file):

Previously, stonier (Daniel Stonier) wrote…

Just for reference, the final proposal (in code - see the comments at the top of route.h) handles the situation by capturing more or less of lanes, lane start and lane end position.

• If it's got a lane and lane start, but no lane end, then the agent knows it needs to be off the lane by lane end.

Correct. Do you think we need to do anything with this flag?

[francocipollone]

LGTM! 🚀 🚀

[francocipollone]

nit: is it ok? is it start of end or start or end? Sorry but maybe I am missing something

[francocipollone]

offtopic: I must say it: this is real art

[francocipollone]

Gently pinging @stonier @liangfok @andrewbest-tri for wrapping up the reviews here as this PR blocks other PRs that go on top 🚀

[liangfok]

Apologies! Will get to this ASAP.

Reviewable status: 2 of 7 files reviewed, 30 unresolved discussions (waiting on @andrewbest-tri, @francocipollone, @p, and @stonier)

[andrewbest-tri]

LGTM

[andrewbest-tri]

does it makes sense for both of these to exist? Is phase position result useful without a phase index?

[agalbachicar]

Great point.

In a development branch which is detached from the latest addressed comments in this one I opted to include a pair<size_t, size_t> to identify a LaneSRange within a Route. That proved to be useful to iterate, search and compare LaneSRanges when processing relationships between them and LaneSRoutes from a specific coordinate towards the end.

IMO, we may see uses of them both similar to RoadPosition and LanePosition. Converting to and from each other may be simple with the appropriate context and save some extra duplication.

I suggest we keep them for a little bit more and remove / amend the API once we finish with a base implementation if it turns up to be redundant or useless. What do you think?

[agalbachicar]

Development branch link: https://github.com/maliput/maliput/blob/agalbachicar/%23543_routing_development/include/maliput/routing/route.h#L117-L120

[andrewbest-tri]

Makes sense to me. Perhaps we just need to make sure in most cases to prefer the more extensive struct where possible in the API 👍

[liangfok]

Completed 2nd pass.

Reviewed 5 of 5 files at r8, all commit messages.
Reviewable status: all files reviewed, 14 unresolved discussions (waiting on @agalbachicar, @andrewbest-tri, @francocipollone, and @stonier)

---

include/maliput/routing/route.h line 216 at r7 (raw file):

Previously, agalbachicar (Agustin Alba Chicar) wrote…

Could the returned api::LaneSRoute span multiple phases?

Yes, it could. Actually, that's expected in the general case.

Does this violate the abstraction barriers between a Route and Router, and between a Route and RoutePhase?

I don't think so. In my opinion these are different levels of abstraction that don't overlap when explained all together with a short description. Let me expand a bit later.

Seems like this method is implementing a router within a route, which is odd.

In a sense, it might be true. But I think it is not that odd once you have a bit more of context. We may be lacking more documentation somewhere else. I suggest we leave a todo and reference to this discussion to better complete it in a future PR. Here is my rationale:

There are potentially multiple routes that connect two positions in a RoadGeometry. A Router would compute one Route based on certain request criteria and implementation. Within a Route, there are multiple paths which are represented with LaneSRoutes right now. Then, you can create trajectories out of a LaneSRoute to have a sequence of poses that the agent needs to follow.

Using mobile robotics navigation stack abstractions to help with the above, we can distinguish the global planner and the local planner. The global planner is well represented as the Router in this abstraction whereas the local planner comprehends the low-level trajectory planning that we get with LaneSRoutes and the final sampling of one of those.

Agents would use more or less information at the Route level or at the LaneSRoute level to later define which is the set of poses to follow.

Also seems like, with this method, agents don't need to know about phases.

I agree with the fact that agents don't need to know about phases. That said, agents don't need to know about LaneSRoutes (a LANE-Frame path) because they only care about the sequence of poses and not the LANE Frame abstraction. It is expected to be just a helper class to represent a measure of progress and reduce the mapping overhead within the Route.

---

What do you think about adding a preamble in the routing namespace to introduce the different levels of granularity that agents would be benefited from considering based on their sophistication level and the requirements to explode their complexity? I think it would be required before proceeding to actually explore the full potential of this abstraction. We can leave it as a TODO and complete it once we have played with some different agents in different circumstances.

Yes, having a preamble that explains the various levels of ganularity would help. Definitely agree we need multiple levels of planning/routing. Happy to wait for the routing API to mature before adding it.

---

include/maliput/routing/route.h line 67 at r8 (raw file):

Previously, francocipollone (Franco Cipollone) wrote…

nit: is it ok? is it start of end or start or end? Sorry but maybe I am missing something

Yeah, should be "start or end".

---

include/maliput/routing/route.h line 67 at r8 (raw file):

/// - `e` indicates the end of the Route.
/// - `x` indicates the start of end of an api::LaneSRange.
/// - `*` indicates the start of end of RoutingPhase.

"of RoutingPhase" should be "of a RoutePhase".

There are several other instances of "RoutingPhase" below that should be "RoutePhase".

---

include/maliput/routing/route_phase.h line 62 at r8 (raw file):

/// methods. This is useful when they are initially placing themselves on a path
/// or for iterative querying.
class RoutePhase final {

Thoughts about shortening this name to be "Phase"?

At least for me, it is easier to say "a Route consists of a sequence of Phases" rather than "a Route consists of a sequence of RoutePhases".

The shortened name should still be clear given that it's in the "routing" namespace.

---

include/maliput/routing/router.h line 72 at r7 (raw file):

Previously, agalbachicar (Agustin Alba Chicar) wrote…

I think that it should be a different method, not the same one. That method will be able to return Routes based on a cost criteria rather than the one that minimizes it. Do you think something like:

std::vector<Route> ComputeRoutes(const api::RoadPosition& start, const api::RoadPosition& end, const RoutingConstraints& routing_constraints, const double max_cost = std::numeric_limits<double>::max()) const;

would work?

I like the method name "ComputeRoutes" but am hesitant to add another parameter named max_cost given the existence of the routing_constraints parameter. The max cost should instead be included in routing_constraints.

---

include/maliput/routing/routing_constraints.h line 44 at r5 (raw file):
Can we mention the following in the docstring?

Cost is a router implementation detail and is thus unitless.

[agalbachicar]

Reviewable status: 1 of 7 files reviewed, 13 unresolved discussions (waiting on @andrewbest-tri, @francocipollone, @liangfok, and @stonier)

---

include/maliput/routing/route.h line 67 at r8 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

"of RoutingPhase" should be "of a RoutePhase".

There are several other instances of "RoutingPhase" below that should be "RoutePhase".

Done.

---

include/maliput/routing/route.h line 108 at r8 (raw file):

Previously, francocipollone (Franco Cipollone) wrote…

offtopic: I must say it: this is real art

Thanks!

---

include/maliput/routing/route_position_result.h line 54 at r8 (raw file):

Previously, andrewbest-tri wrote…

Makes sense to me. Perhaps we just need to make sure in most cases to prefer the more extensive struct where possible in the API 👍

I have added a TODO to verify this type and the other.

---

include/maliput/routing/router.h line 72 at r7 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

I like the method name "ComputeRoutes" but am hesitant to add another parameter named max_cost given the existence of the routing_constraints parameter. The max cost should instead be included in routing_constraints.

Changed the method signature and added the maximum route cost to the RoutingConstraints struct.

---

include/maliput/routing/routing_constraints.h line 44 at r5 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Can we mention the following in the docstring?

Cost is a router implementation detail and is thus unitless.

Done.

---

include/maliput/routing/route_phase.h line 62 at r8 (raw file):

Previously, liangfok (Chien-Liang Fok) wrote…

Thoughts about shortening this name to be "Phase"?

At least for me, it is easier to say "a Route consists of a sequence of Phases" rather than "a Route consists of a sequence of RoutePhases".

The shortened name should still be clear given that it's in the "routing" namespace.

Done.

[agalbachicar]

Thanks everyone. @liangfok it's ready for another review.

Reviewable status: 1 of 7 files reviewed, 13 unresolved discussions (waiting on @andrewbest-tri, @francocipollone, @liangfok, and @stonier)

[liangfok]

Reviewed 6 of 6 files at r9, all commit messages.
Reviewable status: all files reviewed, 10 unresolved discussions (waiting on @agalbachicar, @andrewbest-tri, @francocipollone, and @stonier)

---

include/maliput/routing/route.h line 67 at r9 (raw file):

/// - `e` indicates the end of the Route.
/// - `x` indicates the start or end of an api::LaneSRange.
/// - `*` indicates the start or end of Phase.

BTW, "of Phase" should be "of a Phase".

[agalbachicar]

Thank you @liangfok for all the reviews.
@andrewbest-tri @francocipollone @stonier may I get a final review from you?

Reviewable status: 6 of 7 files reviewed, 9 unresolved discussions (waiting on @andrewbest-tri, @francocipollone, @liangfok, and @stonier)

[francocipollone]

LGTM!

[liangfok]

Reviewed 1 of 1 files at r10, all commit messages.
Reviewable status: all files reviewed, 9 unresolved discussions (waiting on @andrewbest-tri, @francocipollone, and @stonier)