Patent Description:
Robotic devices, such as robotic legs and arms, may include various components or attachments that are designed to interact with the environment. Such components may include robotic feet and hands, which may include additional components that can be used to support, stabilize, grip, and otherwise allow a robotic device to effectively carry out one or more actions.

In particular, robotic arms may include one or more "end effectors" that interact with the environment. For example, end effectors may be impactive (such as a claw), ingressive (such as a pin or needle), astrictive (such as a vacuum or suction element) or contigutive (requiring contact for adhesion, such as glue).

"Self-supervised learning for docking and target reaching" (Jeremy R. Cooperstock, Evangelos E. Milios) discloses a robotic system using simple visual processing and controlled by neural networks. The robot performs docking and target reaching without prior geometric calibration of its components. All effects of control signals on the robot are learned by the controller through visual observation during a training period, and refined during actual operation. Various operations including approaching, centering, paralleling, reaching and adjusting are performed by the robot as it navigates towards the target. The robot attempts to grasp targets that are sufficiently close, or approach them while avoiding collisions with obstacles.

In the course of performing operations in a physical environment, a robot may move its manipulator or aspects thereof (e.g., its end effector) to a plurality of different interaction points (e.g., locations from which to pick up or at which to drop-off an object). In order to reach one or more of these interaction points, the robot may determine a position for its base that allows the manipulator to reach the interaction point without the manipulator or other parts of the robot colliding with physical features of the environment. To that end, the robot utilizes a pre-trained model (e.g., a machine learning model such as an artificial neural network) to determine candidate positions within the environment based on a height map representation thereof. These candidate positions are predicted to allow the robot to plan a collisions-free trajectory for parts of the robot, including the manipulator, for reaching the interaction point. One or more of these candidate positions may be selected by the robot to validate that a collision-free trajectory can, in fact be planned therefrom. Following successful validation, the robot may move to the selected candidate position to operate on the interaction point.

The pre-trained model was trained using a plurality of sample height maps each associated with one or more validated positions. The validated position in the sample height maps may be calculated off-line (e.g., prior to real-time robotic operation), allowing for determination of a complete set of positions from which a collision-free trajectory can be planned. The pre-trained model may take less time to determine candidate positions for a new height map than it would take to determine the complete set of validated positions for this height map. Nevertheless, the pre-trained model may inherently possess the insights gained from the off-line calculations of validated positions.

In addition to the illustrative aspects, embodiments, and features described above, further aspects, embodiments, and features will become apparent by reference to the figures and the following detailed description and the accompanying drawings.

Example methods, devices, and systems are described herein. It should be understood that the words "example" and "exemplary" are used herein to mean "serving as an example, instance, or illustration. " Any embodiment or feature described herein as being an "example" or "exemplary" is not necessarily to be construed as preferred or advantageous over other embodiments or features unless indicated as such. Other embodiments can be utilized, and other changes can be made, without departing from the scope of the appended claims.

Thus, the example embodiments described herein are not meant to be limiting. It will be readily understood that the aspects of the present disclosure, as generally described herein, and illustrated in the figures, can be arranged, substituted, combined, separated, and designed in a wide variety of different configurations.

Throughout this description, the articles "a" or "an" are used to introduce elements of the example embodiments. Any reference to "a" or "an" refers to "at least one," and any reference to "the" refers to "the at least one," unless otherwise specified, or unless the context clearly dictates otherwise. The intent of using the conjunction "or" within a described list of at least two terms is to indicate any of the listed terms or any combination of the listed terms.

The use of ordinal numbers such as "first," "second," "third" and so on is to distinguish respective elements rather than to denote a particular order of those elements. For purpose of this description, the terms "multiple" and "a plurality of" refer to "two or more" or "more than one.

Thus, the figures should be generally viewed as component aspects of one or more overall aspects, with the understanding that not all illustrated features are necessary for each embodiment. In the figures, similar symbols typically identify similar components, unless context dictates otherwise. Further, unless otherwise noted, figures are not drawn to scale and are used for illustrative purposes only. Moreover, the figures are representational only and not all components are shown. For example, additional structural or restraining components might not be shown.

Robotic devices are used to perform a number of different tasks ranging from assembling automobiles to assisting with various routine household jobs. Many applications, such as automobile assembly or semiconductor manufacturing, involve the robots repeatedly performing the same tasks in a predictable environment. Namely, while performing such tasks, the base of robot may be stationary or allowed to traverse the environment in a predefined manner (e.g., on rails). However, robots are being increasingly used in different, less predictable environments to perform various operations that involve traversing these environments. Many robots are thus mobile and capable of moving through such environments in a manner that is not predefined. For example, the same mobile robot may be used by two different end-users to perform similar tasks in two different environments, each requiring the robot to plan different paths through the respective environment. Additionally, even robots operating in the same general location may be faced with changes in the environment of this location over time, necessitating that the robots adapt to these changes.

Picking up, moving, dropping off, holding, and/or adjusting a position of an object are common operations in many robotic tasks. Interacting with the object in this way by a mobile robot involves moving or repositioning the base of the mobile robot to a position that makes the object accessible to a manipulator (e.g., an arm and an end effector) of the robot. Specifically, the base should be positioned such that (i) an interaction point (e.g., pick-up or drop-off location) within the environment is reachable by the manipulator and (ii) the base, the manipulator, and other parts of the robot do not collide with the environment as the manipulator follows a trajectory to reach the interaction point within the environment. Conventionally, determining the position for the base (i.e., the region to be occupied by the base) involves iteratively selecting and checking different possible positions within the environment until a satisfactory position is found. However, such a guess-and-check approach is computationally expensive and thus time consuming. Namely, the guess-and-check approach may slow down operations of the robot, making the robot unsuitable for certain tasks and/or appear indecisive or hesitant while performing other tasks.

Accordingly, provided herein are techniques for determining, by way of a pre-trained model, candidate positions within an environment from which the robotic device can reach an interaction point without any collisions. Specifically, the model was trained based on a plurality of sample height maps that represent different physical environments containing therein respective interaction points for the robotic device. In some examples, the height maps may be two-dimensional (2D) height maps. In alternative examples, the height maps may be three-dimensional (3D) voxel grids, among other possibilities. An example physical environment may include, for example, a desk and a cup disposed thereon for pickup by the robot, with the position of the cup representing the interaction point. However, many other physical environments and interaction points are possible. The model may be, for example, an artificial neural network (ANN) or another machine learning model, particularly one that is well-adapted for 2D image to 2D image mapping.

Each of the sample height maps in the training data is processed by one or more algorithms to identify therein corresponding validated positions that, when occupied by the base of the robot, allow the manipulator of the robot to follow a collision-free trajectory to the interaction point within the environment. Specifically, a collision-free trajectory may define a path for the manipulator and aspects thereof such that no part of the robotic device is determined to collide with or come within a threshold distance of any objects in or feature of the environment (aside from the object being manipulated or interacted with). The validated positions may be represented as one or more regions or areas within the corresponding height map. This processing may take place off-line before the robot uses the model (thus making the model a "pre-trained" model) and thus may be allowed to take more time than similar processing would be allowed to take in real-time robotic operation. Notably, the processing may identify every feasible position within a given height map, thus providing a more complete training set for the pre-trained model.

The model is then trained using the plurality of height maps and the interaction points within these height maps (representing possible inputs), and the validated positions (representing corresponding correct outputs) determined off-line for each of these height maps. Thus, following training, the trained model is configured to determine candidate positions within additional height maps that represent surfaces in physical environments that the model has not previously encountered or trained on. Specifically, the pre-trained model is configured to provide as output a plurality of candidate positions for each new combination of (i) height map and (ii) interaction point provided thereto as input. The output of the pre-trained model may additionally indicate, for each of the plurality of candidate positions, a corresponding confidence level indicating how likely, according to the model, the robot is to plan a collision-free trajectory for that candidate position.

The robot thus uses the pre-trained model to plan the approach path and position of its mobile base when reaching for an interaction point within a new physical environment. Namely, the robot receives sensor data that represents the new physical environment and the interaction point therein. The robot determines, based on this sensor data, a corresponding height map representative of surfaces within the new physical environment. When multiple surfaces are present at different heights at a same horizontal position, the height map may represent, for example, surfaces that fall within a particular height range. For example, the height map may represent surfaces that are (i) below a maximum reach height of the manipulator and (ii) above a minimum height that is based on the height of the interaction point (e.g., several inches below a surface from which the robot is to pick up an object).

This height map and the interaction point are then provided as input to the pre-trained model, which generates as output candidate positions within the new physical environment. These candidate positions are predicted to allow the robot, if positioned therein, to reach the interaction point without collisions. The robot selects a candidate position. For example, the robot may select the candidate position with the highest corresponding confidence level for evaluation. That is, the robot might not assume that this candidate position will allow a collision-free trajectory to be planned. Instead, the robot may attempt to determine a collision-free trajectory for the manipulator to follow from this candidate position to validate the adequacy of this candidate position.

Notably, the collision-free trajectory may be planned based on a 3D representation of the environment. Thus, when the height map is represented in 2D, the trajectory planning may nevertheless be carried out in three dimensions using a 3D model of the same physical environment.

