Pre-computation of kinematically feasible roadmaps

A computing device, comprising:

• one or more processors;
• and
• data storage including at least computer-executable instructions stored thereon that, when executed by the one or more processors, cause the computing device to perform functions comprising:
• determining a roadmap comprising a path associated with a starting pose and an ending pose, the path to be traversed by a robotic device in an environment;
• generating a plurality of trajectories from the starting pose, wherein each trajectory of the plurality of trajectories comprises a different sampled pair of steering position and traction velocity values for the robotic device to maintain during a planning time interval, wherein the planning time interval is a predetermined duration of time;
• for each trajectory of the plurality of trajectories, determining a score for the trajectory indicative of advancement from the starting pose toward the ending pose by simulating the steering position and traction velocity values for the planning time interval, wherein simulating the steering position and traction velocity values for the planning time interval comprises determining a later pose for the robotic device that starts at the starting pose and travels during the planning time interval while maintaining the steering position and traction velocity values for the trajectory;
• selecting a nominal trajectory from among the scored plurality of trajectories;
• storing the nominal trajectory with the roadmap;
• receiving a first request to provide a route through the environment;
• and
• sending a first response to the first request, the first response comprising a portion of the roadmap, wherein the portion of the roadmap includes the stored nominal trajectory.

A non-transitory computer readable medium having stored thereon instructions, that when executed by one or more processors of a computing device, cause the computing device to perform functions comprising:

• determining a roadmap comprising a path associated with a starting pose and an ending pose, the path to be traversed by a robotic device in an environment;
• generating a plurality of trajectories from the starting pose, wherein each trajectory of the plurality of trajectories comprises a different sampled pair of steering position and traction velocity values for the robotic device to maintain during a planning time interval, wherein the planning time interval is a predetermined duration of time;
• for each trajectory of the plurality of trajectories, determining a score for the trajectory indicative of advancement from the starting pose toward the ending pose by simulating the steering position and traction velocity values for the planning time interval, wherein simulating the steering position and traction velocity values for the planning time interval comprises determining a later pose for the robotic device that starts at the starting pose and travels during the planning time interval while maintaining the steering position and traction velocity values for the trajectory;
• selecting a nominal trajectory from among the scored plurality of trajectories;
• storing the nominal trajectory with the roadmap;
• receiving a first request to provide a route through the environment;
• and
• sending a first response to the first request, the first response comprising a portion of the roadmap, wherein the portion of the roadmap includes the stored nominal trajectory.