Patent ID: 12222723

Like reference symbols in the various drawings indicate like elements.

DETAILED DESCRIPTION

To navigate about environments, mobile robots may use some degree of mapping. Maps may contain stored information that informs the robot as to details about an environment.

One type of map for navigation is a topological map, which is a diagram abstracting an area to be represented by a particular type (or subset) of information about the area. For example, with only a particular type or subset of information about an area, a topological map defines the area relationally using the particular information. For instance, a topological map represents a set of places by the relationship between these places. In this respect, a topological map may lack scale or other detailed metric data, such as distance and direction, while maintaining a relationship between points or places. One such example of a topological map is a map of a train line where the map depicts the train's route as a series of connected stops without further precise details such as the distance between stops.

Another form of a map representation is referred to as a metric map. Metric maps are derived from a more precise mapping framework when compared to topological maps. Metric maps represent locations of objects (e.g., obstacles) in an environment based on precise geometric coordinates (e.g., two-dimensional coordinates or three-dimensional coordinates). In order to effectively navigate a robot with a metric map, a robot typically operates with data indicating the robot's coordinate location with some degree of precision. Such data allows determination of the robot's relationship to other objects represented according to geometric coordinates.

Since metric maps represent objects according to detailed spatial information (e.g., geometric coordinates), metric maps may be inherently computationally expensive. For example, generally the more detail present in a map, the greater the number of computational units used for computing operations on the map (e.g., read, write, and/or storage operations). Therefore, when a robot performs navigational processes using the metric map (e.g., querying the metric map for information to make navigation decisions), these processes may demand greater computing resources or take a longer time to occur when compared to navigational processes using a topological map. Topological maps may have this advantage because generally, by diagraming only particular relationships, a topological map includes less information compared to more detailed maps (i.e., metric maps).

With topological maps being typically less computationally expensive than metric maps, it is desirable to employ topological maps as much as possible for robotic navigation. Unfortunately, during navigation, situations may arise where topological maps do not provide enough detailed information to guide the robot successfully to a specific destination.

One such situation that may occur during robotic navigation is that the robot encounters an object that obstructs the robot (referred to as an obstacle) in some unforeseeable way. When an unforeseeable obstacle occurs, a topological map that has abstracted the environment to a set of locations and a relationship among these locations is ill-equipped to provide the robot with a path that avoids the obstacle while continuing to a specific destination. In other words, the presence of an unforeseeable obstacle may break or interfere with the relationship between the set of locations represented in a topological map. Without further detailed information to guide the robot, such a broken relationship may cause the robot to fail to achieve navigation to a target destination using the topological map.

The situation with an unforeseeable obstacle is not uncommon because real-world environments are dynamically changing. That is, structures or objects within an environment may have some temporary or nonpermanent nature. Known obstacles may move and new obstacles may be introduced to the environment. For instance, if the environment for the robot is a construction site, a construction site is a changing environment often including temporary or non-permanent objects, such as tools, tool storage, machinery, material, etc. Dynamic changes (or changes over time) to an environment pose an issue for a robot deployed to perform some task within the dynamically changing environment. This may be especially true when the robot operates autonomously or semi-autonomously.

For localization and navigation purposes, a robot can be initially taught an environment by a mapping process. In one example of a mapping process, an operator of the robot initially guides the robot through the environment while collecting sensor data from sensors associated with the robot. The sensor data (e.g., image data or point cloud data) gathered during this initial mapping process allows the robot to construct a map of the environment. For example, the initial mapping process generates a topological map of locations recorded during the initial mapping process and the relationship between these locations to inform the robot how to navigate along a path from location to location.

When the robot proceeds to use a topological map for navigation in the mapped environment, an obstacle not recognized or discovered during the initial mapping process is an unforeseeable object that will not be accounted for in the topological map. Therefore, if the robot only navigates using a navigation route from the topological map, an unforeseeable object encountered by the robot will hinder (or even entirely prevent) complete execution of the navigation route.

To address some of these issues, the mobile robot may use a directed exploration approach for its navigation system. A directed exploration approach functions as a type of hybrid navigation system that utilizes both a topological map and a more detailed metric map. For instance, during navigation, a topological map guides the robot unless or until the robot encounters an unforeseeable obstacle. Here, once the robot encounters the unforeseeable obstacle, the navigation system then switches temporarily to a local navigation map to determine if the robot can find a path that temporarily deviates from the navigation route of the topological map to avoid the obstacle and enables the robot to resume some portion of the navigation route (e.g., to travel to a destination specified by the navigation route).

For example, while the robot moves along a navigation route, the robot may be generating a local obstacle map for an area immediately surrounding the robot (e.g., generates a grid of some size adjacent to the robot). In this example, when the robot encounters an unforeseeable obstacle that impedes the navigation path, the robot uses the local obstacle map to determine a path that avoids the obstacle and continues the robot on the navigation route. By generating an obstacle avoidance path with the local obstacle map that merges with the original navigation path, the navigation system may once again guide the robot with the navigation path from the topological map instead of continuing to use (e.g., exclusively or predominantly) the local obstacle map after avoidance of the unforeseeable obstacle. This directed exploration approach may therefore minimize the computing cost associated with the navigation system.

Referring to example ofFIGS.1A and1B, the robot100includes a body110with one or more locomotion-based structures (locomotion structures) such as legs120a-dcoupled to the body110that enable the robot100to move within the environment10. In some examples, each leg120is an articulable structure such that one or more joints J permit members122of the leg120to move. For instance, each leg120includes a hip joint JH(for example, JHband JHdinFIG.1A) coupling an upper member122,122Uof the leg120to the body110and a knee joint JK(for example, JKa, JKb, JKc, and JKdinFIG.1A) coupling the upper member122Uof the leg120to a lower member122Lof the leg120. AlthoughFIG.1Adepicts a quadruped robot with four legs120a-d, the robot100may include any number of legs or other locomotion structures (e.g., a biped or humanoid robot with two legs, or other arrangements of one or more legs) that provide a means to traverse the terrain within the environment10.

In order to traverse the terrain, each leg120has a distal end124that contacts a surface of the terrain (i.e., a traction surface). In other words, the distal end124of the leg120is the end of the leg120used by the robot100to pivot, plant, or generally provide traction during movement of the robot100. For example, the distal end124of a leg120corresponds to a foot of the robot100. In some examples, though not shown, the distal end124of the leg120includes an ankle joint such that the distal end124is articulable with respect to the lower member122Lof the leg120.