If a collision-free trajectory can be found for the selected candidate position, the base of the robot is caused to move to this position at which it may pick up the object by following the collision-free trajectory. Alternatively, if a collision-free trajectory cannot be found for the selected candidate position, the robot may select another candidate position to test for whether a collision-free trajectory may be determined therefor. Accordingly, the pre-trained model may reduce the time it takes the robot to find a position from which to pick up the object by predicting the positions most likely to work in view of the different environments used to train the model. Notably, this approach may allow the robot to operate faster, and thus appear more confident, than an approach based on, for example, random selection of candidate positions, a methodical analysis of all possible positions, or another rule-based selection of candidate positions within a new environment.

The pre-trained model may also be used to identify conditions in which a collision-free trajectory is not available. Namely, when the pre-trained model is provided with a height map and an interaction point that are unlike the training data, the pre-trained model might not determine any candidate positions, thereby indicating that the interaction point is unreachable to the manipulator. For example, the pre-trained model might not determine any candidate positions when the interaction point is outside of the range of heights represented by the height map. In such cases, the robotic device may revert to an alternative process for identifying a position from which a collision-free trajectory can be followed (e.g., guess-and-check approach, which may be perceptibly slower), or might forego interaction with the specified interaction point.

In some cases, rather than waiting until a collision-free trajectory is planned before repositioning the mobile base, the robot may advance towards the highest-confidence position. That is, validation of the availability of at least one collision-free trajectory at this highest-confidence position may occur while the robot advances towards it. In another example, the robot may move according to a gradient of the confidence values across the candidate positions. Namely, the robot may move in a direction corresponding to the highest increase in confidence between its current position and any adjacent positions. Thus, this approach allows the pick-up operation to take less time, or at least make the robot appear more confident in its actions.

The pre-trained model may additionally be trained on, configured to take as input, and generate its output based on additional information that defines the operation to be carried out at the interaction point (e.g., object pick-up, object drop-off, object holding) or environmental conditions. In one example, the pre-trained model may be configured to determine candidate positions based on the pose (i.e., position and orientation) of an object to be picked up from the interaction point. In another example, the pre-trained model may be configured to determine candidate positions based on a path of a tool or end effector of the manipulator involved in picking up the object. For example, given a cup to be picked up by a handle thereof using a gripper, the gripper may need to approach the cup from a particular direction and in a particular orientation in order to grasp the handle. In a further example, the pre-trained model may be configured to determine candidate positions based on a physical structure of the robot involved in picking up the object.

When the pre-trained model is an ANN, the structure thereof may include an input layer, an output layer, and one or more hidden layers. The hidden layers may include one or more general layers that are object-independent, task-independent, and/or robot-independent. That is, these general layers may determine candidate positions without accounting for attributes of the object (e.g., shape, size, orientation), attributes of the task (e.g., pick-up vs drop-off), and/or attributes of the robot (e.g., size, degrees of freedom, gripper type, etc.).

The hidden layers may also include one or more additional layers that are specific to a particular object, task, and/or robot. These additional layers may thus operate to filter the results generated by the general layers, selecting candidate positions predicted to work best for a particular object, task, or robot. By structuring the ANN in this way, the ANN may be quickly adapted to new objects, tasks, and/or robots without needing to be entirely retrained using a large amount of new training data. Instead, a new object-specific, task-specific, and/or-robot-specific layer may be trained and added upstream of the general layers. Notably, such training may use fewer training samples than would be necessary to retrain the entire network.

<FIG> illustrates an example configuration of a robotic system that may be used in connection with the implementations described herein. Robotic system <NUM> may be configured to operate autonomously, semi-autonomously, or using directions provided by user(s). Robotic system <NUM> may be implemented in various forms, such as a robotic arm, industrial robot, or some other arrangement. Furthermore, robotic system <NUM> may also be referred to as a robot, robotic device, or mobile robot, among other designations.

As shown in <FIG>, robotic system <NUM> may include processor(s) <NUM>, data storage <NUM>, and controller(s) <NUM>, which together may be part of control system <NUM>. Robotic system <NUM> may also include sensor(s) <NUM>, power source(s) <NUM>, mechanical components <NUM>, and electrical components <NUM>. Nonetheless, robotic system <NUM> is shown for illustrative purposes, and may include more or fewer components. The various components of robotic system <NUM> may be connected in any manner, including wired or wireless connections. Further, in some examples, components of robotic system <NUM> may be distributed among multiple physical entities rather than a single physical entity. Other example illustrations of robotic system <NUM> may exist as well.

Processor(s) <NUM> may operate as one or more general-purpose hardware processors or special purpose hardware processors (e.g., digital signal processors, application specific integrated circuits, etc.). Processor(s) <NUM> may be configured to execute computer-readable program instructions <NUM>, and manipulate data <NUM>, both of which are stored in data storage <NUM>. Processor(s) <NUM> may also directly or indirectly interact with other components of robotic system <NUM>, such as sensor(s) <NUM>, power source(s) <NUM>, mechanical components <NUM>, or electrical components <NUM>.

Data storage <NUM> may be one or more types of hardware memory. For example, data storage <NUM> may include or take the form of one or more computer-readable storage media that can be read or accessed by processor(s) <NUM>. The one or more computer-readable storage media can include volatile or non-volatile storage components, such as optical, magnetic, organic, or another type of memory or storage, which can be integrated in whole or in part with processor(s) <NUM>. In some implementations, data storage <NUM> can be a single physical device. In other implementations, data storage <NUM> can be implemented using two or more physical devices, which may communicate with one another via wired or wireless communication. As noted previously, data storage <NUM> may include the computer-readable program instructions <NUM> and data <NUM>. Data <NUM> may be any type of data, such as configuration data, sensor data, or diagnostic data, among other possibilities.

Controller <NUM> may include one or more electrical circuits, units of digital logic, computer chips, or microprocessors that are configured to (perhaps among other tasks), interface between any combination of mechanical components <NUM>, sensor(s) <NUM>, power source(s) <NUM>, electrical components <NUM>, control system <NUM>, or a user of robotic system <NUM>. In some implementations, controller <NUM> may be a purpose-built embedded device for performing specific operations with one or more subsystems of the robotic device <NUM>.

Control system <NUM> may monitor and physically change the operating conditions of robotic system <NUM>. In doing so, control system <NUM> may serve as a link between portions of robotic system <NUM>, such as between mechanical components <NUM> or electrical components <NUM>. In some instances, control system <NUM> may serve as an interface between robotic system <NUM> and another computing device. Further, control system <NUM> may serve as an interface between robotic system <NUM> and a user. In some instances, control system <NUM> may include various components for communicating with robotic system <NUM>, including a joystick, buttons, or ports, etc. The example interfaces and communications noted above may be implemented via a wired or wireless connection, or both. Control system <NUM> may perform other operations for robotic system <NUM> as well.

During operation, control system <NUM> may communicate with other systems of robotic system <NUM> via wired or wireless connections, and may further be configured to communicate with one or more users of the robot. As one possible illustration, control system <NUM> may receive an input (e.g., from a user or from another robot) indicating an instruction to perform a particular gait in a particular direction, and at a particular speed. A gait is a pattern of movement of the limbs of an animal, robot, or other mechanical structure.

Based on this input, control system <NUM> may perform operations to cause the robotic device <NUM> to move according to the requested gait. As another illustration, a control system may receive an input indicating an instruction to move to a particular geographical location. In response, control system <NUM> (perhaps with the assistance of other components or systems) may determine a direction, speed, or gait based on the environment through which robotic system <NUM> is moving en route to the geographical location.

Operations of control system <NUM> may be carried out by processor(s) <NUM>. Alternatively, these operations may be carried out by controller <NUM>, or a combination of processor(s) <NUM> and controller <NUM>. In some implementations, control system <NUM> may partially or wholly reside on a device other than robotic system <NUM>, and therefore may at least in part control robotic system <NUM> remotely.

Mechanical components <NUM> represent hardware of robotic system <NUM> that may enable robotic system <NUM> to perform physical operations. As a few examples, robotic system <NUM> may include physical members such as leg(s), arm(s), wheel(s), track(s), hand(s), digit(s), feet, or end effectors. The physical members or other parts of robotic system <NUM> may further include actuators arranged to move the physical members in relation to one another. Robotic system <NUM> may also include one or more structured bodies for housing control system <NUM> or other components, and may further include other types of mechanical components. The particular mechanical components <NUM> used in a given robot may vary based on the design of the robot, and may also be based on the operations or tasks the robot may be configured to perform.

In some examples, mechanical components <NUM> may include one or more removable components. Robotic system <NUM> may be configured to add or remove such removable components, which may involve assistance from a user or another robot. For example, robotic system <NUM> may be configured with removable digits, arms, hands, feet, or legs, so that these appendages can be replaced or changed as needed or desired. In some implementations, robotic system <NUM> may include one or more removable or replaceable battery units or sensors. Other types of removable components may be included within some implementations.

Robotic system <NUM> may include sensor(s) <NUM> arranged to sense aspects of robotic system <NUM>. Sensor(s) <NUM> may include one or more force sensors, torque sensors, velocity sensors, acceleration sensors, position sensors, proximity sensors, motion sensors, location sensors, load sensors, temperature sensors, touch sensors, depth sensors, ultrasonic range sensors, infrared sensors, object sensors, or cameras, among other possibilities. Within some examples, robotic system <NUM> may be configured to receive sensor data from sensors that are physically separated from the robot (e.g., sensors that are positioned on other robots or located within the environment in which the robot is operating).

