path search never ends

[moz-sec]

Checklist

• I've read the contribution guidelines.
• I've read document and no solution were found.

Step where the question is related to

Visualization

Description

Problem

I am currently trying to use CARET for my Autoware performance analysis.
When I run Architecture.search_paths() according to the CARET documentation, it exceeds 64GB of memory on my analysis environment and the path search program terminates.
I have tried to trace and analyze according to CARET Analysis for Autoware, but still have the same problem.

Expected

Path search completes within a reasonable time and memory usage.

Software Version

All source code on GitHub was retrieved and built on 2025/04/15 (commit IDs below)

• Autoware: 6cb9f1c
• CARET: 6bb7bd4

Hardware

• CPU: Intel(R) Core(TM) i9-14900KF
• RAM: 64GB
• GPU: NVIDIA RTX 4090

What I tried

Follow CARET Analysis for Autoware, after loading caret_topic_filter.bash and then trace with logging_simulator.

Once the tracing is done, I start the analysis.
I have done path finding on two programs.

1. Ran e2e_planning_to_control.py with reference to target_path.json, excluding the non-existent ROS nodes path_with_lane_id and obstacle_planner.
   → × (Path search never ends)
2. Ran e2e_sensing_to_perception.py with reference to target_path.json
   → ◯ (It takes about 10 seconds to find a path.)

I have tried several others, but the problem seems to occur when including Planning and Control ROS nodes.

The size of the trace data is as follows:

• raw data (session-{timestamp}/ust/uid/1000/64-bit): 33MB
• Converted (caret_converted): 79MB
• Architecture file (architecture.yaml): 18258 lines

Question

I heard that CARET is also used internally at Tier IV.

• When using CARET with Autoware, will the process complete without problems if Planning and Control nodes are included?
• Is there a recommended way to efficiently perform path search even when these nodes are included?

[ymski]

@moz-sec
Thanks for your question. As you pointed out, in caret_analyze, path searching is one of the operations that is not yet fully optimized in terms of time and memory efficiency.

When using CARET with Autoware, will the process complete without problems if Planning and Control nodes are included?

Yes, we have confirmed that it completes without any issues, including cases where the Planning and Control nodes are involved.
You can verify that it works as expected by running the caret_report shell script as below.

# cd to caret_report repo cloned
sh ./compare/makereport_and_compare.sh

The data used for verification is here, and the target for analysis is target_path.json.

Is there a recommended way to efficiently perform path search even when these nodes are included?

Specifying intermediate nodes in the target path enables more efficient path search. However, this is not a solution specifically targeted at nodes like Planning or Control.

If the path search does not complete, the trace data being analyzed may have characteristics that are unfavorable for caret_analyze's path search.
For example, in applications which create timer_callback repeatedly, the tool tries to search paths for each callback, which can significantly increase the processing time.

First, please try running makereport_and_compare.sh from caret_report to verify the behavior.

[moz-sec]

Thank you.
I have run makereport_and_compare.sh and confirmed that the process completes correctly.
In addition, I have prepared target.json in my environment and confirmed that the process completes without problems when measured using run.sh.

[moz-sec]

I checked the contents of add_path_to_architecture.py and noticed that it contains the following processing that I did not describe in my program. If I am wrong, I would appreciate it if you could point it out to me.

• For e2e paths, such as those containing Planning or Control, the path is divided into multiple blocks, such as path_blocks[path[]], and the path search is performed in each block before merging them later.
• Increasing the search depth from 1, and terminating the search when the path is found.
• A timeout is set in case the process does not terminate, and if no path is found within a certain period of time, the process terminates.
• The searched paths that contain loops are excluded from the list of paths.
• Unintended topic names are excluded.

[moz-sec]

When I tried to batch search in e2e as a single path instead of splitting the path like path_blocks, the path search did not finish.

I would like to ask about the following points related to this.

• What is the difference between specifying a relay node in Architecture.search_path() and calling Architecture.search_path() multiple times to search paths individually and then merging them later?
• I have confirmed that there are many loops in Planning. Is it difficult to automatically detect and eliminate them at the Architecture.search_path() stage?
• Is the need to implement such various pre-processing and post-processing on the side that calls Architecture.search_path() specific to large systems such as Autoware, and not specifically mentioned in the documentation, since such processing is unnecessary for general ROS applications?

[ymski]

What is the difference between specifying a relay node in Architecture.search_path() and calling Architecture.search_path() multiple times to search paths individually and then merging them later?

In a case where communication between nodes is defined as shown below:

graph LR
    A --> B
    B --> C
    C --> D
    D --> E
    D --> B

Loading

By dividing the nodes into blocks such as A-B-C and C-D-E, the increase in paths caused by the D -> B connection can be suppressed.

I have confirmed that there are many loops in Planning. Is it difficult to automatically detect and eliminate them at the Architecture.search_path() stage?

Since we also need to support cases where paths that include loops are intended to be analyzed, it is difficult to always remove loops from the results of Architecture.search_path().

Is the need to implement such various pre-processing and post-processing on the side that calls Architecture.search_path() specific to large systems such as Autoware, and not specifically mentioned in the documentation, since such processing is unnecessary for general ROS applications?

Since it is difficult for CARET to make assumptions about the characteristics of the system or paths to be analyzed (for example, whether to exclude paths that include loops), the documentation only describes the basic filters provided by CARET, such as filtering nodes and communications. When applying CARET to large ROS 2 systems, implementing pre-processing and post-processing suited to the characteristics of the paths you want to analyze allows Architecture.search_path() to work effectively.
If there is any additional information you would like to see in the documentation, please feel free to let us know here — we are happy to consider adding it.

