maliput / maliput/maliput_object
More performant ObjectQuery's implementation
Nobody has claimed this yet.
- Dominant language
- C++
- Stars
- 0
- Forks
- 0
- PR merge metrics
- No merged PRs in 30d
Description
### Context
`maliput::object::SimpleObjectQuery` complies with the ObjectQuery API however its underlying implementation may not be as performant as desired.
The bottleneck happens when querying maliput by using methods like `maliput::api::RoadGeometry::FindRoadPositions`(or `ToRoadPosition`). The implementations of these methods are full responsibility of the backend, and so, maliput_object's performance is directly affected by the maliput backend that is being used.
When using `maliput_malidrive` backend, how the `SimpleObjectQuery` implementation performs, is directly affected by the number of lanes of the RoadNetwork as the implementation uses brute force when finding the lanes via FindRoadPosition.
#### Some time measurements.
```
Number of lanes in the TShapeRoad: 12
maliput_query --xodr_file_path=TShapeRoad.xodr --omit_nondrivable_lanes -- FindOverlappingLanesIn intersected 5 5 5 15 15 0 0 0 0
>> Elapsed Query Time: 0.00292117 s
```
```
Number of lanes in the Town01: 202
maliput_query --xodr_file_path=Town01.xodr --omit_nondrivable_lanes -- FindOverlappingLanesIn intersected 5 5 5 15 15 0 0 0 0
>> Elapsed Query Time: 0.0733985 s
```
```
Number of lanes in the Town07: 754
maliput_query --xodr_file_path=Town07.xodr --omit_nondrivable_lanes -- FindOverlappingLanesIn intersected 5 5 5 15 15 0 0 0 0
>> Elapsed Query Time: 0.291728 s
```
### Proposal
We could detach from the maliput backend implementation's performance by proposing a re-organization of the `RoadNetwork` space into a convenient space-partitioning data structure (like kdtree).
Therefore we could create a layer on top of maliput, to reorganize the space and provide FindRoadPositions methods like that can be used later on by this new ObjectQuery implementation.
```mermaid
graph TD;
maliput_object-->maliput_kdtree;
maliput_kdtree-->maliput;
maliput-->maliput_malidrive;
maliput-->maliput_multilane;
maliput-->maliput_dragway;
maliput-->maliput_****;
```
### Suggested Steps for designing
- [ ] Define the requirements/constraints for the `maliput_kdtree` layer/package.
- [ ] Should it be part of `maliput` package? (I guess answer of this will be directly connected to whether which kdtree implementation is going to be used (third-library or homemade)
- [ ] Which methods are expected to provide? Thinking about how is it going to be consumed by the ObjectQuery's implementation. (plus other we consider interesting to have)
- [ ] Define the requirements/constraints for the `kdtree` implementation:
- [ ] Which are the queries we should provide to fulfill `maliput_kdtree` necessities. (closest neighbor, etc)
- [ ] Third library or homemade?
Our space will be static (once the roadnetwork is created there aren't expected modifications.)
_Note: This issue's description is expected to be iterated if needed_
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with maliput::object::SimpleObjectQuery and the maliput::api::RoadGeometry::FindRoadPositions and ToRoadPosition entry points. Review the maliput_query measurements for TShapeRoad, Town01, and Town07, then define requirements for the proposed maliput_kdtree layer and its static-space k-d tree implementation. Done means the package boundary, supported queries, and implementation approach are agreed.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- backend-api-design, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100