Sensor(s) <NUM> may provide sensor data to processor(s) <NUM> (perhaps by way of data <NUM>) to allow for interaction of robotic system <NUM> with its environment, as well as monitoring of the operation of robotic system <NUM>. The sensor data may be used in evaluation of various factors for activation, movement, and deactivation of mechanical components <NUM> and electrical components <NUM> by control system <NUM>. For example, sensor(s) <NUM> may capture data corresponding to the terrain of the environment or location of nearby objects, which may assist with environment recognition and navigation.

In an example configuration, sensor(s) <NUM> may include RADAR (e.g., for long-range object detection, distance determination, or speed determination), LIDAR (e.g., for short-range object detection, distance determination, or speed determination), SONAR (e.g., for underwater object detection, distance determination, or speed determination), VICON® (e.g., for motion capture), one or more cameras (e.g., stereoscopic cameras for 3D vision), a global positioning system (GPS) transceiver, or other sensors for capturing information of the environment in which robotic system <NUM> is operating. Sensor(s) <NUM> may monitor the environment in real time, and detect obstacles, elements of the terrain, weather conditions, temperature, or other aspects of the environment. In another example, sensor(s) <NUM> may capture data corresponding to one or more characteristics of a target or identified object, such as a size, shape, profile, structure, or orientation of the object.

Further, robotic system <NUM> may include sensor(s) <NUM> configured to receive information indicative of the state of robotic system <NUM>, including sensor(s) <NUM> that may monitor the state of the various components of robotic system <NUM>. Sensor(s) <NUM> may measure activity of systems of robotic system <NUM> and receive information based on the operation of the various features of robotic system <NUM>, such as the operation of extendable legs, arms, or other mechanical or electrical features of robotic system <NUM>. The data provided by sensor(s) <NUM> may enable control system <NUM> to determine errors in operation as well as monitor overall operation of components of robotic system <NUM>.

As an example, robotic system <NUM> may use force sensors to measure load on various components of robotic system <NUM>. In some implementations, robotic system <NUM> may include one or more force sensors on an arm, leg, hand, foot, or digit to measure the load on the actuators that move one or more members of the arm, leg, hand, foot, or digit. As another example, robotic system <NUM> may use one or more position sensors to sense the position of the actuators of the robotic system. For instance, such position sensors may sense states of extension, retraction, positioning, or rotation of the actuators on arms, legs, hands, feet, digits, or end effectors.

As another example, sensor(s) <NUM> may include one or more velocity or acceleration sensors. For instance, sensor(s) <NUM> may include an inertial measurement unit (IMU). The IMU may sense velocity and acceleration in the world frame, with respect to the gravity vector. The velocity and acceleration sensed by the IMU may then be translated to that of robotic system <NUM> based on the location of the IMU in robotic system <NUM> and the kinematics of robotic system <NUM>.

Robotic system <NUM> may include other types of sensors not explicitly discussed herein. Additionally or alternatively, the robotic system may use particular sensors for purposes not enumerated herein.

Robotic system <NUM> may also include one or more power source(s) <NUM> configured to supply power to various components of robotic system <NUM>. Among other possible power systems, robotic system <NUM> may include a hydraulic system, electrical system, batteries, or other types of power systems. As an example illustration, robotic system <NUM> may include one or more batteries configured to provide charge to components of robotic system <NUM>. Some of mechanical components <NUM> or electrical components <NUM> may each connect to a different power source, may be powered by the same power source, or be powered by multiple power sources.

Any type of power source may be used to power robotic system <NUM>, such as electrical power or a gasoline engine. Additionally or alternatively, robotic system <NUM> may include a hydraulic system configured to provide power to mechanical components <NUM> using fluid power. Components of robotic system <NUM> may operate based on hydraulic fluid being transmitted throughout the hydraulic system to various hydraulic motors and hydraulic cylinders, for example. The hydraulic system may transfer hydraulic power by way of pressurized hydraulic fluid through tubes, flexible hoses, or other links between components of robotic system <NUM>. Power source(s) <NUM> may charge using various types of charging, such as wired connections to an outside power source, wireless charging, combustion, or other examples.

Electrical components <NUM> may include various mechanisms capable of processing, transferring, or providing electrical charge or electric signals. Among possible examples, electrical components <NUM> may include electrical wires, circuitry, or wireless communication transmitters and receivers to enable operations of robotic system <NUM>. Electrical components <NUM> may interwork with mechanical components <NUM> to enable robotic system <NUM> to perform various operations. Electrical components <NUM> may be configured to provide power from power source(s) <NUM> to the various mechanical components <NUM>, for example. Further, robotic system <NUM> may include electric motors. Other examples of electrical components <NUM> may exist as well.

Although not shown in <FIG>, robotic system <NUM> may include a body, which may connect to or house appendages and components of the robotic system. As such, the structure of the body may vary within examples and may further depend on particular operations that a given robot may have been designed to perform. For example, a robot developed to carry heavy loads may have a wide body that enables placement of the load. Similarly, a robot designed to reach high speeds may have a narrow, small body that does not have substantial weight. Further, the body or the other components may be developed using various types of materials, such as metals or plastics. Within other examples, a robot may have a body with a different structure or made of various types of materials.

The body or the other components may include or carry sensor(s) <NUM>. These sensors may be positioned in various locations on the robotic device <NUM>, such as on the body or on one or more of the appendages, among other examples.

On its body, the robotic device <NUM> may carry a load, such as a type of cargo that is to be transported. The load may also represent external batteries or other types of power sources (e.g., solar panels) that the robotic device <NUM> may utilize. Carrying the load represents one example use for which the robotic device <NUM> may be configured, but the robotic device <NUM> may be configured to perform other operations as well.

As noted above, robotic system <NUM> may include various types of legs, arms, wheels, tracks, end effectors, gripping devices and so on. In general, robotic system <NUM> may be configured with zero or more legs. An implementation of the robotic system with zero legs may include wheels, treads, tracks, or some other form of locomotion. An implementation of the robotic system with two legs may be referred to as a biped, and an implementation with four legs may be referred as a quadruped. Implementations with six or eight legs are also possible. For purposes of illustration, robotic arm implementations of robotic system <NUM> are described below.

<FIG> shows an example robotic arm <NUM>. As shown, robotic arm <NUM> includes a base <NUM>, which may be a stationary base or may be a movable base. In the case of a movable base, the base <NUM> may be considered as one of mechanical components <NUM> and may include wheels (not shown), powered by one or more of actuators, which allow for mobility of the entire robotic arm <NUM>.

Additionally, robotic arm <NUM> includes joints 204A-204F each coupled to one or more actuators. The actuators in joints 204A-204F may operate to cause movement of various mechanical components <NUM> such as appendages 206A-206F or end effector <NUM>. For example, the actuator in joint 204F may cause movement of appendage 206F and end effector <NUM> (i.e., since end effector <NUM> is coupled to appendage 206F). Further, end effector <NUM> may take on various forms and may include various parts. In one example, end effector <NUM> may take the form of a gripper such as a digit gripper as shown here or a different type of gripper such as a suction gripper. In another example, end effector <NUM> may take the form of a tool such as a drill or a brush. In yet another example, the end effector may include sensors such as force sensors, location sensors, or proximity sensors. Other examples may also be possible.

<FIG> illustrates an example robotic device <NUM> that may be involved in the performance of the operations herein described. Robotic device <NUM> may be an example implementation of robotic system <NUM> or a variation of robotic arm <NUM>. Thus, some of the operations described herein as being performed by robotic device <NUM> may be carried out by, for example, control system <NUM> thereof.

Robotic device <NUM>, or robot for short, includes base <NUM> which includes wheels that allow base <NUM> to reposition robot <NUM> within an environment. Robot <NUM> also includes manipulator <NUM> (e.g., an arm) connected at a first end thereof to base <NUM>. End effector <NUM> (e.g., a gripper) is connected to a second end of manipulator <NUM>. Manipulator <NUM> may be configured to move with a plurality of degrees of freedom (e.g., <NUM> degrees of freedom) to interact with various objects. Robot <NUM> may also include head <NUM> that houses therein one or more sensors used to measure (e.g., perceive or observe) various aspects of the environment. However, sensors may also be disposed in other parts of robot <NUM> such as, for example, an area between the fingers (i.e., the palm) of a gripper that makes up end effector <NUM>.

Robot <NUM> may be configured to perform various tasks in a plurality of different physical environments. Each environment may include therein a plurality of different surfaces defined by physical items such as floors, walls, desks, chairs, and shelves, among others, that collectively make up the topography of the environment. <FIG>, for example, illustrates table <NUM> that has a tabletop surface on which cup <NUM> is disposed.

Performance of the various tasks in the environments may involve interacting with, operating on, or operating nearby specific locations within the environments. These specific locations may be referred to as interaction points. That is, an interaction point may be a location within the environment that manipulator <NUM> or end effector <NUM> thereof is to reach in order to perform one or more operations within the environment. The tasks may involve placing an object at an interaction point, picking-up an object from an interaction point, and/or holding an object nearby or at the interaction point, among other possibilities. For example, robot <NUM> may be configured to pick-up cup <NUM> from the specific location (i.e., the interaction point) on the tabletop surface of table <NUM> and move cup <NUM> to another location (e.g., garbage can or dishwasher).

