maps package

Overview

Imagine the diffculty in driving in a new city without the help of a maps service on your phone or car. Even for experienced cab drivers, it is often diffcult to navigate through city traffic, so let us not even discuss the plight of rookie drivers. It is easy to understand that modeling maps is central to the effectiveness of any simulation software. Self-driving start-ups are investing heavily in developing HD maps that explain the fine details of the environment around the vehicle. Putting it simply, the more realistic the maps look, the better the software.

Similarly, modeling maps is central to the effectiveness of CATS. The most important requirements/features of maps are:

• Maps should represent an urban traffic scenario, along with the landscape of the city
• Maps require a detailed modeling of roads, intersections, lanes, etc
• Maps should encode the topological connections between roads, for routing
• Specific to CATS, maps also store the spatial details of all the vehicles in the simulation.

maps.map module

class core.lib.maps.map.Intersection(point_x, point_y, osmid=None, traffic_controller=None)

Characterizes a traffic junction.

Note

An intersection contains multiple Nodes which are the end points of the roads leading up to the intersection. An intersection is initialized with 0 Nodes. Nodes are added later while initializing a map using add_node method. The present implementation assumes the following.

• Fixed number of nodes. Currently only support a ‘+’ kind of intersection (a four way junction)
• Intersections are axis aligned.

__x

float – x coordinate

__y

float – y coordinate

__grade

float – altitude

__osmid

int – unique identifier of the Intersection

__traffic_controller

object – TrafficController on the Intersection

__nodes

list – list of Node objects

Todo

• Extend to dynamically create an intersection with variable number of roads coming in (different shapes)

add_node(node)

Adds node object to an Intersection instance.

Parameters:node (object) – node object

get_grade()

Getter method for __grade attribute.

get_nodes()

Getter method for __nodes attribute.

get_osmid()

Getter method for __osmid attribute.

get_x()

Getter method for __x attribute.

get_y()

Getter method for __y attribute.

class core.lib.maps.map.Lane(lane_no, road, lane_polygon, lane_center, speed_limit=None, _type=None)

Characterizes a lane that is a part of a Road.

Note

• Current Implementation (to be deprecated): Provides the bare minimum information such as lane_center (used to calculated distance from lane center), lane_no, speed_limit etc. Has no particularly important role other than the attributes defined.
• Future Implementation (under development): The vehicles are store on the lanes. If a vehicle changes a lane, a method on lanes is called to update the vehicles on the source lane and the destination lane. The vehicles on a lane are stored in a linked list in decreasing order of distance from the end of the road.

__vehicles

list – list of vehicle objects

__lane_no

int – lane_no is calculated from 0 (center of road, i.e. left most lane)

__lane_type

str – type of lane (turn only etc)

__road

object – Road of which the lane is a part of

__lane_polygon

object – Shapely bounding polygon of the lane

__lane_center

object – Shapely LineString object of the lane_center

__speed_limit

float – speed limit of the road

__name

str – name oft he lane

__start_x

float – x coordinate of the start of the lane center

__start_y

float – y coordinate of the start of the lane center

__end_x

float – x coordinate of the end of the lane center

__end_y

float – y coordinate of the end of the lane center

remove_vehicle(vehicle)

Note

Not used currently. To be used in the future

Parameters:vehicle (object) – Vehicle that needs to be removed from the lane Raises:ValueError – Vehicle not found in the lane

class core.lib.maps.map.Node(point_x, point_y, incoming, _id=None, parent=None, traffic_signal=None)

Class determining the data structure of a Node (end points of a Road).

Note

This class is similar to a (class) SubNode, except that (class) Node is an endpoint of a (class) Road and usually is a bound to (class) Intersection.

__x

float – x coordinate

__y

float – y coordinate

__grade

float – altitude

__parent

class – Intersection of which the node is a part of

__id

int – identifier of the Node

__traffic_signals

object – Traffic Signal on the node (if any)

__incoming

bool – If the Node ends at an intersection (it is incoming into the intersection)

id

Getter method for __id attribute.

parent

Getter method for __parent attribute.

traffic_signals

Getter method for __traffic_signals attribute.

x

Getter method for __x attribute.

y

Getter method for __y attribute.

class core.lib.maps.map.Road(start_node, end_node, line_string, _type='straight', no_of_lanes=3, name=None, osmid=None, lane_width=5, speed_limit=40)

Characterizes the Road in a TrafficGraph.

The Road is determined by a start node, an end node, a RoadString (for the curvature/ linestring). It has attributes like speed limit, number of lanes etc that are specified while constructing the Road, and attributes like width, polygons that are calculated.