In the examples shown, the robot100includes an arm126that functions as a robotic manipulator. The arm126may be configured to move about multiple degrees of freedom in order to engage elements of the environment10(e.g., objects within the environment10). In some examples, the arm126includes one or more members128, where the members128are coupled by arm joints JA(for example, JA1, JA2, JA3, JA4, JA5, and JA6inFIG.1A) such that the arm126may pivot or rotate about the joint(s) JA. For instance, with more than one member128, the arm126may be configured to extend or to retract. To illustrate an example,FIG.1Adepicts the arm126with three members128corresponding to a lower member128L, an upper member128U, and a hand member128H(e.g., also referred to as an end-effector128H). Here, the lower member128Lmay rotate or pivot about one or more arm joints JAlocated adjacent to the body110(e.g., where the arm126connects to the body110of the robot100). For example,FIG.1Adepicts the arm126able to rotate about a first arm joint JA1or yaw arm joint. With a yaw arm joint, the arm126is able to rotate in 360 degrees (or some portion thereof) axially about a vertical gravitational axis (e.g., shown as Az) of the robot100. The lower member128Lmay pivot (e.g., while rotating) about a second arm joint JA2. For instance, the second arm joint JA2(shown adjacent the body110of the robot100) allows the arm126to pitch to a particular angle (e.g., raising or lowering one or more members128of the arm126). The lower member128Lis coupled to the upper member128Uat a third arm joint JA3and the upper member128Uis coupled to the hand member128Hat a fourth arm joint JA4.

In some examples, such asFIG.1A, the hand member128Hor end-effector128His a mechanical gripper that includes a one or more moveable jaws configured to perform different types of grasping of elements within the environment10. In the example shown, the end-effector128Hincludes a fixed first jaw and a moveable second jaw that grasps objects by clamping the object between the jaws. The moveable jaw is configured to move relative to the fixed jaw in order to move between an open position for the gripper and a closed position for the gripper (e.g., closed around an object).

In some implementations, the arm126may include additional joints JAsuch as the fifth arm joint JA5and/or the sixth arm joint JA6. The fifth joint JA5may be located near the coupling of the upper member128Uto the hand member128Hand functions to allow the hand member128Hto twist or to rotate relative to the lower member128U. In other words, the fifth arm joint JA4may function as a twist joint similarly to the fourth arm joint JA4or wrist joint of the arm126adjacent the hand member128H. For instance, as a twist joint, one member coupled at the joint J may move or rotate relative to another member coupled at the joint J (e.g., a first member portion coupled at the twist joint is fixed while the second member portion coupled at the twist joint rotates). Here, the fifth joint JA5may also enable the arm126to turn in a manner that rotates the hand member128Hsuch that the hand member128Hmay yaw instead of pitch. For instance, the fifth joint JA5allows the arm126to twist within a 180 degree range of motion such that the jaws associated with the hand member128Hmay pitch, yaw, or some combination of both. This may be advantageous for hooking some portion of the arm126around objects or refining the how the hand member128Hgrasps an object. The sixth arm joint JA6may function similarly to the fifth arm joint JA5(e.g., as a twist joint). For example, the sixth arm joint JA6also allows a portion of an arm member128(e.g., the upper arm member128U) to rotate or twist within a 180 degree range of motion (e.g., with respect to another portion of the arm member128or another arm member128). Here, a combination of the range of motion from the fifth arm joint JA5and the sixth arm joint JA6may enable 360 degree rotation. In some implementations, the arm126connects to the robot100at a socket on the body110of the robot100. In some configurations, the socket is configured as a connector such that the arm126may attach or detach from the robot100depending on whether the arm126is needed for operation. In some examples, the first and second arm joints JA1,2may be located at, adjacent to, or a portion of the socket that connects the arm126to the body110.

The robot100has a vertical gravitational axis (e.g., shown as a Z-direction axis AZ) along a direction of gravity, and a center of mass CM, which is a position that corresponds to an average position of all parts of the robot100where the parts are weighted according to their masses (i.e., a point where the weighted relative position of the distributed mass of the robot100sums to zero). The robot100further has a pose P based on the CM relative to the vertical gravitational axis AZ(i.e., the fixed reference frame with respect to gravity) to define a particular attitude or stance assumed by the robot100. The attitude of the robot100can be defined by an orientation or an angular position of the robot100in space. Movement by the legs120relative to the body110alters the pose P of the robot100(i.e., the combination of the position of the CM of the robot and the attitude or orientation of the robot100). Here, a height generally refers to a distance along the z-direction (e.g., along a z-direction axis AZ). The sagittal plane of the robot100corresponds to the Y-Z plane extending in directions of a y-direction axis AYand the z-direction axis AZ. In other words, the sagittal plane bisects the robot100into a left and a right side. Generally perpendicular to the sagittal plane, a ground plane (also referred to as a transverse plane) spans the X-Y plane by extending in directions of the x-direction axis AXand the y-direction axis AY. The ground plane refers to a ground surface14where distal ends124of the legs120of the robot100may generate traction to help the robot100move within the environment10. Another anatomical plane of the robot100is the frontal plane that extends across the body110of the robot100(e.g., from a left side of the robot100with a first leg120ato a right side of the robot100with a second leg120b). The frontal plane spans the X-Z plane by extending in directions of the x-direction axis AXand the z-direction axis Az.

In order to maneuver within the environment10or to perform tasks using the arm126, the robot100includes a sensor system130(also referred to as a vision system) with one or more sensors132,132a-n. For instance,FIG.1Aillustrates a first sensor132,132amounted at a head of the robot100, a second sensor132,132bmounted near the hip of the second leg120bof the robot100, a third sensor132,132ccorresponding one of the sensors132mounted on a side of the body110of the robot100, a fourth sensor132,132dmounted near the hip of the fourth leg120dof the robot100, and a fifth sensor132,132emounted at or near the end-effector128Hof the arm126of the robot100. The sensors132may include vision/image sensors, inertial sensors (e.g., an inertial measurement unit (IMU)), force sensors, and/or kinematic sensors. Some examples of sensors132include a camera such as a stereo camera, a time-of-flight (TOF) sensor, a scanning light-detection and ranging (LIDAR) sensor, or a scanning laser-detection and ranging (LADAR) sensor. In some examples, the sensor132has a corresponding field(s) of view FVdefining a sensing range or region corresponding to the sensor132. For instance,FIG.1Adepicts a field of a view FVfor the robot100. Each sensor132may be pivotable and/or rotatable such that the sensor132may, for example, change the field of view FVabout one or more axis (e.g., an x-axis, a y-axis, or a z-axis in relation to a ground plane). In some examples, multiple sensors132may be clustered together (e.g., similar to the first sensor132a) to stitch a larger field of view FVthan any single sensor132. With sensors132placed about the robot100, the sensor system130may have a 360 degree view or a nearly 360 degree view of the surroundings of the robot100.