To that end, robot <NUM> may be configured to scan the environment using one or more of its sensors (e.g., in head <NUM>), as illustrated by field of view <NUM>. The sensors may generate, among other possibilities, perception data in the form of one or more of image data, depth data, or a combination thereof. Based on sensor data generated during this scan, robot <NUM> may be configured to determine a height map of the environment. The height map may indicate a plurality of heights of surfaces within the environment. For example, the height map may indicate the height of the tabletop of table <NUM>, cup <NUM>, and the floor around table <NUM>.

The height map may be represented in multiple different ways. In one example, the height map may be a two-dimensional (2D) height map that represents a top-down view of the environment. The 2D height map may be represented as a grid, with each element, or cell, of the grid corresponding to an area within the environment. Each respective cell may be associated with a value that indicates the height of a surface in the corresponding area within the environment. The different heights represented by the 2D height map may be visually indicated with a grayscale or color image, where each shade of grey or color, respectively, represents a particular discrete height value. Notably, <FIG> illustrates a height map of an example environment shown in <FIG>.

In another example, the height map may be a three-dimensional height map. For example, the 3D height map may be a voxel grid, where each voxel indicates whether a volume of the environment represented thereby is occupied or unoccupied. Thus, the 3D height map may be able to indicate multiple different heights at each horizontal position within the environment. For example, the 3D height map may indicate that the tabletop of table <NUM> is at a first height and the floor is at a second height below the tabletop. Other implementations of the height map are possible. Notably, in some implementations, even when the height map is 2D, a 3D representation of the environment may nevertheless be determined for use in planning of the trajectory of manipulator <NUM>.

Once the height map is determined, robot <NUM> may identify or designate therein the interaction point associated with one or more operations. For example, robot <NUM> may identify the position of cup <NUM> as an interaction point associated with picking up cup <NUM>. In order to reach cup <NUM>, robot <NUM> may need to satisfy at least two conditions. First, robot <NUM> may need to identify a position that base <NUM> can occupy within a threshold distance of the interaction point so that the interaction point is within reach of manipulator <NUM>. Notably, base <NUM> needs to be able to move to this position from its current location. Second, robot <NUM> may need to determine a collision-free trajectory for moving end effector <NUM> (or another part of manipulator <NUM>) to the interaction point while base <NUM> is so positioned. The trajectory of manipulator <NUM> may define a path in space for end effector <NUM> and one or more portions of manipulator <NUM>. In some implementations, the trajectory may additionally define the velocity and acceleration at one or more points along the path. The trajectory may be determined under the constraint that it is achievable (i.e., physically reachable) by manipulator <NUM>, among other parts of robot <NUM>.

Conventionally, a position for base <NUM> may be identified by iteratively selecting a test position within the physical environment to evaluate for whether the interaction point will be reachable without any collisions if base <NUM> is disposed at this tests position. That is, a test position may be guessed and then checked for suitability in planning a collision-free trajectory. Specifically, robot <NUM> may attempt to plan one or more trajectories for reaching the interaction point while assuming that base <NUM> will be disposed at the test position while the trajectories are executed. If at least one of the one or more trajectories is collision-free, the test position may be selected for occupancy by base <NUM>. If not, another test position may be selected for evaluation. When a test position is found that allows for the interaction point to be reached without any collisions when base <NUM> is disposed at this tests position, robot <NUM> may be moved to this position and manipulator <NUM> may be actuated to follow the collision-free trajectory to reach the interaction point.

The test position may be selected using heuristics or other rule-based algorithms. For example, any position within the threshold distance of the interaction point that is unoccupied may be selectable as a test position. Positions that form part of large unoccupied regions may be selected for testing before positions that form part of smaller unoccupied regions. In another example, test positions may be selected randomly. In a further example, test positions may be selected in a predetermined fashion (e.g., starting from the bottom left corner of the height map and moving right and upwards). Other approaches are possible.

Notably, due to the variety of possible physical environments in which robot <NUM> may operate, a rule-based algorithm might not be able to quickly and accurately identify feasible positions in such a range of environments. Random or methodical selection of test positions may face a similar problem. Thus, before a satisfactory position is found, multiple different unsatisfactory positions may be evaluated. Evaluating multiple positions in this manner is a computationally-intensive and time-consuming process, especially where a large number of test positions needs to be evaluated before finding a satisfactory position. As a result, the robot may take a long time to find a satisfactory position (e.g., more than ten seconds) and perform a given task. Additionally, a robot operating in this manner may slow down or stop moving until a satisfactory test position is identified. As a result, the robot may appear hesitant or lacking in confidence, which may result in any humans operating in a shared environment with this robot lacking confidence in the robot's abilities and being uncomfortable working with the robot.

Accordingly, <FIG> illustrates a system for more accurately and quickly determining candidate positions for base <NUM> of robot <NUM> that allow manipulator <NUM> to reach an interaction point within an environment. The system of <FIG> utilizes pre-trained model <NUM> to determine candidate positions within the physical environment that are most likely to allow robot <NUM> to plan a collision-free trajectory for reaching an interaction point within the environment. Thus, rather than evaluating multiple test positions whose likelihood of success might not be known, the system of <FIG> allows robot <NUM> to start the evaluation with candidate positions that are most likely to yield satisfactory results.

The system of <FIG> includes pre-trained model <NUM> and manipulator trajectory planner <NUM>. Pre-trained model <NUM> may be an artificial intelligence (AI) algorithm, a machine learning (ML) algorithm, or another algorithm capable of learning based on prior examples or other feedback. An example implementation of pre-trained model <NUM> is illustrated in and described with respect to <FIG>. An example training procedure for configuring model <NUM> to determine candidate positions is illustrated in and described with respect to <FIG>. Pre-trained model <NUM> is configured to identify candidate positions <NUM> (i.e., candidate position <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>) based at least on interaction point <NUM> and height map <NUM>. In some implementations, pre-trained model <NUM> may additionally be configured to base the determination of candidate positions <NUM> on robot structure <NUM> of the robotic device for which planning is to be carried out.

Interaction point <NUM> may define one or more of coordinates <NUM>, interaction type <NUM>, and object pose <NUM>. Coordinates <NUM> may define, for example, the x-position, y-position, and z-position of interaction point <NUM>. Interaction type <NUM> may indicate that an object is to be picked-up from coordinates <NUM>, an object is to be dropped-off at coordinates <NUM>, or an object is to be held at coordinates <NUM> (e.g., a paint nozzle is to be positioned at the interaction point to paint a nearby object), among other possibilities. Object pose <NUM> may define an orientation in which the object is currently disposed at interaction point <NUM>, or an orientation in which the object is expected to be disposed or held at interaction point <NUM>. Interaction point <NUM> may thus dictate where, how, and how long manipulator <NUM> or end effector <NUM> should be positioned to complete the operation associated with interaction point <NUM>.

Height map <NUM> may be a 2D or 3D representation of surfaces within the physical environment that contains interaction point <NUM> for robot <NUM>. Accordingly, coordinates <NUM> may define a position within or with respect to height map <NUM>. As discussed above, height map <NUM> may be determined by robot <NUM> based on sensor data from sensors on robot <NUM>. Notably, height map <NUM> may represent an environment that has not been used to train pre-trained model <NUM>.

Robot structure <NUM> may include one or more of end effector structure <NUM>, base structure <NUM>, and manipulator structure <NUM>. End effector structure <NUM> may indicate a type, size, and arrangement of aspects of end effector <NUM>, among other attributes. For example, end effector type <NUM> may indicate that end effector <NUM> is an actuated gripper, an underactuated gripper, or a suction gripper, among other possibilities. Base structure <NUM> may indicate a size of base <NUM> and a type of mechanism used for locomotion thereof (e.g., wheels, tracks, etc.), among other attributes. Manipulator structure <NUM> may indicate the number of degrees of freedom of manipulator <NUM>, a length of manipulator <NUM> of the different linkages thereof, or a reach of manipulator <NUM>, among other attributes thereof.

In some implementations, pre-trained model <NUM> may be specific to a first robot and thus robot structure <NUM> might not need to be provided to pre-trained model <NUM>. That is, pre-trained model may be trained to determine candidate positions <NUM> on the assumption that the first robot, having a specific physical structure, will be operating on the interaction point. In this case, some variation in the structure of a second robot from that of the first robot might not adversely impact the ability of pre-trained model <NUM> to accurately identify candidate positions <NUM> for the second robot. However, as the structure of the second robot deviates more significantly from that of the first robot (e.g., beyond a threshold difference as measured, for example, by the reach of the respective manipulators), candidate positions <NUM> might become less accurate for the second robot. For example, the second robot, having a shorter reach and fewer degrees of freedom than the first robot, might not be able to access the interaction point from some candidate positions that would otherwise work for the first robot due to its longer reach and additional degrees of freedom.