If you could share the trace data where the issue is occurring, we believe it would be possible to provide more detailed advice.
We would appreciate it if you could consider this.

[moz-sec]

I may have misunderstood something basic.
As I understand it, the actual depth-first search is done in search_paths() in graph_search.py of caret_analyze.

In this method, the visited flag is used to track edges (paths that have been traversed). Therefore, I assumed that no loop would occur (i.e., the same node would not be revisited).

In reality, however, we observed several paths where the same ROS node appeared multiple times. Also, based on the previous explanation, we are certain that paths containing loops are generated.

Could you please tell me why such loops occur?
Or is it possible that the use of the visited flag is different from what I assumed?

[ymski]

In this method, the visited flag is used to track edges (paths that have been traversed). Therefore, I assumed that no loop would occur (i.e., the same node would not be revisited).

Yes, that understanding is correct. In the searching path, visited edges are managed using a visited flag, and the same edge is never selected more than once as part of a path. What’s important here is that it manages visited edges, not nodes. As long as the same edge is not selected, the same node can appear multiple times in the result.
Such cases are included in the test case. Loop path is here

[moz-sec]

Suppose the communication between nodes is defined like this:

graph LR
    A --> B
    A --> C
    D --> A
    B --> D
    C --> D

Loading

A path such as A→B→D→A→B is judged to be a loop and is prevented.
However, a path that revisits node A but passes through another edge, such as A→B→D→A→C→D, is not judged as a loop because it does not revisit the same edge.
Am I understanding this correctly?

[ymski]

In CARET, paths that include loops are allowed.
Therefore, a path like A→B→D→A→C→D can appear as a valid result.
On the other hand, if multiple visits to the same edge were allowed—as in A→B→D→A→B—it would permit paths that go through the loop repeatedly, such as A→(B→D→A)→...→(B→D→A)→C→D.
As you know, this would cause the computation to never terminate.
For this reason, during path search, each edge is allowed to be visited only once.

[moz-sec]

Here, I would like to clear up my first question.

For example, the following simple implementation of Architecture.search_paths():

arch = Architecture()
paths = arch.search_paths(
    "/planning/scenario_planning/lane_driving/behavior_planning/behavior_path_planner",
    "/planning/scenario_planning/lane_driving/behavior_planning/behavior_velocity_planner",
    "/planning/planning_validator",
)

My understanding is that this call searches all paths up to a depth of 15, not including duplicate edges (although duplicate nodes are allowed).

For example, when I ran add_path_to_architecture.py in my environment, component_planning ended up finding 457 paths up to a depth of 6.
If the search were to continue to a depth of 15, I would expect the number of paths to increase exponentially, since there would be no edge overlap, but would include node overlap.
As a result, we believe that the number of paths explored is very large, resulting in huge memory usage.

Is this understanding correct?

[ymski]

If the search were to continue to a depth of 15, I would expect the number of paths to increase exponentially, since there would be no edge overlap, but would include node overlap.
As a result, we believe that the number of paths explored is very large, resulting in huge memory usage.

Yes, your understanding is correct.
As you pointed out, when performing a path search on long paths while specifying only a small number of nodes, the process can consume a large amount of memory and may not complete.

To handle such situations, CARET provides the following options, as noted in the runtime output and documentation:

• Filtering the search targets using communication_filter and node_filter
• Specifying intermediate nodes between the start and end nodes during the search
• Setting an upper limit on the search depth

Since the path search mechanism in CARET is not fully optimized, it may cause inconvenience when analyzing large-scale systems.

[moz-sec]

I understand that in the current implementation of add_path_to_architecture.py, the path search is performed in order of shallow depth, and the search is terminated at the first path found.
Therefore, if intermediate nodes are not properly specified, there is a possibility that unintended paths may be found.
For example, when I simply performed the search, I found 8 paths at depth 3 that did not contain behavior_velocity_planner, at which point the process terminated.

{
  "name": "component_planning_2",
  "path": [
    "/planning/scenario_planning/lane_driving/behavior_planning/behavior_path_planner",
    "/planning/planning_validator"
  ]
}

However, these paths do not contain the entire component_planning ROS node that I wanted to analyze.

Against this background, is it best practice to specify some intermediate nodes, referring to the Node Diagram, etc., in order to accurately cover the intended scope?
If there is a better method elsewhere, I would be very interested in hearing about it.

I also feel that specifying intermediate nodes requires some knowledge of Autoware's configuration and internal structure.
For example, I am concerned that for someone in a position not directly developing Autoware, such as a system integrator or security engineer, it would be difficult to properly select an intermediate node, which would be a hurdle to analysis.
What are your thoughts on this point?

[ymski]

Against this background, is it best practice to specify some intermediate nodes, referring to the Node Diagram, etc., in order to accurately cover the intended scope?
If there is a better method elsewhere, I would be very interested in hearing about it.

As you mentioned, specifying intermediate nodes by referring to the Node Diagram and similar resources is currently the best practice.

I also feel that specifying intermediate nodes requires some knowledge of Autoware's configuration and internal structure.
For example, I am concerned that for someone in a position not directly developing Autoware, such as a system integrator or security engineer, it would be difficult to properly select an intermediate node, which would be a hurdle to analysis.
What are your thoughts on this point?

I agree that analysis can be difficult without sufficient knowledge of Autoware's structure.
When performing analysis, a minimum understanding of the target system is necessary, and in the case of using CARET, this includes understanding the node structure.
We would like to support analysis even when the internal structure is not well understood, but at this point, we do not have a concrete solution for that.