When surveying a field of view FVwith a sensor132, the sensor system130generates sensor data134(e.g., image data) corresponding to the field of view FV. The sensor system130may generate the field of view FVwith a sensor132mounted on or near the body110of the robot100(e.g., sensor(s)132a,132b). The sensor system may additionally and/or alternatively generate the field of view FVwith a sensor132mounted at or near the end-effector128Hof the arm126(e.g., sensor(s)132c). The one or more sensors132may capture sensor data134that defines the three-dimensional point cloud for the area within the environment10about the robot100. In some examples, the sensor data134is image data that corresponds to a three-dimensional volumetric point cloud generated by a three-dimensional volumetric image sensor132. Additionally or alternatively, when the robot100is maneuvering within the environment10, the sensor system130gathers pose data for the robot100that includes inertial measurement data (e.g., measured by an IMU). In some examples, the pose data includes kinematic data and/or orientation data about the robot100, for instance, kinematic data and/or orientation data about joints J or other portions of a leg120or arm126of the robot100. With the sensor data134, various systems of the robot100may use the sensor data134to define a current state of the robot100(e.g., of the kinematics of the robot100) and/or a current state of the environment10about the robot100. In other words, the sensor system130may communicate the sensor data134from one or more sensors132to any other system of the robot100in order to assist the functionality of that system.

In some implementations, the sensor system130includes sensor(s)132coupled to a joint J. Moreover, these sensors132may couple to a motor M that operates a joint J of the robot100(e.g., sensors132,132b-d). Here, these sensors132generate joint dynamics in the form of joint-based sensor data134. Joint dynamics collected as joint-based sensor data134may include joint angles (e.g., an upper member122Urelative to a lower member122Lor hand member128Hrelative to another member of the arm126or robot100), joint speed, joint angular velocity, joint angular acceleration, and/or forces experienced at a joint J (also referred to as joint forces). Joint-based sensor data generated by one or more sensors132may be raw sensor data, data that is further processed to form different types of joint dynamics, or some combination of both. For instance, a sensor132measures joint position (or a position of member(s)122coupled at a joint J) and systems of the robot100perform further processing to derive velocity and/or acceleration from the positional data. In other examples, a sensor132is configured to measure velocity and/or acceleration directly.

As the sensor system130gathers sensor data134, a computing system140stores, processes, and/or communicates the sensor data134to various systems of the robot100(e.g., the computing system140, the control system170, the perception system180, and/or the navigation system200). In order to perform computing tasks related to the sensor data134, the computing system140of the robot100(which is schematically depicted inFIG.1Aand can be implemented in any suitable location(s), including internal to the robot100) includes data processing hardware142and memory hardware144. The data processing hardware142is configured to execute instructions stored in the memory hardware144to perform computing tasks related to activities (e.g., movement and/or movement-based activities) for the robot100. Generally speaking, the computing system140refers to one or more locations of data processing hardware142and/or memory hardware144.

In some examples, the computing system140is a local system located on the robot100. When located on the robot100, the computing system140may be centralized (e.g., in a single location/area on the robot100, for example, the body110of the robot100), decentralized (e.g., located at various locations about the robot100), or a hybrid combination of both (e.g., including a majority of centralized hardware and a minority of decentralized hardware). To illustrate some differences, a decentralized computing system140may allow processing to occur at an activity location (e.g., at motor that moves a joint of a leg120) while a centralized computing system140may allow for a central processing hub that communicates to systems located at various positions on the robot100(e.g., communicate to the motor that moves the joint of the leg120).

Additionally or alternatively, the computing system140utilizes computing resources that are located remotely from the robot100. For instance, the computing system140communicates via a network150with a remote system160(e.g., a remote server or a cloud-based environment). Much like the computing system140, the remote system160includes remote computing resources, such as remote data processing hardware162and remote memory hardware164. Here, sensor data134or other processed data (e.g., data processing locally by the computing system140) may be stored in the remote system160and may be accessible to the computing system140. In additional examples, the computing system140is configured to utilize the remote resources162,164as extensions of the computing resources142,144such that resources of the computing system140may reside on resources of the remote system160.

In some implementations, as shown inFIGS.1A and1B, the robot100includes a control system170and a perception system180. The perception system180is configured to receive the sensor data134from the sensor system130and process the sensor data134to generate perception maps182. With the perception maps182generated by the perception system180, the perception system180may communicate the perception maps182to the control system170in order to perform controlled actions for the robot100, such as moving the robot100within the environment10. In some examples, by having the perception system180separate from, yet in communication with the control system170, processing for the control system170may focus on controlling the robot100while the processing for the perception system180focuses on interpreting the sensor data134gathered by the sensor system130. For instance, these systems170,180execute processing in parallel to ensure accurate, fluid movement of the robot100in an environment10.

A given controller172may control the robot100by controlling movement about one or more joints J of the robot100. In some configurations, the given controller172is software with programming logic that controls at least one joint J or a motor M which operates, or is coupled to, a joint J. For instance, the controller172controls an amount of force that is applied to a joint J (e.g., torque at a joint J). As programmable controllers172, the number of joints J that a controller172controls is scalable and/or customizable for a particular control purpose. A controller172may control a single joint J (e.g., control a torque at a single joint J), multiple joints J, or actuation of one or more members122,128(e.g., actuation of the hand member128H) of the robot100. By controlling one or more joints J, actuators or motors M, the controller172may coordinate movement for all different parts of the robot100(e.g., the body110, one or more legs120, the arm126). For example, to perform a behavior with some movements, a controller172may be configured to control movement of multiple parts of the robot100such as, for example, two legs120a-b, four legs120a-d, the arm126, or any combination of legs120and/or arm126(e.g., two or four legs120combined with the arm126). In some examples, a controller172is configured as an object-based controller that is setup to perform a particular behavior or set of behaviors for interacting with an interactable object.

In some examples, the control system170includes at least one controller172, a path generator174, a step locator176, and a body planner178. The control system170may be configured to communicate with at least one sensor system130and any other system of the robot100(e.g., the perception system180and/or the navigation system200). The control system170performs operations and other functions using the computing system140. The controller172is configured to control movement of the robot100to traverse the environment10based on input or feedback from the systems of the robot100(e.g., the sensor system130, the perception system180, and/or the navigation system200). This may include movement between poses and/or behaviors of the robot100. For example, the controller172controls different footstep patterns, leg patterns, body movement patterns, or vision system-sensing patterns.

In some implementations, the control system170includes specialty controllers that are dedicated to a particular control purpose. These specialty controllers may include, but need not be limited to, the path generator174, the step locator176, and/or the body planner178. Referring toFIG.1B, the path generator174is configured to determine horizontal motion for the robot100. For instance, the horizontal motion refers to translation (i.e., movement in the X-Y plane) and/or yaw (i.e., rotation about the Z-direction axis AZ) of the robot100. The path generator174determines obstacles within the environment10about the robot100based on the sensor data134. The path generator174communicates the obstacles to the step locator176such that the step locator176may identify foot placements for legs120of the robot100(e.g., locations to place the distal ends124of the legs120of the robot100). The step locator176generates the foot placements (i.e., locations where the robot100should step) using inputs from the perception system180(e.g., map(s)182). The body planner178, much like the step locator176, receives inputs from the perception system180(e.g., map(s)182). Generally speaking, the body planner178is configured to adjust dynamics of the body110of the robot100(e.g., rotation, such as pitch or yaw and/or height) to successfully move about the environment10.