Accordingly, as an alternative, pre-trained model <NUM> may be configured to determine candidate positions <NUM> for a plurality of different robots having a plurality of different structures. Thus, pre-trained model <NUM> may utilize robot structure <NUM> in making this determination. For example, a first stage or module of pre-trained model may determine a plurality of candidate positions that would be suitable for a plurality of different robotic structures. A second stage or module may then select, from the plurality of candidate positions, a subset expected to be specifically suitable for a robot having structure <NUM>. In such an implementation, adapting pre-trained model <NUM> to a new robot may involve re-training the second stage or module, rather than re-training the entirety of pre-trained model <NUM>.

In some implementations, each of candidate positions <NUM> may be associated with a corresponding confidence value indicating how likely a given candidate position is to allow a collision-free trajectory to be planned for manipulator <NUM>. Additionally or alternatively to explicitly providing a confidence value, pre-trained model may sort candidate positions <NUM> from most likely to least likely to allow a collision-free trajectory to be planned.

Manipulator trajectory planner <NUM> may be configured to receive one or more of candidate positions <NUM> as input and attempt to plan a collision-free trajectory for manipulator <NUM> given that base <NUM> will be disposed at the one or more of candidate positions <NUM>. When pre-trained model <NUM> indicates the confidence value associated with each of candidate positions <NUM>, or sorts positions <NUM>, trajectory planner <NUM> may be configured to start planning with the candidate position most likely to succeed. For example, given that candidate positions <NUM> - <NUM> are arranged in order of decreasing confidence values, trajectory planner would first select candidate position <NUM> for testing. Trajectory planner would then plan and simulate one or more candidate trajectories for manipulator <NUM> moving relative to base <NUM> positioned at candidate position <NUM>. Trajectory planner <NUM> may be configured to check whether any portion of robot <NUM> intersects with or comes within a threshold distance of (i.e., collides with) any features within the physical environment (e.g., as represented by the sensor data or a model generated based thereon) at a plurality of different points along the one or more candidate trajectories.

If any of the one or more candidate trajectories are determined to be collision-free, candidate position <NUM> may be selected as a successful position <NUM> to be executed in the physical environment. On the other hand, if none of the one or more candidate trajectories are found to be collision-free, candidate position <NUM> may be determined to be a colliding position <NUM>. Trajectory planner <NUM> may be configured to then select for evaluation candidate position <NUM> which has the next highest confidence value.

Thus, although a given candidate position might not allow for a collision-free trajectory to be planned, the number of candidate trajectories needed to be tested before a satisfactory one is found may be reduced relative to conventional position planning operations. Notably, the system of <FIG> may be able to evaluate approximately <NUM> - <NUM> candidate positions in under <NUM> second, and at least one of these <NUM> - <NUM> candidate positions may be likely to yield a collision-free trajectory. Thus, the system of <FIG> may be able to identify a collision-free trajectory in less than one tenth of the time taken by conventional position planning operations, which may take upwards of <NUM> seconds to identify a collision-free trajectory.

Once successful position <NUM> is determined by pre-trained model <NUM> and verified by trajectory planner <NUM>, robot <NUM> may be caused to move to successful position <NUM> and execute one of the planned collision-free trajectories. In one example, robot <NUM> may be caused to move to successful position <NUM> after determining that a collision-free trajectory is available therefor. That is, assuming candidate position <NUM> (but not <NUM>) is determined to be successful position <NUM>, movement of robot <NUM> might not be directed at candidate position <NUM> until candidate position <NUM> is verified by trajectory planner <NUM>. Alternatively, robot <NUM> may be caused to first move towards candidate position <NUM> before or while candidate position <NUM> is evaluated by trajectory planner <NUM>. When candidate position <NUM> is found to be unsuitable, robot <NUM> may be redirected towards candidate position <NUM>. That is, robot <NUM> may be cause to move towards the candidate position with the highest confidence value until this candidate position is found to be a colliding position.

In an alternative implementation, robot <NUM> may be caused to move according to a gradient of confidence values across candidate positions <NUM>. The gradient may be computed for a given candidate position by determining the difference in confidence values between the given candidate position and neighboring candidate positions (e.g., candidate positions above, below, left, and right of the given candidate position). The neighboring candidate positions may be directly adjacent to one another or may be separated from one another by one or more positions within the physical environment that are not selected as candidate positions. Robot <NUM> may be caused to move from its current position in a direction associated with a highest value of the gradient (i.e., a highest increase in confidence associated among candidate positions <NUM>).

The gradient may be periodically recomputed as (i) additional sensor data is received that results in an update to height map <NUM>, candidate positions <NUM>, and the respective confidence values associated with candidate positions <NUM>, and (ii) one or more of candidate positions <NUM> are found to be colliding by trajectory planner <NUM>. By causing robot <NUM> to move according to the gradient, robot <NUM> may be directed towards candidate positions that have an increasingly higher probability of yielding collision-free trajectories.

By advancing robot <NUM> either according to the gradient or towards a candidate position with the highest confidence value, robot <NUM> may appear to be more capable and confident than a robot that stands in place while searching for a suitable position for base <NUM>. Additionally, by relying on pre-trained model <NUM>, robot <NUM> might change how it approaches the interaction point only a few times (e.g., once after determining that candidate position <NUM> is unsuitable) and, notably, this chance in direction might be small enough so as to be imperceptible or appear to be part of normal operation of the robot, contrary to a long pause while robot <NUM> looks for a position using conventional methods.

<FIG> illustrates a top-down view of an example physical environment in which robot <NUM> may be configured to operate. Physical environment <NUM> includes wall <NUM> that defines a boundary of physical environment <NUM>. Environment <NUM> also includes therein table <NUM> having disposed thereon cup <NUM> with which robot <NUM> is to interact (e.g., pick up the cup), and chairs <NUM> and <NUM> disposed to the left of table <NUM>. As described with respect to <FIG>, robot <NUM> may use one or more sensors to scan environment <NUM>. Based on the sensor data received from the sensors during this scan, robot <NUM> may determine a height map of environment <NUM>, as illustrated in <FIG>.

<FIG> illustrates environment <NUM> as a 2D height map that subdivides environment <NUM> according to a grid. The different surfaces present in environment <NUM> are illustrated using different patterns at the corresponding elements (i.e., squares, pixels, or cells) of the grid. Each pattern additionally indicates a height of the corresponding surface. Namely, table <NUM>, the tabletop of which is positioned at a first height, is illustrated using first pattern <NUM> (i.e., cross-hatching) at the corresponding grid elements. Similarly, the seats of chairs <NUM> and <NUM>, which are positioned at a second height, are illustrated using two instances <NUM> and <NUM> of a second pattern (i.e., one-directional hatching). The backs of chairs <NUM> and <NUM>, which are positioned at a third height, are illustrated using two instances of a third pattern (i.e., a fine grid). Wall <NUM>, which extends from the floor to the ceiling, is illustrated using a fourth pattern <NUM> (i.e., solid black color). Cup <NUM>, which is positioned at a fifth height, is illustrated using a fifth pattern <NUM> (i.e., black dotted with white). Finally, the floor of environment <NUM>, which is positioned at a sixth height, is illustrated using a sixth pattern (i.e., solid white color).

In some cases, environment <NUM> may include, at a particular horizontal position, two or more different objects at two or more different heights. For example, the horizontal region occupied by table <NUM> may include the floor at the sixth height and the tabletop of table <NUM> at the first height. Alternatively or additionally, a chandelier may be suspended above table <NUM> at a seventh height. In such instances, the height map may be generated by filtering out one or more of the physical features when generating the height map. For example, objects below a first height threshold (other than the floor) and above a second height threshold might not be included in the height map. The second height threshold may be defined, for example, based on a reach of manipulator <NUM>. Thai is, surfaces that manipulator <NUM> cannot reach need not be represented in the height map as no collisions therewith are possible. The first height threshold may be defined based on the height of the interaction point. That is, the first height threshold may be a particular distance below the height of the interaction point.

When two objects fall within the first and second height thresholds, the height map may represent, for example, the one having the greater height (e.g., pattern <NUM>, representing cup <NUM>, is shown in the middle of pattern <NUM> representing table <NUM>). Alternatively, in some cases, a modified height map may be used to store multiple height values for each horizontal grid position (e.g., akin to a red-green-blue image, rather than a grayscale image), thereby allowing multiple heights to be accounted for by the height map at each grid position. Notably, such a modified height map may be used to represent objects whose height falls outside of the of the first or second threshold.

The height map of environment <NUM> may be provided to pre-trained model <NUM> in order to determine therein one or more candidate positions for base <NUM>. <FIG> illustrates an example output of pre-trained model <NUM>. The output includes three different regions <NUM>, <NUM>, and <NUM> that collectively define the plurality of candidate positions for base <NUM> or a portion thereof. <FIG> illustrates regions <NUM>, <NUM>, and <NUM> superimposed on the image of environment <NUM> to show how the output of pre-trained model <NUM> corresponds with physical environment <NUM>. Notably, regions <NUM>, <NUM>, and <NUM> are regions around table <NUM> that are not occupied by chairs <NUM> and <NUM>. Additionally, occupancy of regions <NUM>, <NUM>, and <NUM> by base <NUM> places cup <NUM> within reach of manipulator <NUM>. Circle <NUM> approximately outlines the area from within which cup <NUM> may be within reach of manipulator <NUM> (although it does not indicate that all regions of this area are occupiable by base <NUM> or that a collision-free trajectory could be planned thereat).