Note

There are two types of roads:

• Normal road that connects two nodes (which are on two different intersections),
• Turn road that connects two nodes within the same intersection.

They are simulated on a micro scale within an intersection (traffic junction which is usually at least 20 meters in diameter). By considering two types of roads, there are several edge cases on the vehicle class that need to be taken care of when trying to update the state of the vehicle. Also, the current implementation is only for a plus shaped intersection, but when there are various types of intersections, care must be taken in assigning the turn roads.

__start_node

object – start_node

__end_node

object – end_node

__type

str – _type

__speed_limit

float – speed limit of the road

__line_string

object – Shapely LineString of the center of the road

__name

str – name of the road

__osmid

int – unique identifier of the Road

__no_of_lanes

int – no_of_lanes

__lane_width

float – lane_width

__left_line_string

object – Shapely LineString of the left edge of the road.

__left_line_string_x

list ? – x coords of the left LineSting

__left_line_string_y

list ? – y coords of the left LineString

__road_string

object – RoadString that determines the curvature, heading of the road

__length

float – length of the road (measured along the line string)

__width

float – no_of_lanes* lane_width

__lanes

list – list of the Lanes on the Road

__heading

list – list of the headings across difference segments in the RoadString

__traffic_count

int – number of vehicles on the road

__traffic_trace

dict – history of traffic attributes on the road

__lane_wise_traffic

dict – traffic attributes

__total_traffic

dict – traffic attributes

__time

float – estimated travel time along a road (determined by the speed limit)

__avg_time

float – estimated travel time along a road (average of the time taken by the traffic on that road)

__val

int

__min_bounding_box

object – Shapely Polygon of the axis aligned polygon of the Road

__bounding_polygon

object – Shapely Polygon of the Road (the actual polygon, which fits the edges)

bounding_polygon

It is a Shapely.Polygon object that defines the bounds of the road.

Note

The current implementation only considers straight roads (roads which are not curved). Future implementations must modify this method to take the curvature/turns into consideration. Note that the return type also changes when curved roads are considered.

Returns:a list of the points of the polygon Return type:list

get_distance_from_road_center(x, y)

Calculates the distance from the center of the road using the __line_string.

Parameters:

• x (float) – x coordinate
• y (float) – y coordinate

Returns:

distance from the center of the Road

Return type:

float

get_lane(x, y, segment=0)

Calculates the lane number of the vehicle by taking its coordinates (x,y). The distance from the left edge of the road is calculated and divided by the lane width to find the lane number.

Note

When curved roads are implemented in the future, this method does not have to change much. If the __left_line_string attribute is modified for curved roads, this method only needs to use the segment number and calculate the distance (by using the line string in that segment).

Parameters:

• x (float) – x coordinate of the vehicle
• y (float) – y coordinate of the vehicle
• segment (int) – optional (for now, until this method is updated for curved roads)

Returns:

lane number calculated

Return type:

int

reset_traffic()

Assigns the traffic attributes to the class Attributes at the end of the time interval and resets the traffic attributes.

Note

Future research may include a time series data of the traffic attributes.

update_traffic_from_vehicle_data(velocity)

Does the job of a loop detector by updating the attributes of the traffic, like number of vehicles, average velocity etc. This update is done one vehicle at a time. Each vehicle, after updating its states, calls this method to update the attributes of the road on which it is travelling.

Parameters:velocity (float) – velocity of the vehicle calling this method

class core.lib.maps.map.RoadString(line_string)

Encapsulates all the information about the road.

__sub_nodes

list – list of SubNode objects at points on the linestring

__no_sub_nodes

int – number of subnodes in the linestring

__segment_headings

list – list of heading angle from one SubNode on the line string to the next SubNode

__perpendicular_segments

list – list of lines perpendicular to the line joining two adjacent SubNodes

__length_segments

list – list of lengths of segments joining two adjacent SubNodes

static get_perpendicular_segment(theta1, theta2, point)

Calculates equation of a line passing through a point with slope as an average of two slopes.

Parameters:

• theta1 (float) – angle in radians
• theta2 (float) – angle in radians
• point (tuple) – (x,y) coordinates of the point

Returns:

(1, -slope, -intercept) where the equation of line is y + slope * x + intercept = 0

Return type:

tuple

line_string

Getter method for __line_string attribute.

no_sub_nodes

Getter method for __no_sub_nodes attribute.

perpendicular_segments

Getter method for __perpendicular_segments attribute.

segment_headings

Getter method for __segment_headings attribute.

segment_lengths