The perception system180is a system of the robot100that helps the robot100to move more precisely in a terrain with various obstacles. As the sensors132collect sensor data134for the space about the robot100(i.e., the robot's environment10), the perception system180uses the sensor data134to form one or more perception maps182for the environment10. Once the perception system180generates a perception map182, the perception system180is also configured to add information to the perception map182(e.g., by projecting sensor data134on a preexisting map) and/or to remove information from the perception map182.

In some examples, the one or more perceptions maps182generated by the perception system180are a ground height map182,182a, a no step map182,182b, and/or a body obstacle map182,182c(collectively182a-cinFIG.1B). The ground height map182arefers to a perception map182generated by the perception system180based on spatial occupancy of an area (e.g., the environment10) divided into three-dimensional volume units (e.g., voxels from a voxel map). In some implementations, the ground height map182afunctions such that, at each X-Y location within a grid of the map182(e.g., designated as a cell of the ground height map182a), the ground height map182aspecifies a height. In other words, the ground height map182aconveys that, at a particular X-Y location in a horizontal plane, the robot100should step at a certain height.

The no step map182bgenerally refers to a perception map that defines regions where the robot100is not allowed to step in order to advise the robot100when the robot100may step at a particular horizontal location (i.e., location in the X-Y plane). In some examples, much like the body obstacle map182cand the ground height map182a, the no step map182bis partitioned into a grid of cells where each cell represents a particular area in the environment10about the robot100. For instance, each cell is a three centimeter square. For ease of explanation, each cell exists within an X-Y plane within the environment10. When the perception system180generates the no-step map182b, the perception system180may generate a Boolean value map where the Boolean value map identifies no step regions and step regions. A no step region refers to a region of one or more cells where an obstacle exists while a step region refers to a region of one or more cells where an obstacle is not perceived to exist. The perception system180may further process the Boolean value map such that the no step map182bincludes a signed-distance field. Here, the signed-distance field for the no step map182bincludes a distance to a boundary of an obstacle (e.g., a distance to a boundary of the no step region) and a vector v (e.g., defining nearest direction to the boundary of the no step region) to the boundary of an obstacle.

The body obstacle map182cgenerally determines whether the body110of the robot100may overlap a location in the X-Y plane with respect to the robot100. In other words, the body obstacle map182cidentifies obstacles for the robot100to indicate whether the robot100, by overlapping at a location in the environment10, risks collision or potential damage with obstacles near or at the same location. As a map of obstacles for the body110of the robot100, systems of the robot100(e.g., the control system170) may use the body obstacle map182cto identify boundaries adjacent, or nearest to, the robot100as well as to identify directions (e.g., an optimal direction) to move the robot100in order to avoid an obstacle. In some examples, much like other perception maps182, the perception system180generates the body obstacle map182caccording to a grid of cells (e.g., a grid of the X-Y plane). Here, each cell within the body obstacle map182cincludes a distance from an obstacle and a vector pointing to the closest cell that is an obstacle (i.e., a boundary of the obstacle).

Referring further toFIG.1B, the robot100also includes a navigation system200. The navigation system200is a system of the robot100that navigates the robot100along a path referred to as a navigation route202(or simply route202) in order to traverse an environment10. The navigation system200may be configured to receive the navigation route202as an input or to generate the navigation route202(e.g., in its entirety or some portion thereof). To generate the navigation route202and/or to guide the robot100along the navigation route202, the navigation system200is configured to operate in conjunction with the control system170and/or the perception system180. For instance, the navigation system200receives perception maps182that may inform decisions performed by the navigation system200or otherwise influence some form of mapping performed by the navigation system200itself. The navigation system200may operate in conjunction with the control system170such that one or more controllers172and/or specialty controller(s)174,176,178may control the movement of components of the robot100(e.g., legs120and/or the arm126) to navigate along the navigation route202.

As the navigation system200guides the robot100through movements that follow the navigation route202, the navigation system200is configured to determine whether the navigation route202becomes obstructed by an object. That is, the navigation route202is derived from a topological map204(see for example,FIG.2A) that includes locations associated with movement instructions that dictate how to move from one location to another. The topological map204may correspond to a high-level map of the environment that is abstracted to remove metric details that fail to correspond to the locations and movement instructions. Put another way, the movement instructions are able to account for objects or other obstacles at the time of recording the locations to the topological map204, but may not reflect objects or obstacles introduced to the environment or shifted since the time of recording.

Since the environment10may dynamically change from the time of recording the locations to the topological map204, the navigation system200is configured to determine whether the navigation route202becomes obstructed by an object that was not previously discovered in its obstructed location when recording the locations being used by the navigation route202. Stated differently, an object is in a location that obstructs the navigation route202during execution of the route202when the object exists in the path of the route202and the object was not present in that location when the location(s) of the navigation route202was recorded to the topological map204. This results in the object being an “unforeseeable obstacle” in the navigation route202because the initial mapping process that informs the navigation route202did not recognize the object in the obstructed location. This may occur when an object is moved or introduced to a mapped environment.

When an unforeseeable obstacle obstructs the route202, the navigation system200is configured to attempt to generate an alternative path206to a location in the route202that avoids the unforeseeable obstacle. This alternative path206may deviate from the navigation route202temporarily, but then resume the navigation route202after the deviation.

Unlike other approaches to generate an obstacle avoidance path, the navigation system200has the goal to only temporarily deviate from the route202to avoid the unforeseeable obstacle such that the robot100may return to using course features (e.g., like topological features from the topological map204) for the navigation route202.

In this sense, successful obstacle avoidance for the navigation system200is when an obstacle avoidance path both (i) avoids the unforeseeable obstacle and (ii) enables the robot100to resume some portion of the navigation route202. This technique to merge back with the navigation route202after obstacle avoidance may be advantageous because the navigation route202may be important for task or mission performance for the robot100(or an operator of the robot100). For instance, an operator of the robot100tasks the robot100to perform an inspection task at a location of the route202. By generating an obstacle avoidance route that continues on the route202after obstacle avoidance, the navigation system200aims to promote task or mission success for the robot100.

To illustrate,FIG.1Adepicts a navigation route202that includes three locations shown as waypoints212(e.g., shown as waypoints212a,212b, and212c).

In the example ofFIG.1A, while moving along a first portion of the route202(e.g., shown as a first edge214,214a) from a first location (e.g., shown as a first waypoint212a) to a second location (e.g., shown as a second waypoint212b), the robot100encounters an unforeseeable obstacle20depicted as a partial pallet of boxes. This unforeseeable obstacle20blocks the robot100from completing the first portion214aof the route202to the second location (e.g., shown as the second waypoint212b). Here, the X over the second location symbolizes that the robot100is unable to successfully travel to the second location (second waypoint212b) given the pallet of boxes20. As depicted inFIG.1A, the route202would normally have a second portion (e.g., shown as a second edge214,214b) that extends from the second location to a third location (e.g., shown as a third waypoint212c). Due to the unforeseeable object20, the navigation system200generates an alternative path206that directs the robot100to move to avoid the unforeseeable obstacle20and to travel to the third location (third waypoint212c) of the navigation route202(e.g., from a point along the first portion of the route202).

In this respect, the robot100may not be able to successfully navigate to one or more locations, such as the second location (second waypoint212b), but may resume a portion of the navigation route202after avoiding the obstacle20. For instance, the navigation route202includes more locations subsequent to the third location (waypoint212c) and the alternative path206enables the robot100to continue to those locations after the alternative path206navigates the robot100to the third location (i.e., a location included in the route202). The waypoint212cis an untraveled waypoint along the navigation route202that inFIG.1Athe robot100has not yet reached.

In some implementations, an object that is an unforeseeable obstacle20(also referred to as obstacle20) may be specific to the type of robot100performing navigation. That is, whether an object blocking a portion of the route202is truly an obstacle may vary based on the morphology of the robot100(e.g., the locomotion structures of the robot100). For instance, some objects may not be considered “obstacles” because the robot100is implemented with a footpath range of motion that steps over the object. Here, if the robot100is able to step across the object without requiring deviation from the route202, the object is not an obstacle. This is true even when the robot100may need to deviate from a nominal step height, but nonetheless execute a step height within the robot's capabilities. In contrast, if the robot100were a wheel-based or tracked-based robot, the robot100would not have the capability to step over the object, and most objects would cause these types of robots100to deviate from the route202to avoid the object. With a wheel-based or tracked-based robot, many objects that block the route202would be considered an unforeseeable obstacle20. Although in situations where a wheel-based robot or tracked-based robot is able to wheel over the object, the object may also not be considered an obstacle for route navigation purposes. In some implementations, when the robot100is a quadruped robot100with four legs120, there may be a situation when an object does not pose a foot placement issue (i.e., obstructs or hinders a foot touchdown), but nonetheless poses an obstruction for the body110of the robot100. For instance, an object occupies a plane offset from the ground plane, but has open space underneath the plane. In this sense, for something that resembles a table or a platform, the robot100may be able to place one of its feet124underneath the occupied plane, but the body110of the robot100would collide with the plane. Here, due to the shape of the body110and the legs120(e.g., the legs120offset the body110from a support surface), this type of object would be considered an obstacle. For reasons such as this, the shape and/or design of the robot100may dictate whether an object actually functions as an obstacle20.

Referring now toFIGS.2A-2F, the navigation system200includes a navigation generator210and a route executor220. The navigation generator210(also referred to as the navigation generator210) is configured to construct a topological map204and to generate the navigation route202from the topological map204. To generate the topological map204, the navigation system200and, more particularly, the generator210records locations within an environment10that has been traversed or is being traversed by the robot100as waypoints212. A waypoint212can correspond to a representation of what the robot100sensed (e.g., according to its sensor system130) at a particular place within the environment10. The generator210generates waypoints212based on the image data134collected by the sensor system130of the robot100. For instance, a robot100may perform an initial mapping process where the robot100moves through the environment10. While moving through the environment10, systems of the robot100, such as the sensor system130are gathering data (e.g., sensor data134) as a means to understand the environment10. By gathering an understanding of the environment10, the robot100may later move about the environment10(e.g., autonomously, semi-autonomously, or with assisted operation by a user) using the information or a derivative thereof gathered from the initial mapping process.

In some implementations, the generator210builds the topological map204by executing at least one waypoint heuristic (e.g., waypoint search algorithm) that triggers the generator210to record a waypoint placement at a particular location in the topological map204. For example, the waypoint heuristic is configured to detect a threshold feature detection within the image data134at a location of the robot100(e.g., when generating or updating the topological map204).

The generator210(e.g., using a waypoint heuristic) may identify features within the environment10that function as reliable vision sensor features offering repeatability for the robot100to maneuver about the environment10. For instance, a waypoint heuristic of the generator210is pre-programmed for feature recognition (e.g., programmed with stored features) or programmed to identify features where spatial clusters of volumetric image data134occur (e.g., corners of rooms or edges of walls). In response to the at least one waypoint heuristic triggering the waypoint placement, the generator210records the waypoint212on the topological map204. This waypoint identification process may be repeated by the generator210as the robot100drives through an area (e.g., the robotic environment10). For instance, an operator of the robot100manually drives the robot100through an area for an initial mapping process that establishes the waypoints212for the topological map204.

When recording each waypoint212, the generator210generally associates a waypoint edge214(also referred to as an edge214) with a respective waypoint212such that the topological map204produced by the generator210includes both waypoints212and their respective edges214. An edge214is configured to indicate how one waypoint212(e.g., a first waypoint210a) is related to another waypoint212(e.g., a second waypoint212b). For example, the edge214represents a positional relationship between waypoints212(e.g., adjacent waypoints212). In other words, the edge214is a connection or designated path between two waypoints212(e.g., the edge214ashown inFIG.2Aas a connection between a first waypoint210aand a second waypoint210b). For instance, the edge214is a path (e.g., a movement path for the robot100) between the first waypoint210ato the second waypoint210b. Yet, in some examples, an edge214is not simply a line (or trajectory) for the robot100to follow. Rather each edge214includes movement instructions that inform the robot100how to move or navigate between waypoints212connected by the respective edge214. Here, these movement instructions may include one or more pose transform that expresses how the robot100moves along the edge214between two waypoints212.

Pose transformations may describe a position and/or orientation of one coordinate frame within an environment relative to another coordinate frame. In other words, the pose transformations serve as movement instructions that dictate one or more positions and/or orientations for the robot100to assume to successfully navigate along the edge214from a source waypoint212to a destination waypoint212. In some implementations, the edge214includes a full three-dimensional transform (e.g., six numbers). Some of these numbers include various estimates such as, for example, a dead reckoning pose estimation, a vision based estimation, or other estimations based on kinematics and/or inertial measurements of the robot100.

In some examples, the edge214includes annotations that provide further indication/description of the environment10. Some examples of annotations include a description or an indication that an edge214is associated with or located on some feature of the environment10. For instance, an annotation for an edge214specifies that the edge214is located on stairs or crosses a doorway. These annotations may aid the robot100during maneuvering especially when visual information is missing or lacking (e.g., a void such as a doorway). In some configurations, the annotations include directional constraints (also may be referred to as pose constraints). A directional constraint of the annotation may specify an alignment and/or an orientation (e.g., a pose) of the robot100at a particular environment feature. For example, the annotation specifies a particular alignment or pose for the robot100before traveling along stairs or down a narrow corridor which may restrict the robot100from turning.

In some implementations, each waypoint212of the topological map204also includes sensor data134corresponding to data collected by the sensor system130of the robot100when the generator210recorded a respective waypoint212to the topological map204. Here, the sensor data134at a waypoint212may enable the robot100to localize by comparing real-time sensor data134gathered as the robot100traverses the environment10according to the topological map204(e.g., a route202from the topological map204) with sensor data134stored for the waypoints212of the topological map204.

In some configurations, after the robot100moves along an edge214(e.g., with the intention to be at a target waypoint212), the robot100is configured to localize by directly comparing real-time sensor data134with the topological map204(e.g., sensor data134associated with the intended target waypoint212of the topological map204). Here, by storing raw or near-raw sensor data134with minimal processing for the waypoints212of the topological map204, the robot100may use real-time sensor data134to localize efficiently as the robot100maneuvers within the mapped environment10. In some examples, an iterative closest points (ICP) algorithm localizes the robot100with respect to a waypoint212.

Because the generator210produces the topological map204using waypoints212and edges214, the topological map204may be locally consistent (e.g., spatially consistent within an area due to neighboring waypoints), but does not need to be globally accurate and/or consistent. That is, as long as geometric relations (e.g., edges214) between adjacent waypoints212are roughly accurate, the topological map204does not require precise global metric localization for the robot100and sensed objects within the environment10. Without requiring this for the topological map204, a navigation route202derived or built using the topological map204also does not need precise global metric information. Moreover, since the topological map204may be built only using waypoints212and a relationship between waypoints (e.g., edges214), the topological map204may be considered an abstraction or high-level map in comparison to a metric map. That is, the topological map204can be devoid of other metric data about the mapped environment that does not relate to waypoints212or their corresponding edges214. For instance, the mapping process (e.g., by the generator) that creates the topological map204may not store or record other metric data or the mapping process may remove recorded metric data to form a topological map204of waypoints212and edges214.

Either way, navigating with the topological map204may simplify the hardware needed for navigation and/or the computational resources used during navigation. That is, topological-based navigation may operate with low-cost vision and/or low-cost inertial measurement unit (IMU) sensors when compared to navigation using metric localization that often requires expensive LIDAR sensors and/or expensive IMU sensors. Metric-based navigation tends to demand more computational resources than topological-based navigation because metric-based navigation often performs localization at a much higher frequency than topological navigation (e.g., with waypoints212). For instance, the common navigation approach of Simultaneous Localization and Mapping (SLAM) using a global occupancy grid is constantly performing robot localization.

Referring toFIG.2A, the generator210records a plurality of waypoints212,212a-ion a topological map204. From the plurality of recorded waypoints212, the generator210selects some number of recorded waypoints212as a sequence of waypoints212that form the navigation route202for the robot100. In some examples, an operator of the robot100may use the generator210to select or build a sequence of waypoints212to form the navigation route202. In some implementations, the generator210generates the route202based on receiving a destination location and a starting location for the robot100. For instance, the generator210matches the starting location with a nearest waypoint212and similarly matches the destination location with a nearest waypoint212. The generator210may then select some number of waypoints212between these nearest waypoints212to generate the route202. In some configurations, the generator210receives a task or mission and generates a route202as a sequence of waypoints212that will achieve that task or mission. For instance, for a mission to inspect different locations on a pipeline, the generator210generates a route202that includes waypoints212that coincide with the inspection locations. In the example shown inFIG.2A, the generator210generates a route202with a sequence of waypoints212that include nine waypoints212a-iand their corresponding edges214a-h.FIG.2Aillustrates each waypoint212of the route202in a double circle while recorded waypoints212that are not part of the route202only have a single circle. The generator210then communicates the route202to the route executor220.

The route executor220(also referred to as the executor220) is configured to receive and to execute the navigation route202. To execute the navigation route202, the executor220may coordinate with other systems of the robot100to control the locomotion-based structures of the robot100(e.g., the legs) to drive the robot100along the route202through the sequence of waypoints212. For instance, the executor220communicates the movement instructions of edges214connecting waypoints212in the sequence of waypoints212of the route202to the control system170. The control system170may use these movement instructions to position the robot100(e.g., in an orientation) according to one or more pose transforms to successfully move the robot100along the edges214of the route202.

While the robot100is traveling along the route202, the executor220is also configured to determine whether the robot100is unable to execute a particular movement instruction for a particular edge214. For instance, the robot100is unable to execute a movement instruction for an edge214because the robot100encounters an unforeseeable obstacle20while moving along the edge214to a waypoint212. Here, the executor220recognizes that an unforeseeable obstacle20blocks the path of the robot100(e.g., using real-time or near real-time sensor data134) or otherwise precludes the robot100from executing the movement instructions for the edge214and is configured to determine whether an alternative path206for the robot100exists to an untraveled waypoint212,212U in the sequence of the route202. An untraveled waypoint212U refers to a waypoint212of the waypoint sequence for the route202that the robot100has not already successfully traveled to. For instance, if the robot100had already traveled to three of the nine waypoints212a-cof the route202, the executor220would try to find an alternative path206to one or the remaining six waypoints212d-iif possible.

The executor220may first attempt to find the alternative path206to the next untraveled-to waypoint212before attempting to find the alternative path206to subsequent untraveled to-waypoints212, such as attempting to find the alternative path206from waypoint212cto waypoint212dbefore finding the alternative path206from waypoint212cto one of waypoints212e-i. In this sense, the alternative path206is an obstacle avoidance path that avoids the unforeseeable obstacle20and also a path that allows the robot100to resume the navigation route202(e.g., toward a particular goal or task). This means that after the robot100travels along the alternative path206to a destination of an untraveled waypoint212U, the executor220continues executing the route202from that destination of the alternative path206. This approach enables the robot100to return to navigation using the sparse topological map204. In other words, the alternative path206avoiding the obstacle20may deviate from the navigation route202to avoid the obstacle20and merge with or continue the navigation route202after avoiding the obstacle20to return to navigating using the less resource-intensive topological map204.

For example, referring to the example ofFIG.2A, if the unforeseeable obstacle20blocks some portion of the third edge214c(e.g., blocks some portion of the third edge214cand the fourth waypoint212d), the robot100has already traveled to three waypoints212a-c; therefore, the executor220generates an alternative path206avoiding the unforeseeable obstacle20to the fifth waypoint212e, which is an untraveled waypoint212U. The robot100may then continue the sequence of waypoints212for the route202from the fifth waypoint212e. This means that the robot100would then travel to the untraveled portion following the sequence of waypoints212for the route202(e.g., by using the movement instructions of edges214of the untraveled portion). In the example, the robot100would travel from the fifth waypoint212eto the sixth, seventh, eighth, and finally ninth waypoints212,212f-ibarring some other unforeseeable object20. This means that, although the unforeseeable object20was present along the third edge214c, the robot100only missed a single waypoint, the fourth waypoint212d, during its movement path while executing the route202.

In some implementations, when the executor220determines that an unforeseeable obstacle20blocks an edge214, the executor220identifies that the topological map204fails to provide an alternative route206avoiding the unforeseeable obstacle20. This is usually the case because the topological map204includes waypoints212and edges214that were recorded during the mapping process (e.g., by the generator210). Since the unforeseeable obstacle20was not present at that time of mapping, the topological map204fails to be able to generate an alternative path206on its own.

In other words, the generator210did not anticipate needing a path or edge214resembling the alternative path inFIG.2Afrom the third waypoint212cto the fifth waypoint212e. This also means that the alternative path206is likely a path that does not correspond to an existing edge214in the topological map204. Stated differently, the alternative path206results in a path between two waypoints212that were previously unconnected (e.g., by an edge214) in the navigation route202In other implementations, the executor220assumes that the presence of an unforeseeable obstacle20necessitates that the executor220use other means besides the topological map204to generate the alternative path206.

In some configurations, when an edge214is blocked by an unforeseeable object20, the executor220resorts to other maps that are available from the systems of the robot100. In some examples, the executor220uses or generates a local obstacle map222from current sensor data134captured by the sensor system130of the robot100. Here, the local obstacle map222may refer to a more detailed map of the environment10than the topological map204, but only for a local area surrounding the robot100(e.g., a three meter by three meter square area).

In some configurations, the local obstacle map222includes an occupancy grid where each cell within the grid designates whether an obstacle is present in that cell or not. The executor220may then generate the alternative path206using the unoccupied cells of the occupancy grid in combination with the positions of the untraveled waypoints212U.

In some examples, the local obstacle map222is formed in whole or in part using the perception maps182from the perception system180(e.g., the ground height map182a, the no step map182b, and/or the body obstacle map182c) for the local area surrounding the robot100.

With the local obstacle map222of finite size, the executor220may determine which untraveled waypoint212U should be the destination of the alternative path206by determining which untraveled waypoints212U exists within the bounds of the local obstacle map222.

Referring to the example ofFIG.2B, the navigation route202includes a sequence of five waypoints212a-e. Here, the robot100has traveled to the second waypoint212bonly to discover an unforeseeable obstacle20blocking a second edge214bconnecting the second waypoint212band a third waypoint212c. To determine the alternative path206(e.g., the destination of the alternative path206), the executor220determines which untraveled waypoints212U exist within the bounds of the local obstacle map222. In this example, the untraveled waypoints212U are the third, fourth, and fifth waypoints212c-eand only the fourth waypoint212dis within the bounds of the local obstacle map222.

For reference,FIG.2Billustrates the local obstacle map222as a grid. Although the third waypoint212cand the fifth waypoint212eare also untraveled waypoints212U in addition to the fourth waypoint212d, neither of these waypoints212c,212eexist within the bounds of the local obstacle map222. In a sense, the local obstacle map222is therefore unaware how to generate an alternative path206to either of the third or fifth waypoints212c,212e. Since the fourth waypoint212dis the only waypoint212within the bounds of the local obstacle map222, the executor220generates the alternative path206avoiding the obstacle20to the fourth waypoint212d. The robot100would then proceed to follow the route202from the fourth waypoint212dto the fifth waypoint212ealong the fourth edge214d.

In some examples, the executor220functions methodically such that, for each untraveled waypoint212U, the executor220identifies whether a respective untraveled waypoint212U exists within the local obstacle map222. For instance, the executor220performs this identification for each untraveled waypoint sequentially following the waypoint sequence of the route202. For the example ofFIG.2B, this would mean that the executor220first determines whether the third waypoint212cis within the local obstacle map222, which it is not. The executor220next determines whether the fourth waypoint212dis within the local obstacle map222, which it is. The executor220then determines whether the fifth waypoint212eis in the local obstacle map222.

In the example ofFIG.2C, the local obstacle map222includes multiple untraveled waypoints. Thus, in comparison to the example ofFIG.2Bin which the fifth waypoint212eis not in the bounds of the local obstacle map222,FIG.2Cdepicts an example in which the fifth waypoint212eis located within the bounds of the local obstacle map222. In a situation likeFIG.2Cwhere more than one untraveled waypoint212U is within the bounds of the local obstacle map222, the executor220may be configured to ensure the robot100travels to as many of the waypoints212of the route202as possible. With this criteria, the executor220would generate an alternative path206to the fourth waypoint212dinstead of the fifth waypoint212eso that, when the robot100continues along the navigation route202after traveling along the alternative path206to the fourth waypoint212d, the robot100will travel to the fifth waypoint212e, thus ensuring that the robot100travels to the most possible waypoints212of the route202during its movement path.

FIGS.2D and2Eillustrate a scenario that may occur where there are no untraveled waypoints212U within the bounds of the local obstacle map222. In this situation, the executor220may be configured to generate an exploration path224in a direction toward the next waypoint212in the sequence of waypoints212for the route202that avoids the unforeseeable obstacle20. InFIG.2D, the unforeseeable obstacle20obstructs the second edge214bbetween the second waypoint212band the third waypoint212c. Because the third waypoint212cis the next untraveled waypoint212U in the sequence of waypoints212for the route202, the executor220generates an exploration path224where the exploration path224is an obstacle avoidance path towards the third waypoint212c. In the example ofFIGS.2D and2E, the robot100has open space to explore in the direction indicated by the exploration path224until the third waypoint212cis within the local obstacle map222.

Thus, as the robot100moves along the exploration path224, the local obstacle map222will continue to span its finite area. This means that an untraveled waypoint212U previously not within the bounds of the local obstacle map222may become within the bounds of the local obstacle map222. In this respect, the robot100is exploring along the exploration path224until an untraveled waypoint212U exists within the bounds of the local obstacle map222.

As shown in the example ofFIG.2E, once an untraveled waypoint212U exists within the bounds of the local obstacle map222, the executor220is able to generate the alternative path206with a destination of the untraveled waypoint212U. By traveling along an exploration path224towards the next waypoint212in the sequence of waypoints212for the route202, the executor220is configured to minimize the number of waypoints212that will not be traveled to by the robot100(or maximize the number of waypoints212achieved by the robot100).

The example ofFIG.2Fis similar to the example ofFIG.2Cin that the bounds of the local obstacle map222include more than one untraveled waypoint212U. In the illustrated embodiment, a first unforeseeable obstacle20,20aobstructs a second edge214band a fifth edge214e(e.g., completely blocking a room or a corridor). Meanwhile, a second obstacle20,20bdoes not block an edge214, but forces the alternative path206to account for its presence at least partially obstructing the shortest path between the second waypoint212band the sixth waypoint212f. This example also illustrates that the alternative path206may result in skipping multiple waypoints212(e.g., the third, fourth, and fifth waypoints212U,212c-e). Since the executor220generates an alternative path206from the second waypoint212bto the untraveled sixth waypoint212U,212f, the robot100would continue to travel along the route202from the sixth waypoint212fto the seventh waypoint212galong the sixth edge214f.

FIG.3is a flowchart of an example arrangement of operations for a method300of generating an alternative path206for a navigation route202. At operation302, the method300receives a navigation route202for a mobile robot100to traverse an environment10. The navigation route202includes a sequence of waypoints212connected by edges214where each waypoint is recorded during an initial mapping of the environment10. Each edge214corresponds to movement instructions that navigate the mobile robot100between adjacent waypoints212of the sequence of waypoints212. While the mobile robot100is traveling along the navigation route202, operations304-308occur. At operation304, the method300determines that the mobile robot100is unable to execute a respective movement instruction for a respective edge214of the navigation route202due to an obstacle20previously undiscovered during the initial mapping of the environment10. At operation306, the method300generates an alternative path206to an untraveled waypoint212U of the sequence of waypoints212that avoids the obstacle20and deviates from the navigation route202. After traveling along the alternative path206to the untraveled waypoint212U, at operation308, the method300resumes the navigation route202to traverse the environment10.

FIG.4is a schematic view of an example computing device400that may be used to implement the systems (e.g., the robot100, the sensor system130, the computing system140, the remote system160, the control system170, the perception system180, and/or the navigation system200) and methods (e.g., the method300) described in this document. The computing device400is intended to represent various forms of digital computers, such as laptops, desktops, workstations, personal digital assistants, servers, blade servers, mainframes, and other appropriate computers. The components shown here, their connections and relationships, and their functions, are meant to be exemplary only, and are not meant to limit implementations of the inventions described and/or claimed in this document.

The computing device400includes a processor410(e.g., data processing hardware142,162), memory420(e.g., memory hardware144,164), a storage device430, a high-speed interface/controller440connecting to the memory420and high-speed expansion ports450, and a low speed interface/controller460connecting to a low speed bus470and a storage device430. Each of the components410,420,430,440,450, and460, are interconnected using various busses, and may be mounted on a common motherboard or in other manners as appropriate. The processor410can process instructions for execution within the computing device400, including instructions stored in the memory420or on the storage device430to display graphical information for a graphical user interface (GUI) on an external input/output device, such as display480coupled to high speed interface440. In other implementations, multiple processors and/or multiple buses may be used, as appropriate, along with multiple memories and types of memory. Also, multiple computing devices400may be connected, with each device providing portions of the necessary operations (e.g., as a server bank, a group of blade servers, or a multi-processor system).

The memory420stores information non-transitorily within the computing device400. The memory420may be a computer-readable medium, a volatile memory unit(s), or non-volatile memory unit(s). The non-transitory memory420may be physical devices used to store programs (e.g., sequences of instructions) or data (e.g., program state information) on a temporary or permanent basis for use by the computing device400. Examples of non-volatile memory include, but are not limited to, flash memory and read-only memory (ROM)/programmable read-only memory (PROM)/erasable programmable read-only memory (EPROM)/electronically erasable programmable read-only memory (EEPROM) (e.g., typically used for firmware, such as boot programs). Examples of volatile memory include, but are not limited to, random access memory (RAM), dynamic random access memory (DRAM), static random access memory (SRAM), phase change memory (PCM) as well as disks or tapes.

The storage device430is capable of providing mass storage for the computing device400. In some implementations, the storage device430is a computer-readable medium. In various different implementations, the storage device430may be a floppy disk device, a hard disk device, an optical disk device, or a tape device, a flash memory or other similar solid state memory device, or an array of devices, including devices in a storage area network or other configurations. In additional implementations, a computer program product is tangibly embodied in an information carrier. The computer program product contains instructions that, when executed, perform one or more methods, such as those described above. The information carrier is a computer- or machine-readable medium, such as the memory420, the storage device430, or memory on processor410.

The high speed controller440manages bandwidth-intensive operations for the computing device400, while the low speed controller460manages lower bandwidth-intensive operations. Such allocation of duties is exemplary only. In some implementations, the high-speed controller440is coupled to the memory420, the display480(e.g., through a graphics processor or accelerator), and to the high-speed expansion ports440, which may accept various expansion cards (not shown). In some implementations, the low-speed controller460is coupled to the storage device430and a low-speed expansion port470. The low-speed expansion port470, which may include various communication ports (e.g., USB, Bluetooth, Ethernet, wireless Ethernet), may be coupled to one or more input/output devices, such as a keyboard, a pointing device, a scanner, or a networking device such as a switch or router, e.g., through a network adapter.

The computing device400may be implemented in a number of different forms, as shown in the figure. For example, it may be implemented as a standard server400aor multiple times in a group of such servers400a, as a laptop computer400b, as part of a rack server system500c, as part of the robot100, or as part of the remote control.

Various implementations of the systems and techniques described herein can be realized in digital electronic and/or optical circuitry, integrated circuitry, specially designed ASICs (application specific integrated circuits), computer hardware, firmware, software, and/or combinations thereof. These various implementations can include implementation in one or more computer programs that are executable and/or interpretable on a programmable system including at least one programmable processor, which may be special or general purpose, coupled to receive data and instructions from, and to transmit data and instructions to, a storage system, at least one input device, and at least one output device.

These computer programs (also known as programs, software, software applications or code) include machine instructions for a programmable processor, and can be implemented in a high-level procedural and/or object-oriented programming language, and/or in assembly/machine language. As used herein, the terms “machine-readable medium” and “computer-readable medium” refer to any computer program product, non-transitory computer readable medium, apparatus and/or device (e.g., magnetic discs, optical disks, memory, Programmable Logic Devices (PLDs)) used to provide machine instructions and/or data to a programmable processor, including a machine-readable medium that receives machine instructions as a machine-readable signal. The term “machine-readable signal” refers to any signal used to provide machine instructions and/or data to a programmable processor.

The processes and logic flows described in this specification can be performed by one or more programmable processors executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows can also be performed by special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit). Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read only memory or a random access memory or both. The essential elements of a computer are a processor for performing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks. However, a computer need not have such devices. Computer readable media suitable for storing computer program instructions and data include all forms of non-volatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto optical disks; and CD ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry.

