Systems and methods for vehicular navigation

A non-transitory computer-readable medium for vehicular navigation and storing instructions that when executed by one or more processors cause the one or more processors to:

• generate a reference path for a vehicle for at least a portion of a route, wherein the reference path is a polyline including a plurality of nodes connected by line segments, the plurality of nodes including an origin node;
• store a representation of the polyline in a data structure that includes a plurality of cells, the plurality of cells corresponding, respectively, to the plurality of nodes, each cell in the plurality of cells having a corresponding index and storing contents including a signed arclength to the origin node;
• detect, based on sensor data, a plurality of obstacles ahead of the vehicle along the route;
• identify one or more obstacle gates among the plurality of obstacles using path coordinates relative to the reference path, each obstacle gate including at least one cluster of obstacles, the path coordinates of a given obstacle in the plurality of obstacles including an index corresponding to a particular cell in the plurality of cells, the signed arclength to the origin node stored in the particular cell, and a lateral offset from the reference path;
• identify one or more gaps within each of the one or more obstacle gates;
• determine an obstacle-avoidance path for the vehicle that passes through a particular one of the one or more gaps in each of the one or more obstacle gates;
• and
• control one or more aspects of operation of the vehicle based, at least in part, on the obstacle-avoidance path.

A method of vehicular navigation, the method comprising:

• generating a reference path for a vehicle for at least a portion of a route, wherein the reference path is a polyline including a plurality of nodes connected by line segments, the plurality of nodes including an origin node;
• storing a representation of the polyline in a data structure that includes a plurality of cells, the plurality of cells corresponding, respectively, to the plurality of nodes, each cell in the plurality of cells having a corresponding index and storing contents including a signed arclength to the origin node;
• detecting, based on sensor data, a plurality of obstacles ahead of the vehicle along the route;
• identifying one or more obstacle gates among the plurality of obstacles using path coordinates relative to the reference path, each obstacle gate including at least one cluster of obstacles, the path coordinates of a given obstacle in the plurality of obstacles including an index corresponding to a particular cell in the plurality of cells, the signed arclength to the origin node stored in the particular cell, and a lateral offset from the reference path;
• identifying one or more gaps within each of the one or more obstacle gates;
• determining an obstacle-avoidance path for the vehicle that passes through a particular one of the one or more gaps in each of the one or more obstacle gates;
• and
• controlling one or more aspects of operation of the vehicle based, at least in part, on the obstacle-avoidance path.