Getter method for __length_segments attribute.

set_attributes(line_string)

Calculates all the information of the road from the given line string.

Parameters:line_string (shapely LineString) – of the road

subnodes

Getter method for __sub_nodes attribute.

class core.lib.maps.map.SubNode(point_x, point_y)

Characterizes points of a line string along a curved road.

__x

float – x coordinate

__y

float – y coordinate

get_grade()

Getter method for __grade attribute.

set_grade(g)

Sets the value of __grade attribute.

Parameters:g (float) – value of __grade attribute

set_x(x)

Sets the value of __x attribute.

Parameters:x (float) – value of __x attribute

set_y(y)

Sets the value of __y attribute.

Parameters:y (float) – value of __y attribute

x

Getter method for __x attribute.

y

Getter method for __y attribute.

class core.lib.maps.map.TrafficGraph(simulation)

Comprises of and defines the topological connections between the other classes defined in map module.

TrafficGraph defines the landscape, the connections between roads, and everything related to the map used in the simulation. TrafficGraph currently uses a graph data structure to store the topological connections, and an rtree data structure to store the spatial information related to the static objects (nodes, intersections, roads) and mobile objects (such as the vehicles).

__graph

object – a networkx graph object

_simulation

object – simulation object that uses the trafficgraph

__intersections_table

dict – a dictionary of the intersections defined in the trafficgraph

__intersections_count

int – len of the __intersections_table

__sources

list – list of the nodes in the graph that have 0 incoming edges

__sinks

list – list of the nodes in the graph that have 0 outgoing edges

__nodes_count

int – number of nodes in the graph

__roads_count

int

__roads_table

dict()

__roads_tree

index.Index()

__roads_tree.interleaved

True

__vehicles_count

0

__vehicles_table

{}

__vehicles_tree

index.Index()

__vehicles_tree.interleaved

True

add_vehicle(vehicle)

Takes a vehicle object and adds it to the traffic graph.

Parameters:vehicle (object) – vehicle object to be added (not the id)

create_sample_network()

Creates a default network (or chooses from among a set of default networks).

Note

Must include a GUI support to enable a user to create a network on the fly by dragging and dropping

get_all_nodes(objects=True)

Returns all the nodes stored in the graph.

Parameters:objects (bool) – If objects are yielded or object ids Yields:object – Nodes in the graph

get_all_vehicles()

Returns a list of all the vehicle objects.

Returns:a list of all the vehicle objects Return type:list

get_edge_attributes(edge)

Returns a Road object.

Parameters:edge (tuple) – [start node id, end node id] Returns:Road object Return type:object

get_edges()

Returns a EdgeView containing edge. For attributes call getEdgeAttr(edge)

Returns:a list of edge objects Return type:list

get_incoming_edges(node)

Returns a list of edges that come into the give node.

Parameters:node (int) – id of the node Returns:list of edges (which is a tuple of nodes) that come into the given node Return type:list

get_nearest_nodes(bounding_box, number, generator=True, objects=False)

Returns the give number of nodes closest to a bounding box.

Parameters:

• bounding_box (tuple) – axis aligned bounding box coordinates (xmin, ymin, xmax, ymax)
• number (int) – number of required nodes
• generator (bool) – If the output should be a generator
• objects (bool) – If the output should be node ids or objects

Returns:

(or generator) of the given number of nodes closest to a bounding box ordered by distance

Return type:

list

References

http://toblerity.org/rtree/tutorial.html

get_nearest_vehicles(bounding_box, number, generator=True, objects=False)

Returns the vehicles in a given axis aligned bounding box.

Parameters:

• bounding_box (tuple) – axis aligned bounding box coordinates (xmin, ymin, xmax, ymax)
• number (int) – number of required vehicles
• generator (bool) – If the output should be a generator
• objects (bool) – If the output should be vehicle ids or objects

Returns:

(or generator) of the given number of vehicles closest to a bounding box ordered by distance

Return type:

list

References

http://toblerity.org/rtree/tutorial.html

get_node_attribute(node)

Returns a node object given an id.

Parameters:node (int) – id of the node Returns:Node object Return type:object

get_nodes_by_bounding_box(bounding_box, generator=True, objects=False)

Returns the nodes in a given axis aligned bounding box.

Parameters:

• bounding_box (tuple) – axis aligned bounding box coordinates (xmin, ymin, xmax, ymax)
• generator (bool) – If the output should be a generator
• objects (bool) – If the output should be node ids or objects

Returns:

(or generator) of the nodes closest to a bounding box ordered by distance

Return type:

list

References

http://toblerity.org/rtree/tutorial.html