To provide for interaction with a user, one or more aspects of the disclosure can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube), LCD (liquid crystal display) monitor, or touch screen for displaying information to the user. In certain implementations, interaction is facilitated by a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user can provide input to the computer. Other kinds of devices can be used to provide interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback, e.g., visual feedback, auditory feedback, or tactile feedback; and input from the user can be received in any form, including acoustic, speech, or tactile input. In addition, a computer can interact with a user by sending documents to and receiving documents from a device that is used by the user; for example, by sending web pages to a web browser on a user's client device in response to requests received from the web browser.

A number of implementations have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the disclosure. For example, while processes or blocks are presented in a given order, alternative embodiments may perform routines having steps, or employ systems having blocks, in a different order, and some processes or blocks may be deleted, moved, added, subdivided, combined, and/or modified. Each of these processes or blocks may be implemented in a variety of different ways. Also, while processes or blocks are at times shown as being performed in series, these processes or blocks may instead be performed in parallel, or may be performed at different times. Furthermore, the elements and acts of the various embodiments described above can be combined to provide further embodiments. Indeed, the methods and systems described herein may be embodied in a variety of other forms; furthermore, various omissions, substitutions and changes in the form of the methods and systems described herein may be made without departing from the spirit of the disclosure. Accordingly, other implementations are within the scope of the following claims.