February 18, 2021 • 4 min read

Routing Sidewalk Robots: Intro (Part 1)

Today, many tech companies are developing autonomous sidewalk delivery robots – a marriage between the burgeoning self-driving and delivery industries. Routing a sidewalk bot, however, comes with several unique challenges. Firstly, robots cannot simply travel anywhere pedestrians can — perhaps a path is impassable because a crosswalk is under construction or because a restaurant’s outdoor dining makes a sidewalk too busy. Furthermore, each specific delivery bot has its own capabilities and limitations. For example, some bots on wheels may not be able to traverse intersections without curb ramps. Clearly, routing a sidewalk bot from Point A to Point B requires customizable, constraint-based routing, which is the foundation of our routing engine at rideOS.

 

This blog series will discuss how we've tackled the challenge of bringing our efficient, customizable routing for on-road vehicles to sidewalk robots as well. Here in Part 1, we’ll introduce why constraint-based sidewalk routing is a unique challenge that requires a different basemap than the one we currently use for on-road vehicles. In later parts of the series, we’ll go into more implementation details on how we created the new sidewalk basemap and how we’ve extended our constraints and Map Annotations API to work with this use-case.

 

As a sneak-peek, here’s a visual of our sidewalk routing in action:

 

Our routing engine can now compute optimal routes for robots along sidewalks and crosswalks

 

Why do sidewalk bots and on-road vehicles require different basemaps?

Let’s start with defining what a basemap is. When it comes to routing on-road vehicles, the basemap is our representation of the road network as a graph of nodes and edges, where nodes represent intersections and edges represent roads connecting intersections. The basemap is the basis on which we search for optimal routes and apply constraints.

 

Unfortunately, the basemap that we use for on-road vehicles is insufficient for routing and applying constraints to sidewalk bots, as we’ll see below.

 

Differences in Routing

To understand some of the differences between routing an on-road vehicle and a sidewalk bot, here’s an example of how their optimal routes might differ for the same pickup and dropoff locations.

 

sidewalk-bots-0 (1)

An optimal route for an on-road vehicle following right-hand traffic rules can be very different from an optimal route for a sidewalk bot

 

As you can see, routing is extremely different between the two– one reason being that on-road vehicles must follow the direction of the road, whereas sidewalk bots can travel either way along a single sidewalk (because sidewalks are inherently bidirectional). To properly compute optimal routes for sidewalk bots, we needed to develop a new basemap that properly captured the idiosyncrasies of sidewalk routing.

 

Differences in Constraints

Aside from the actual routing, sidewalk bots also added complexity to our constraints system. To understand why constraining sidewalk bots might be different than constraining on-road vehicles, imagine an intersection with two curbs that are impassable for sidewalk bots, perhaps because there are no curb ramps:

 

Two impassable curbs for sidewalk bots are depicted in orange

 

In this scenario, users might want to constrain their sidewalk bots from making the following left turns, since the curbs are impassable:

 

Because of the impassable curbs, users would want their sidewalk bots to avoid taking the routes marked in red

 

Using our constraints system for on-road vehicles, if users wanted to prevent their fleets from making these left turns, they might try to create an “avoid left turn” constraint at this intersection:

 

Users could create an “avoid left turn” constraint at this intersection which would prohibit all left turns for vehicles. The constraint is displayed on the road, since previously constraints could only be applied to our on-road vehicle basemap

 

Although this “avoid left turn” constraint might be appropriate for on-road vehicles, it is overly restrictive for the sidewalk use-case. Sidewalk bots are actually able to make some left turns at this intersection, just as long as they don’t use either of the impassable curbs. For example, they can make either of the left turns which start on the other side of the street:

 

The two left turns starting on the other side of the street should be allowed for sidewalk bots, but would be prohibited by the “avoid left turn” constraint for on-road vehicles shown previously.

 

Thus, we needed the ability to constrain specific crosswalks, rather than entire turns, which would cause our routing engine to correctly avoid the impassable curbs without unnecessarily restricting valid parts and turns in the intersection. In order to do this, we needed a basemap that actually included the concept of “crosswalks”– something the basemap for on-road vehicles doesn’t have.

 

We needed a basemap that would allow us to add specific crosswalk restrictions, rather than general turn restrictions, in order to correctly model the expected sidewalk routing behavior

 

Summary

In Part 1 of Routing Sidewalk Robots, we hoped to demonstrate some of the reasons why our basemap for on-road vehicles was insufficient for handling constraint-based sidewalk routing. To support the sidewalk use-case, we needed a new basemap that specifically included sidewalks and crosswalks upon which we could route and apply constraints. Next up, we’ll share how we actually generate this new sidewalk basemap.

 

If you’re interested in learning more about our customizable sidewalk routing or think it could be useful to your business, feel free to contact us!