detour package

Submodules

detour.clustering module

class detour.clustering.HierarchicalClusterer(distance_calculation_method='ward')

Bases: object

This class implements Hierarchical Clustering for data points represented by their features.

cluster(features_list)

Given a list of feature lists, use hierarchical clustering to obtain a tree structure (dendogram) and return its root as well as the distance matrix showing pairwise distances between nodes in vector form.

class detour.clustering.RoadClusterer(road_feature_extractor)

Bases: HierarchicalClusterer

This class implements Hierarchical Clustering for Road objects based on their features.

cluster(roads)

Given a list of roads, and a feature_extractor use hierarchical clustering to obtain a tree structure (dendogram) and return its root as well as the distance matrix showing pairwise distances between nodes in vector form.

detour.detour module

class detour.detour.DETOUR(executed_roads, not_executed_roads, road_clusterer, random_seed=0)

Bases: object

This is the main class defining DETOUR test selection/prioritization procedures.

static choose_from_selectable_subtree(root, distance_matrix, n)

Given the root of a tree of nodes that represent selectable/failing tests with pairwise distances between all n nodes in the tree given in distance_matrix, return the node representing the selectable test in the tree that is closest to a failing test.

static get_distance(distance_matrix, n, i, j)

Given a distance matrix (in vector form) showing pairwise distance between n objects, return the distance between ith and jth objects.

static get_oracle_ids(roads)

This function retrieves indices (ids for the dendogram) of roads that serve eas oracles (executed tests that are not selectable).

static is_m_closest_oracle_all_passing(roads, distance_matrix, n, oracle_ids, m, i)

This function checks if the m roads that are feature-wise closest to given road (with id i) are all not-failing (i.e., passing).

static m_closest_oracle_ids(distance_matrix, n, oracle_ids, m, i)

This function provides the indices (ids for the dendogram) of m roads that are feature-wise closest to a road with a given id i.

prioritize(select_ratio)

This method uses Retrieve functuon to prioritize roads among select_ratio ration of those that are not-executed (selectable). It works by passing the request to select method by setting min_select_ratio and max_select ratio. When those are equal, windowed selection via parameters m_closest_neighbor_count and w_selection_threshold does not apply.

static retrieve(root, distance_matrix, n)

This method chooses a leaf node of a tree of nodes that represent selectable/failing tests with pairwise distances between all n nodes in the tree given in distance_matrix. The selection procedure ensures that the selected node represents a selectable test case that has desirable properties (being close to a test that is known to be failing) and diversity is promoted through exploration via probabilistic selection of branches to choose the node from.

select(min_select_ratio=0.05, max_select_ratio=0.4, m_closest_neighbor_count=4, w_selection_threshold=4)

This method uses Retrieve function to select a number of not-executed (selectable) roads based on given parameters: min_select_ratio (number of selected roads / total not-executed (selectable) road count is at least min_select_ratio) max_select_ratio (number of selected roads / total not-executed (selectable) road count is at most max_select_ratio) m_closest_neighbor_count (m) w_selection_threshold (w) such that selection is stopped early and for each of the last w selected tests, m closest executed tests are all passing.

detour.features module

class detour.features.CurvatureBasedRoadFeatureExtractor(road_section_count)

Bases: RoadFeatureExtractor

extract_features(xvalues, yvalues)

Extract features as a concatenated list of initial orientation, together with curvature and arc length values

static reduce(kappas, arclengths, N)

Reduces given lists of kappas and arclengths to shorter versions by approximating an underlying road with a road with N number of sections.

The approximation algorithm works iteratively on the road described curvature and arc length values (kappas, arclengths) of road sections. At each iteration two road sections are selected and merged. The new road section has the curvature value set as the average curvature of the merged sections and its arclength is the sum of the merged sections. The selection is done so that after the merging the curvature of the new road (merging changes the road) is closest to the road beforehand in comparison to other merging options.

class detour.features.RoadFeatureExtractor

Bases: object

abstractmethod extract_features(xvalues, yvalues)

When (x, y) Cartesian coordinates of a road is given this method extracts features and returns them as a list of numeric values.

detour.road module

This module provides the Road class that characterizes the roads used for testing ADS. Roads are identified by an identifying object (id) that can be a unique number or a json data that includes an id. Roads have Cartesian coordinate values xvalues and yvalues. Roads can be Oracle (executed tests) or Non-Oracle (not-executed tests). Oracle, Failing: is_failing=True/False, is_selectable=False Non-Oracle: is_failing=False/None, is_selectable=True

class detour.road.Road(id, xvalues, yvalues, is_failing, is_selectable)

Bases: object

detour.roadgeometry module

detour.roadgeometry.angle_adjust(thetadiff)

Adjust a given angle difference so as to restrict it between -pi and pi radians. The procedure is described at https://rosettacode.org/wiki/Angle_difference_between_two_bearings

detour.roadgeometry.xy2ka(xs, ys)

Converts a given road from Cartesian coordinates to coordinates in Frenet frame described with curvature and arclength values as described in

Castellano, Cetinkaya, Arcaini, ‘Analysis of raod representations in search-based testing of autonomous driving systems’, in Proc. IEEE QRS, pp. 167-178, 2021 doi:10.1109/QRS54544.2021.00028.

Conversion is done from (x,y) coordinates to initial orientation together with kappa (curvature) and arclength values of road sections. The number of kappas is 2 short of the number of given coordinates. The number of pieces is 1 short of the number of given coordinates.

detour.treeutils module

This module provides functions for manipulating nodes in a tree structure.

detour.treeutils.add_info(root, roads, parent=None)

Given the root of a Tree where each node is associated with a Road object, this method adds additional information to tree nodes based on associated Road objects.

detour.treeutils.decrease_selectable_count(node)

This method decreases selectable_count values of a node and its ancestors.

detour.treeutils.get_leafs_of_tree(root)

This method returns the leafs of a tree with the given root node.

Module contents