A candidate position may include one or more of the grid elements of regions <NUM>, <NUM>, and <NUM>. In one implementation, each grid element of the height map may be sized to be smaller than the width or length of base <NUM>. For example, each grid element may be between <NUM> and <NUM> centimeters while mobile base <NUM> has a length of approximately <NUM> centimeters (e.g., +/- <NUM> centimeters). A candidate position may be defined by one of the grid elements under the assumption that a particular portion of mobile base <NUM> will occupy the corresponding physical location. The particular position may be, for example, a center of mobile base <NUM>, a center of a front axle thereof, or a center of a rear axle thereof, among other possibilities.

Each grid element may therefore be associated with a corresponding confidence value. Notably, the confidence value may be conditioned upon the particular portion (e.g., center) of mobile base <NUM> occupying the corresponding physical position. That is, if mobile base <NUM> is positioned such that the particular portion (e.g., center) thereof occupies the candidate position (i.e., the grid element), the confidence value of that grid element may be an accurate representation of the actual likelihood of determining a collision-free trajectory therefrom. On the other hand, if mobile base <NUM> is positioned such that a different portion (e.g., front axle) thereof occupies the candidate position, the confidence value of that grid element might not be an accurate representation of the actual likelihood of determining a collision-free trajectory therefrom.

In another implementation, a candidate position may be defined by a plurality of grid elements that approximate or outline the shape of base <NUM>. For example, rectangular region <NUM> may approximate or outline the length and width of base <NUM>. Thus, region <NUM> may be considered a candidate position. On the other hand, region <NUM> may include therein multiple different candidate positions. That is, there are multiple ways to fit a 2x3 rectangle inside region <NUM>. In this implementation, the confidence value for each candidate position (comprised of multiple grid elements) may be represented by the sum, average, or some other function of the confidence values associated with the individual grid elements. For example, the confidence value of the candidate position defined by region <NUM> may be the sum of the confidence values associated with each grid element thereof. Thus, depending on the implementation, the output of pre-trained model <NUM> may need to be further processed to determine the confidence value associated with each candidate position.

In a further implementation, each grid element of the height map may be sized to approximate the length or width of base <NUM>. Thus, each grid element of regions <NUM>, <NUM>, and <NUM> may represent a region able to fit therein the entirety of at least one of the length of width of base <NUM>. In such a case, each grid element may be associated with a corresponding confidence value.

Notably, regions <NUM>, <NUM>, and <NUM> of <FIG> are shown in black, while other aspects of these figures are shaded white, for clarity of illustration and not necessarily to indicate that pre-trained model <NUM> is configured to generate, for each grid element, a binary output. Instead, for example, each grid element of regions <NUM>, <NUM>, and <NUM> may have a corresponding confidence value that is above a threshold value (e.g., <NUM>%) and may therefore be shaded black. Thus, grid elements that are shaded white may also, in some cases, constitute candidate positions, albeit with lower confidence values. Additionally, depending on how candidate regions are related to the grid elements (e.g., how many grid elements make up a candidate position), the shape of regions <NUM>, <NUM>, and/or <NUM> and/or the confidence values associated with the grid elements may be different than shown.

<FIG> illustrates an example artificial neural network (ANN) <NUM> that may make up pre-trained model <NUM>. Notably, neural networks are well-adapted to generating transformations between two images (e.g., generating image of candidate positions based on height map). ANN <NUM> may include input nodes <NUM>, <NUM>, and <NUM> that form part of input layer <NUM> of ANN <NUM> and are configured to accept inputs x<NUM> and x<NUM> through xn, respectively. In some embodiments, the number of inputs n may be equal to the sum of elements in the data that makes up (i) interaction point <NUM>, (ii) height map <NUM>, and (iii) robot structure <NUM> (when ANN <NUM> is not robot-specific). For example, height map <NUM> may be represented as a 2D image comprising M columns and N rows of pixels. Each of the M x N pixels may be associated with a corresponding value representing the height. Accordingly, ANN <NUM> may be configured to take height map <NUM> as input using M x N input nodes.

In another example, height map <NUM> may be provided to ANN <NUM> in the form of a 3D voxel grid having a height M, a width N, and a depth K. Each voxel of the 3D height map may be associated with a <NUM> value (voxel unoccupied) or a <NUM> value (voxel occupied). Accordingly, ANN <NUM> may be configured to take height map <NUM> as input using M x N x K input nodes. In further examples, ANN <NUM> may accept height map <NUM> formatted in different ways. Additionally, interaction point <NUM>, robot structure <NUM>, and other possible inputs may be provided as inputs by allocating one input node to each data element thereof. For example, coordinates <NUM> representing an x-position, a y-position, and a z-height may be allocated <NUM> additional input nodes.

ANN <NUM> may additionally include a plurality of hidden nodes that form part of one or more hidden layers <NUM> and <NUM>. Hidden nodes <NUM>, <NUM>, <NUM>, <NUM> and <NUM> may form first hidden layer <NUM> while hidden nodes <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> may form second hidden layer <NUM>. In some examples, ANN <NUM> may include additional hidden nodes and additional hidden layers not shown herein. The number of hidden nodes and hidden layers may be determined empirically during training of ANN <NUM> to achieve an ANN that determines candidate positions with a satisfactory accuracy (i.e., an accuracy greater than a threshold accuracy).

Notably, the terms "hidden node" and "hidden layer" are used herein to designate nodes and layers, respectively, located between the input and output layers of the ANN. These and similar terms are not to be construed as implying that values, functions, or other properties associated with the hidden nodes or layers are necessarily unknown or hidden.

ANN <NUM> may further include output nodes <NUM>, <NUM>, and <NUM> that form part of an output layer <NUM> of ANN <NUM>. Output nodes <NUM>, <NUM>, and <NUM> may be configured to provide outputs y<NUM>, y<NUM>, and ym, respectively. When the output of ANN <NUM> is a 2D image, the number of outputs m may be equal to the number of pixels in this image. The value associated with each pixel may represent, for example, the probability of successfully planning a collision-free trajectory if base <NUM> or a portion thereof is disposed at the corresponding location within the physical environment.

The nodes of ANN <NUM> may be connected with one another, as illustrated by the arrows in <FIG>. For example, input nodes <NUM> - <NUM> may be connected to hidden nodes <NUM> - <NUM> of the first hidden layer <NUM> (i.e., input layer <NUM> may be connected to hidden layer <NUM>), hidden nodes <NUM> - <NUM> may be connected to hidden nodes <NUM> - <NUM> of the second hidden layer <NUM> (i.e., hidden layer <NUM> may be connected to hidden layer <NUM>), and hidden nodes <NUM> - <NUM> may be connected to output nodes <NUM> - <NUM> (i.e., hidden layer <NUM> may be connected to output layer <NUM>). In some embodiments, each node of a layer may be connected to each node within a subsequent layer (e.g., node <NUM> may be connected to each of nodes <NUM> - <NUM>). Alternatively, some nodes within a layer may be unconnected to one or more nodes within a subsequent layer. Some nodes may additionally be provided with a constant bias signal (not shown).

One or more of the hidden nodes may represent feature filters configured to filter the input sensor data for specific features (e.g., vertical lines, horizontal lines, curves, edges, etc.). The filters may become increasingly complex, filtering for higher-order features (e.g., tables, chairs, shelves, floors, etc.), as the hidden nodes of ANN <NUM> are traversed. In one example, hidden layer <NUM> may be configured to identify a plurality of positions that are not specific to a particular robot structure, interaction type, or object pose, among other factors. Hidden layer <NUM> may be configured to select therefrom candidate positions specific to a robotic device with a particular physical structure, a particular type of interaction, or a particular object pose, among other factors. Thus, updating ANN <NUM> to a robot with a new physical structure or a new type of interaction task may involve retraining hidden layer <NUM>, but without needing to retrain the other layers <NUM>, <NUM>, and <NUM>.

In further embodiments, nodes within a layer may be connected back to nodes within a previous layer or within the same layer. For example, node <NUM> within layer <NUM> may be connected to node <NUM> within prior layer <NUM> by way of connection <NUM>. In another example, node <NUM> within layer <NUM> may be connected to at least one of nodes <NUM>, <NUM>, <NUM>, or <NUM> within layer <NUM> (not shown). Thus, ANN <NUM> may include feedback that creates internal state within the network. This type of ANN may be referred to as a recurrent artificial neural network (RANN). Notably, an ANN without any feedback paths may be referred to as a feedforward artificial neural network (FF-ANN).

Each connection between nodes of ANN <NUM> may be associated with a respective weighting value. A given node may receive inputs a<NUM>, a<NUM>, through ak. Each of inputs a<NUM>, a<NUM>, through ak may be associated with corresponding weighting values w<NUM>, w<NUM>, through wk, respectively. The given node may operate by first taking the sum of the respective products of each input multiplied by the corresponding weighting value. The given node may thus compute the sum φ = w<NUM>a<NUM> + w<NUM>a<NUM> +. The sum φ may then be passed through an activation function to produce the output of the given node. Example activation functions may include a linear activation function where the node output is linearly proportional to the sum φ, a Gaussian activation function where the node output is normally distributed along a bell curve according to the sum φ, a sigmoidal activation function where the sum φ is mapped to a bounded range of node outputs, or a Rectified Linear Units (RELu) function where the node output is max (<NUM>, φ).