get_out_edges(node)

Returns a list of edges that come out of the given node.

Parameters:node (int) – id of the node Returns:list of edges (which is a tuple of nodes) that come out of the given node Return type:list

get_road(edge)

Returns Road object on the given edge.

Parameters:edge (tuple) – [start node id, end node id] Returns:Road object Return type:object

get_roads()

Returns a list of Road objects.

Returns:[start node id, end node id, road object] Return type:list

get_shortest_path(source, destination, weight='distance')

Returns the shortest path from source to destination.

Parameters:

• source (int) – source node id
• destination (int) – destination node id
• weight (str) – parameters based on which the cost is calculated

Returns:

a list of the node ids along the shortest path from the source to the destination

Return type:

list

get_sinks()

Returns:a list of Node objects with zero outgoing edges Return type:list

get_sources()

Returns:a list of Node objects with 0 incoming edges Return type:list

get_vehicle(vehicle_id)

Returns the vehicle object with the given id in the __vehicles_table.

Parameters:vehicle_id (int) – vehicle id to be retrieved Returns:Vehicle object with the given vehicle_id Return type:object

get_vehicles()

Yields the vehicle object from the __vehicles_table.

Yields:object – Vehicle object

get_vehicles_by_bounding_box(bounding_box, generator=False, objects=False)

Returns the vehicles in a given axis aligned bounding box.

Parameters:

• bounding_box (tuple) – axis aligned bounding box coordinates (xmin, ymin, xmax, ymax)
• generator (bool) – If the output should be a generator
• objects (bool) – If the output should be vehicle ids or objects

Returns:

(or generator) of the given number of vehicles closest to a bounding box ordered by distance

Return type:

list

References

http://toblerity.org/rtree/tutorial.html

remove_vehicle(vehicle)

Removes the given vehicle id from the __vehicles_table.

Parameters:vehicle (int) – vehicle id to be deleted

update_road_attributes(road)

Updates the Road object.

Parameters:road (list) – [start_node_id, end_node_id, road_object] Returns:estimated average time to travel on the road Return type:float

update_vehicle_network()

Deletes the rtree and re initializes it using the self.vehicle_generator() method using bulk upload. This method of bulk upload of all the vehicles at the end of a time interval is preferred as compared to updating it after each vehicle’s update.

vehicle_generator()

Yields:tuple – (id, (x,y,x,y)) id of vehicle and coordinates of vehicle

core.lib.maps.map.add_intersections_to_graph(graph, intersections_table)

Iterates over the intersections and adds nodes to the graph, and create edges (Roads) from nodes that are connected. This piece of code assumes the simple plus shaped intersections, and the turn_links variable is based on this assumption.

Note

Future implementations must consider various shapes of intersections and different combinations of turn roads to be added to the intersection.

Parameters:

• graph (object) – Networkx graph object
• intersections_table (dict) – dict containing the intersection objects

Returns:

Graph object

Return type:

object

core.lib.maps.map.build_sample_network()

Builds a simple grid like network with + shaped intersections.

Returns:graph object, intersections table Return type:tuple

core.lib.maps.map.create_plus_intersection(point_x, point_y, counter, scale=12, traffic_controller=True)

Creates a + shaped intersection and instantiates nodes (in a fixed fashion).

Note

Future implementations must include methods to create arbitrary (shaped/sized) intersections.

Parameters:

• point_x (float) – x coordinate
• point_y (float) – y coordinate
• counter (int) – used to number the nodes (node ids)
• scale (int) – scaling factor of the coordinates (since the nodes are placed here wrt distance from intersection)
• traffic_controller (object) – traffic controller on the intersection

Returns:

Intersection object, and counter number (used to sync the node ids on the graph)

Return type:

tuple

core.lib.maps.map.get_grade(x, y)

Determines the landscape of the region under the map.

This method is determined by a smooth function, and returns the function value evaluated at the input location. The function must have subtle variations in the grade with relative changes in x and y. This function is now external to the map, but later it can be integrated into the TrafficGraph class.

Parameters:

• x (float) – x coordinate
• y (float) – y coordinate

Returns:

grade of the (x,y) coordinate

Return type:

float

Todo

• Determine a 2-D function which maps to the grade (altitude) of a given point.

core.lib.maps.map.polygon_from_linestring(linestring, width_from_center)

Generates a polygon object around the given line string with the given width from center.

Parameters:

• linestring (object) – Shapely LineString object
• width_from_center (float) – distance from the center to either sides (Edges) of the polygon

Returns:

Shapely Polygon object

Return type:

object