In some embodiments, ANN <NUM> may be or may include therein aspects of a convolutional artificial neural network (CANN). For example, ANN <NUM> may include pooling layers (i.e., downsampling layers) between layers <NUM>, <NUM>, <NUM>, and <NUM>. Further, ANN <NUM> may additionally include aspects of probabilistic neural networks, time-delay neural networks, regulatory feedback neural networks, and spiking neural networks, among other types of neural networks not herein discussed.

The output of the given node may be provided as input to other nodes within ANN <NUM>. At each respective node to which the output of the given node is connected, this output may be multiplied by a corresponding weighting value and summed along with other inputs to the respective node. For example, the output of node <NUM> may be provided to node <NUM>. The output of node <NUM> may be multiplied by a weighting value associated with the connection between node <NUM> and <NUM>. This product may then be summed at node <NUM> along with the product of the output of node <NUM> and the weighting value between node <NUM> and node <NUM>, the product of the output of node <NUM> and the weighting value between node <NUM> and node <NUM>, the product of the output of node <NUM> and the weighting value between node <NUM> and node <NUM>, and the product of the output of node <NUM> and the weighting value between node <NUM> and node <NUM>. The sum may be passed through an activation function to determine the output of node <NUM>. The output of node <NUM> may then be provided to nodes <NUM>, <NUM>, and <NUM>.

The weighting values between interconnected nodes may be determined by training ANN <NUM> based on a plurality of sample height maps containing respective interaction points and validated positions determined therefor, among other training data that may be associated therewith (e.g., data indicating the structure of the robot to which the validated positions correspond). The training of ANN <NUM> may be performed by, for example, backpropagation (e.g., classical backpropagation, backpropagation with momentum, Gauss-Jacobi backpropagation, Gauss-Seidel backpropagation, etc.).

Generally, ANN <NUM> may be configured to accept as input and determine candidate positions based on the type of data with which it is trained. Thus, for example, an ANN trained using a data set that includes (i) a plurality of height maps, (ii) validated positions within these height maps, (iii) designated interaction points within the height maps, and (iv) an indication of a structure of the robots for which a given validated position is satisfactory, may accept as input and determine candidate positions based on a height map having designated therein an interaction point and data indicating a physical structure of the robot for which the candidate positions are to be determined.

Notably, the trained ANN <NUM> may determine candidate positions within physical environments that it has not previously encountered or trained on. The ANN may determine candidate positions that, based on the training data, are similar to the validated positions in the sample height maps. For example, the ANN may determine candidate positions that are accessible by base <NUM>, large enough to accommodate the size of base <NUM>, and allow at least a threshold distance between objects with which manipulator <NUM> can collide, among other considerations.

<FIG> illustrates an example system for generating a pre-trained model (i.e., training the model). The system includes position validation module <NUM> and model trainer <NUM>. Position validation module <NUM> is configured to take as input sample height maps <NUM>, of which height map <NUM> is an example. Sample height maps <NUM> may represent a plurality of different environments, which may be real-world physical environments or simulated physical environments generated for the purpose of training the model. Sample height maps <NUM> may include, for example, <NUM>,<NUM> different height maps. Each of sample height maps <NUM> may contain therein one or more interaction points for a robot. Height map <NUM> illustrates an environment containing therein a table with an interaction point in the center thereof.

Position validation module may be configured to process sample height maps <NUM> off-line and identify therein validated positions <NUM>. Validated positions <NUM> may represent positions within the corresponding physical environment that, when occupied by a base of the robot, allow a manipulator of the robot to follow a collision-free trajectory to reach the interaction point in the corresponding physical environment. In some implementations, because validated positions <NUM> may be computed off-line (i.e., while the robotic device is not actively operating) with little to no time limit, the validated positions for a given sample height map may represent every possible base position that allows for a collision-free trajectory to be planned for the manipulator. That is, validated positions <NUM> may represents a complete solution set associated with sample height maps <NUM> and therefore provide a complete and accurate training set for model trainer <NUM>.

Grid <NUM> illustrates a set of validated positions corresponding to height map <NUM>. The validated positions are indicated by a dark shading of the corresponding grid elements. Similarly to <FIG>, the validated positions corresponding to height map <NUM> are found approximately within a circle having a radius defined by the reach of the manipulator. However, whereas the candidate positions shown in <FIG> are predicted to allow for a collision-free trajectory to be planned, the validated positions shown in grid <NUM> are guaranteed to allow for a collision-free trajectory to be planned. In other words, a position in grid <NUM> is labeled as a validated position after one or more collision-free trajectories are planned therefor, whereas a position in <FIG> is labeled as a candidate position when it is predicted that one or more collision-free trajectories may be planned therefor.

Position validation module <NUM> may identify validated positions <NUM> by determining, for each of sample height maps <NUM>, positions that are occupiable by the base of the robot, as indicated by block <NUM>. This may involve, for example, identifying regions within the height map that are (i) traversable by the base or the robot (e.g., have a height gradient that does not exceed a threshold value) and (ii) large enough to accommodate the base without colliding with other physical features (determined, e.g., by convolving the height map using a convolution kernel having a size that approximates the size of the base). For each of the occupiable positions determined at block <NUM>, position validation module <NUM> may then determine a plurality of candidate trajectories for the manipulator to follow to reach the respective interaction point, as indicated by block <NUM>. Trajectory planning may utilize any of a number of trajectory planning approaches such as polynomial fitting or genetic algorithms, among other possibilities.

From these candidate trajectories, position validation module <NUM> may identify trajectories that are collision-free, as indicated by block <NUM>. A trajectory may be collision-free when, while being followed by the manipulator, the manipulator, the end effector, and other portions of the robot (i) do not intersect with any features within the physical environment or (ii) do not come within a threshold distance of any features within the physical environment (aside from the interaction point). Notably, when sample height maps <NUM> are three-dimensional, planning and evaluation of the trajectories may be carried out using sample height maps <NUM>. Alternatively, when sample height maps <NUM> are two-dimensional, planning and evaluation of the trajectories may be carried out using 3D representations (not shown) of the environments represented by sample height maps <NUM>.

In some implementations, the operations of blocks <NUM> and <NUM> may be combined. That is, trajectory planning may be carried out with various constraints that result in avoidance of collisions, thereby resulting in any planned trajectories being free of collisions. Such an implementation thus might not be able to determine any trajectories under some conditions, indicating that no collision-free trajectories are available.

Additionally, in cases where pre-trained model <NUM> is specific to a robot having a particular physical structure, the operations of position validation module <NUM> may be specific to that robot. In cases where pre-trained model <NUM> is to take into account different physical structures of different robots, the operations of validation module <NUM> may be carried out for the different physical structures. There may thus be multiple sets of validated positions for each sample height map, with each set representing the validated positions that will allow a robot with a particular physical structure to reach the respective interaction point.

Once validated positions <NUM> are determined, validated positions <NUM> and sample height maps <NUM> may be provided as input to model trainer <NUM> to be used in generating pre-trained model <NUM>. Pre-trained model <NUM> may correspond to pre-trained model <NUM> of <FIG>. Generation, or training, of model <NUM> may involve selecting one or more types of algorithms to be used for model <NUM>, as indicated by block <NUM>. In one example, the model may be an ANN, as discussed with respect to <FIG>. However, model <NUM> may additionally or alternatively include a combination of one or more of linear regression, logistic regression, linear discriminant analysis, classification or decision trees, naive Bayes, k-nearest neighbors, learning vector quantization, support vector machines, random forests, and boosting, among other possibilities. These algorithms may be structured or combined into a pipeline, or series, that collectively carries out functions associated with predicting candidate positions within a variety of different environments. The types of algorithms and their arrangements may be user-specified or selected automatically by model trainer <NUM>.

Once the type and arrangement of algorithms is selected to form the general structure of the model, the algorithms that make up the model may be trained using sample height maps <NUM>, validated positions <NUM>, and other data (e.g., different possible robot physical structures) in order to determine the parameters that will result in the algorithms predicting candidate positions, as indicated by block <NUM>. In the case of an ANN, for example, the parameters may include the number of hidden layers and the weights associated with connections between nodes, which may be determined using, for example, backpropagation.

Once the parameters are determined, pre-trained model <NUM> may be evaluated using one or more test cases to determine whether pre-trained model <NUM> performs as expected, as indicated by block <NUM>. The test cases may include height maps with known validated positions but which have not been used during training. For example, evaluation of pre-trained model <NUM> may involve determining whether the model correctly predicts at least a threshold fraction of candidate positions in each of the test height maps or whether the model has a false-positive detection rate no larger than a threshold value. Other evaluation metrics are possible.

Once pre-trained model <NUM> is successfully evaluated, it may be used as part of the system of <FIG>. If pre-trained model <NUM> does not perform to a satisfactory standard, the operations of one or more of blocks <NUM> or <NUM> may be repeated to refine pre-trained model <NUM>.

In some embodiments, as robots operate in various physical environments, the sensor data gathered thereby may be used to generate additional sample height maps <NUM>. For example, robotic devices utilizing pre-trained model <NUM> may store various height maps used hereby to navigate. These height maps may be compiled and used to augment the size of the training data for pre-trained model <NUM>. In turn, model <NUM> may be periodically revised and adjusted based on this additional training data to make more accurate predictions. An updated version of pre-trained model <NUM> may be periodically provided to the robotic devices as part of a software update, for example.

<FIG> illustrates flow chart <NUM> of operations related to determining a position for a base of a robot that allows the robot to operate on a particular interaction point within an environment. The operations may be carried out by robotic system <NUM>, robotic arm <NUM>, robot <NUM>, control systems thereof, or other computing devices associated therewith. The operations may be similar to and may include variations of the operations discussed with respect to <FIG>.

Block <NUM> may involve receiving sensor data representative of surfaces in a physical environment containing an interaction point for a robotic device.

Block <NUM> may involve determining, based on the sensor data, a height map of the surfaces in the physical environment.

Block <NUM> involves determining, by inputting the height map and the interaction point into a pre-trained model, one or more candidate positions for a base of the robotic device to allow a manipulator of the robotic device to reach the interaction point.

Block <NUM> may involve determining a collision-free trajectory to be followed by the manipulator of the robotic device to reach the interaction point when the base of the robotic device is positioned at a selected candidate position of the one or more candidate positions.

Block <NUM> may involve, based on determining the collision-free trajectory, causing the base of the robotic device to move to the selected candidate position within the physical environment.

The pre-trained model was trained by operations that include determining a plurality of sample height maps each representing surfaces in a corresponding physical environment that contains therein a respective interaction point for the robotic device. The operations also include determining, for each of the plurality of sample height maps, one or more validated positions for the base that allow the manipulator to follow at least one collision-free trajectory to the respective interaction point. The operations further include determining, based on (i) the plurality of sample height maps, (ii) the one or more validated positions determined for each of the plurality of sample height maps, and (iii) the respective interaction point represented in each of the plurality of sample height maps, the pre-trained model.

In some embodiments, determining the one or more validated positions for the base of the robotic device comprises may include determining, for each of the plurality of sample height maps, a plurality of positions that (i) the robotic device can occupy within the corresponding physical environment and (ii) place the respective interaction point within reach of the manipulator. For each respective position of the plurality of positions, one or more candidate trajectories may be determined for the manipulator to follow to the respective interaction point while the base is disposed at the respective position. It may be determined that at least one of the one or more candidate trajectories is free of collisions. Based on determining that the at least one of the one or more candidate trajectories is free of collisions, the respective position may be selected as one of the one or more validated positions.

In some embodiments, the height map may be a two-dimensional height map. Determining the height map may include determining, based on the sensor data, a three-dimensional representation of the surfaces in the physical environment. From the three-dimensional representation of the surfaces, surfaces may be selected that are above a first height threshold and below a second height threshold. The second height threshold may be greater than the first height threshold. The two-dimensional height map may be generated based on the selected surfaces.

In some embodiments, the collision-free trajectory to be followed by the manipulator may be determined based on the three-dimensional representation of the surfaces in the physical environment.

In some embodiments, the height map may be a three-dimensional voxel grid. Each voxel may indicate whether a portion of the physical environment represented thereby is occupied.

In some embodiments, the pre-trained model may be configured to determine, for each of the one or more candidate positions, a corresponding confidence value. A first candidate position may be selected that has a highest corresponding confidence value of the one or more candidate positions. One or more candidate trajectories may be selected to be followed by the manipulator to reach the interaction point when the base is positioned at the first candidate position. It may be determined whether at least one of the one or more candidate trajectories is free of collisions. When the at least one of the one or more candidate trajectories is free of collisions, the collision-free trajectory to be followed by the manipulator may be selected from the at least one of the one or more candidate trajectories. When the at least one of the one or more candidate trajectories is not free of collisions, another candidate position may be selected for collision testing. The another candidate position may have a highest corresponding confidence value of any untested candidate positions of the one or more candidate positions.

In some embodiments, the pre-trained model may be configured to determine, for each of the one or more candidate positions, a corresponding confidence value. A candidate position having a highest corresponding confidence value of the one or more candidate positions may be selected. The base may be caused to move toward the selected candidate position before the collision-free trajectory to be followed by the manipulator is determined.

In some embodiments, the pre-trained model may be configured to determine, for each of the one or more candidate positions, a corresponding confidence value. A gradient of the corresponding confidence values across the one or more candidate positions may be determined. The gradient may define, for each pair of neighboring candidate positions of the one or more candidate positions, a difference between the corresponding confidence values of the neighboring candidate positions. Before determining the collision-free trajectory to be followed by the manipulator, the base may be caused to move in a direction associated with a highest value of the gradient.

In some embodiments, updated sensor data representative of the surfaces in the physical environment may be received. Based on the updated sensor data, an updated height map of the surfaces in the physical environment may be determined. An updated corresponding confidence value for each of the one or more candidate positions may be determined by inputting the updated height map into the pre-trained model. An updated gradient of the updated corresponding confidence values across the one or more candidate positions may be determined. A direction of motion of the base may be adjusted based on the updated gradient while determining the collision-free trajectory to be followed by the manipulator.

In some embodiments, the pre-trained model may be an artificial neural network (ANN).

In some embodiments, the ANN may include one or more first layers configured to determine a plurality of candidate positions for respective bases of a plurality of different robotic devices each having a different physical structure. The plurality of different robotic devices may include the robotic device. The ANN may also include one or more second layers configured to select, from the plurality of candidate positions, the one or more candidate positions for the base of the robotic device based on a physical structure of the robotic device.

In some embodiments, the pre-trained model may be further configured to determine the one or more candidate positions based on (i) a pose of an object disposed at the interaction point and (ii) a pose of an end effector connected to the manipulator and configured to interact with the object. Accordingly, the one or more candidate positions may be determined by inputting into the pre-trained model (i) the pose of the object disposed at the interaction point and (ii) the pose of the end effector connected to the manipulator and configured to interact with the object.

The present disclosure is not to be limited in terms of the particular embodiments described in this application, which are intended as illustrations of various aspects. Many modifications and variations can be made without departing from the scope of the claimed invention. Functionally equivalent methods and apparatuses within the scope of the disclosure, in addition to those enumerated herein, will be apparent to those skilled in the art from the foregoing descriptions. Such modifications and variations are intended to fall within the scope of the appended claims.

The above detailed description describes various features and functions of the disclosed systems, devices, and methods with reference to the accompanying figures. In the figures, similar symbols typically identify similar components, unless context dictates otherwise. The example embodiments described herein and in the figures are not meant to be limiting. It will be readily understood that the aspects of the present disclosure, as generally described herein, and illustrated in the figures, can be arranged, substituted, combined, separated, and designed in a wide variety of different configurations.

A block that represents a processing of information may correspond to circuitry that can be configured to perform the specific logical functions of a herein-described method or technique. Alternatively or additionally, a block that represents a processing of information may correspond to a module, a segment, or a portion of program code (including related data). The program code may include one or more instructions executable by a processor for implementing specific logical functions or actions in the method or technique. The program code or related data may be stored on any type of computer readable medium such as a storage device including a disk or hard drive or other storage medium.

The computer readable medium may also include non-transitory computer readable media such as computer-readable media that stores data for short periods of time like register memory, processor cache, and random access memory (RAM). The computer readable media may also include non-transitory computer readable media that stores program code or data for longer periods of time, such as secondary or persistent long term storage, like read only memory (ROM), optical or magnetic disks, compact-disc read only memory (CD-ROM), for example. The computer readable media may also be any other volatile or non-volatile storage systems. A computer readable medium may be considered a computer readable storage medium, for example, or a tangible storage device.

Moreover, a block that represents one or more information transmissions may correspond to information transmissions between software or hardware modules in the same physical device. However, other information transmissions may be between software modules or hardware modules in different physical devices.

It should be understood that other arrangements can include more or less of each element shown in a given figure. Yet further, examples can include elements that are not illustrated in the figures.

Claim 1:
A method comprising:
receiving sensor data representative of surfaces in a physical environment containing an interaction point for a manipulator (<NUM>) of a robotic device (<NUM>; <NUM>);
determining, based on the sensor data, a height map of the surfaces in the physical environment;
determining, by inputting the height map and the interaction point into a pre-trained model, a plurality of candidate positions (<NUM>) for a mobile base (<NUM>) of the robotic device within a region of the physical environment represented by the height map, wherein each respective candidate position of the plurality of candidate positions is predicted by the pre-trained model to allow the manipulator of the robotic device to reach the interaction point when the mobile base of the robotic device is positioned at the respective candidate position;
selecting a candidate position from the plurality of candidate positions;
determining a collision-free trajectory to be followed by the manipulator of the robotic device to reach the interaction point when the mobile base of the robotic device is positioned at the selected candidate position of the plurality of candidate positions; and
based on determining the collision-free trajectory, causing the mobile base of the robotic device to move to the selected candidate position within the physical environment, wherein the pre-trained model was trained by operations comprising:
determining a plurality of sample height maps each representing surfaces in a corresponding physical environment that contains therein a respective interaction point for the robotic device;
determining, for each of the plurality of sample height maps, one or more validated positions for the mobile base that allow the manipulator to follow at least one collision-free trajectory to the respective interaction point; and
determining, based on (i) the plurality of sample height maps, (ii) the one or more validated positions determined for each of the plurality of sample height maps, and (iii) the respective interaction point represented in each of the plurality of sample height maps, the pre-trained model.