DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 102
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale or otherwise available to the public before the effective filing date of the claimed invention.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 1-7, 9-20 are rejected under 35 U.S.C. 102(a)(1) and/or 102(a)(2) as being anticipated by Ebrahimi Afrouzi et al. (US 20220066456 A1; hereinafter Ebrahimi).
Regarding claim 1, Ebrahimi discloses a computer-implemented method for controlling a character (title, Abstract), the method comprising:
performing one or more operations to solve for a two-dimensional (2D) path through a scene (…robot to drive along a trajectory that follows along a planned path …Abstract,
In some embodiments, existence of an open space is hypothesized for some grid size, a path is planned within that hypothesized grid space, from the original point, grids are covered moving along the path planned within the hypothesized space, ¶0576.);
performing one or more operations to refine at least one portion of the 2D path based on one or more heights of one or more obstacles within the scene to generate a three-dimensional (3D) path (In some embodiments, the map may be a state space with possible values for x, y, z. In some embodiments, a value of x and y may be a point on a Cartesian plane on which the robot drives and the value of z may be a height of depth of cliffs, ¶0940.
For example, FIG. 188 illustrates a path 10300 traversable by the robot as all the values of z (indicative of height) within the cells are five and the particular wheel dimensions and mechanical characteristics of the robot allow the robot to overcome areas with a z value of five. FIG. 189 illustrates another example of a traversable path 10400. In this case, the path is traversable as the values of z increase gradually, making the area climbable (or traversable) by the robot. FIG. 190 illustrates an example of a path 10500 that is not traversable by the robot because of the sudden increase in the value of z between two adjacent cells. FIG. 191 illustrates an adjustment to the path 10500 illustrated in FIG. 140 that is traversable by the robot. FIG. 192 illustrates examples of areas traversable by the robot 10700 because of gradual incline/decline or the size of the wheel 10701 of the robot 10700 relative to the area in which a change in height is observed. FIG. 193 illustrates examples of areas that are not traversable by the robot 10700 because of gradual incline/decline or the size of the wheel 10701 of the robot 10700 relative to the area in which a change in height is observed. In some embodiments, the z value of each cell may be positive or negative and represent a distance relative to a ground zero plane, ¶1149.
The transition from the hard floor with a height of zero and the carpet with a height of one may be deemed a traversable path, ¶1332);
…computing one or more velocities of the character along the 3D path to generate a first path that includes the one or more velocities (FIG. 44 illustrates an example of a velocity map, according to some embodiments, ¶0051.
…controls robot speed, and executes the coverage algorithm using, for example, RTOS or Bare-metal. With the advancement of SLAM and HW cost reduction, path planning, localization, and mapping are possible with the use of a CPU, GPU, NPU, etc, ¶0249.
In some embodiments, the processor uses reinforcement learning to learn a speed at which to reduce the probability of the location being occupied by the object. For example, after initialization at a seed value, the processor observes whether the robot collides with vanishing objects and may decrease a speed at which the probability of the location being occupied by the object is reduced if the robot collides with vanished objects, ¶0381.
In some embodiments, the processor may generate a velocity map based on multiple images taken from multiple cameras at multiple time stamps, wherein objects do not move with the same speed in the velocity map. Speed of movement is different for different objects depending on how the objects are positioned in relation to the cameras, ¶0512.
In a velocity motion model, the translational velocity at time t0 may be denoted with V.sub.t and the rotational velocity during a same duration may be denoted by Wt, ¶0538
In some embodiments, PID may be used to smoothen the curve on the function ƒ′(x) representing trajectory and minimize deviation from the path that is planned f(x) (in the context of straight movement only). In some embodiments, a trajectory f′(x) of the robot may be smoothed to minimize its deviation from the planned path f(x). In embodiments, the movement and velocity of the camera may be correlated to the wheels. For example, two cameras on two sides of the robot, their velocities V1 and V2, and observations follow the trajectory of each of the two wheels., ¶0539); and
causing the character to perform an action based on the first path (ibid, Abstract, ¶0512, ¶0539).
Regarding claim 2, Ebrahimi discloses the computer-implemented method of claim 1, further comprising, responsive to determining that the character has reached a goal or will collide with a first obstacle based on an estimated movement of the first obstacle and the first path, performing one or more operations to generate a second path through the scene (…the processor avoids collisions between the robot and objects (including dynamic objects such as humans and pets) using sensors and a perceived path of the robot … For example, a robot transporting passengers may execute a predetermined path by following observed marking on the road or by driving on a rail and may use sensor data and perceived information during operation to avoid collisions with objects, ¶0414
Upon identifying an object in an image as an object from the object dictionary different responses may be enacted (e.g., altering a movement path to avoid colliding with or driving over the object). For example, once the processor identifies objects, the processor may alter the navigation path of the robot to drive around the objects and continue back on its path, ¶1193).
Regarding claim 3, Ebrahimi discloses the computer-implemented method of claim 1, wherein the one or more operations to solve for the 2D path are based on a textual instruction (In some embodiments, the user may also add labels and other annotations to the plan, ¶0361) and information about the scene that indicates at least one of one or more heights within the scene (In some embodiments, the map may be a state space with possible values for x, y, z. In some embodiments, a value of x and y may be a point on a Cartesian plane on which the robot drives and the value of z may be a height of obstacles or depth of cliffs, ¶0940), one or more landmarks within the scene (The processor uses sensor data to continuously detect and follow markings. In some embodiments, the robot executes the path using digital landmarks positioned along the path, ¶0414), or the one or more obstacles within the scenes (The darker paths 4612 used in navigating from one coverage box to the next and for robust coverage are planned offline, wherein the algorithm plans the navigation path ahead of time before the robot executes the path and the path planned is based on obstacles already known in the global map, ¶0936).
Regarding claim 4, Ebrahimi discloses the computer-implemented method of claim 1, wherein the one or more operations to solve for the 2D path negatively weight larger height differences along the 2D path (In some embodiments, the value associated with each cell may be used to determine a location of the cell in a planar surface along with a height from a ground zero plane. In some embodiments, a plane of reference (e.g., x-y plane) may be positioned such that it includes a lowest point in the map. In this way, all vertical measurements (e.g., z values measured in a z-direction normal to the plane of reference) are always positive. In some embodiments, the processor of the robot may adjust the plane of reference each time a new lower point is discovered and all vertical measurements accordingly. In some embodiments, the plane of reference may be positioned at a height of the work surface at a location where the robot begins to perform work and data may be assigned a positive value when an area with an increased height relative to the plane of reference is discovered (e.g., an inclination or bump) and assigned a negative value when an area with a decreased height relative to the plane of reference is observed, ¶0940).
Regarding claim 5, Ebrahimi discloses the computer-implemented method of claim 1, wherein the one or more operations to solve for the 2D path include one or more operations of an A* algorithm, and a cost function of the A* algorithm accounts for one or more height differences (In some embodiments, the value associated with each cell may be used to determine a location of the cell in a planar surface along with a height from a ground zero plane. In some embodiments, a plane of reference (e.g., x-y plane) may be positioned such that it includes a lowest point in the map. In this way, all vertical measurements (e.g., z values measured in a z-direction normal to the plane of reference) are always positive. In some embodiments, the processor of the robot may adjust the plane of reference each time a new lower point is discovered and all vertical measurements accordingly. In some embodiments, the plane of reference may be positioned at a height of the work surface at a location where the robot begins to perform work and data may be assigned a positive value when an area with an increased height relative to the plane of reference is discovered (e.g., an inclination or bump) and assigned a negative value when an area with a decreased height relative to the plane of reference is observed, ¶0940).
Regarding claim 6, Ebrahimi discloses the computer-implemented method of claim 1, wherein the one or more operations to refine the at least one portion of the 2D path is further based on the character (Concurrently, the robot may use reinforcement learning for a task such as its calibration, obstacle inflation, bump reduction, path optimization, etc., ¶0313.
This continuous process fine tunes the SLAM and control of the robot over time. At each time sequence, data from the controller, SLAM and path planning algorithms, and the reward system of trajectory measurement and observation algorithm are transmitted to the database for input into the Deep Q-Network for reinforcement learning, ¶0343).
Regarding claim 7, Ebrahimi discloses the computer-implemented method of claim 1, wherein the one or more velocities of the character along the 3D path are computed to minimize a motion time of the character and to adhere to one or more constraints ( …controls robot speed, and executes the coverage algorithm using, for example, RTOS or Bare-metal. With the advancement of SLAM and HW cost reduction, path planning, localization, and mapping are possible with the use of a CPU, GPU, NPU, etc., ¶0249
In some embodiments, the processor uses reinforcement learning to learn a speed at which to reduce the probability of the location being occupied by the object. For example, after initialization at a seed value, the processor observes whether the robot collides with vanishing objects and may decrease a speed at which the probability of the location being occupied by the object is reduced if the robot collides with vanished objects, ¶0381).
Regarding claim 9, Ebrahimi discloses the computer-implemented method of claim 1, wherein causing the character to perform the action comprises generating the action via a trained machine learning model and based on a state of the character, the first path, and a height map, wherein the action comprises a first type of motion included in a plurality of types of motions for which the trained machine learning model is trained to generate actions (¶0261, 0271, 0307, 0313, 0343, 0794, 1150, 1156, 1198 …etc.).
Regarding claim 10, Ebrahimi discloses the computer-implemented method of claim 1, wherein the character is one of a three-dimensional (3D) virtual character or a physical robot (abstract, title).
Regarding claim 11, Ebrahimi discloses one or more non-transitory computer-readable media storing instructions that, when executed by at least one processor, cause the at least one processor to perform the steps of (¶0735, 0838, 0865, 1506):
performing one or more operations to solve for a two-dimensional (2D) path through a scene; performing one or more operations to refine at least one portion of the 2D path based on one or more heights of one or more obstacles within the scene to generate a three-dimensional (3D) path; computing one or more velocities of the character along the 3D path to generate a first path that includes the one or more velocities; and causing the character to perform an action based on the first path (see substantively similar claim 1 rejection above).
Regarding CRM claim(s) 12-15, 19 although wording is different, the material is considered substantively equivalent to the method claim(s) 2-3, 5, 7, 9 as described above.
Regarding claim 16, Ebrahimi discloses the one or more non-transitory computer-readable media of claim 15, wherein the one or more constraints include at least one of a speed limit (In some embodiments, the processor uses reinforcement learning to learn a speed at which to reduce the probability of the location being occupied by the object, ¶0381.
While an IMU may detect an inertial acceleration after the robot has accelerated a desired cruise speed, ¶0448.
In the position state, this may correspond to the robot reaching a wall, and in the velocity state, it may correspond to the motor limit, ¶1042), an acceleration constraint (While an IMU may detect an inertial acceleration after the robot has accelerated a desired cruise speed, the accelerometer may not be helpful in detecting motion with a constant speed, ¶0448; The second robot vehicle may decide to wait, drive around the first robot vehicle, accelerate, or instruct the first robot vehicle to stop, ¶1271), or a curvature constraint (¶0825).
Regarding claim 17, Ebrahimi discloses the one or more non-transitory computer-readable media of claim 11, wherein the three-dimensional (3D) path avoids the one or more obstacles (…the processor avoids collisions between the robot and objects (including dynamic objects such as humans and pets) using sensors and a perceived path of the robot … For example, a robot transporting passengers may execute a predetermined path by following observed marking on the road or by driving on a rail and may use sensor data and perceived information during operation to avoid collisions with objects, ¶0414.
Upon identifying an object in an image as an object from the object dictionary different responses may be enacted (e.g., altering a movement path to avoid colliding with or driving over the object). For example, once the processor identifies objects, the processor may alter the navigation path of the robot to drive around the objects and continue back on its path, ¶1193).
Regarding claim 18, Ebrahimi discloses the one or more non-transitory computer-readable media of claim 11, wherein performing one or more operations to refine the at least one portion of the 2D path comprises re-weighting a connectivity graph associated with the 2D path based on a slope (In some embodiments, the control system computes the next driving action of a robotic chassis navigating from a first location to a second location by determining the shortest path in the directed, weighted graph. In other embodiments, the weight assigned to an edge depends on one or more other variables such as, traffic within close proximity of the edge, obstacle density within close proximity of the edge, road conditions, number of available charged robotic chassis within close proximity of the edge, number of robotic chassis with whom linking is possible within close proximity of the edge, etc., ¶1492.
In some embodiments, the processor may identify an edge as a location in the image at which the gradient is especially high in a first direction and low in a second direction normal to the first direction, ¶1345).
Regarding claim 20, Ebrahimi discloses a system, comprising:
one or more memories storing instructions; and one or more processors that are coupled to the one or more memories and, when executing the instructions, are configured to (¶0735, 0838, 0865, 1506):
perform one or more operations to solve for a two-dimensional (2D) path through a scene, perform one or more operations to refine at least one portion of the 2D path based on one or more heights of one or more obstacles within the scene to generate a three-dimensional (3D) path, compute one or more velocities of the character along the 3D path to generate a first path that includes the one or more velocities, and cause the character to perform an action based on the first path (see substantively similar claims 1 and 10 rejection above).
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102 of this title, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim 8 is rejected under 35 U.S.C. 103 as being unpatentable over Ebrahimi in view of Li (US 20220163969 A1).
Regarding claim 8, Ebrahimi discloses the computer-implemented method of claim 1, except, further comprising storing the first path using a k-dimensional tree.
However, Li discloses optimizing route plan of a robot (title, abstract), wherein a tree type data structure saves the planned path (¶0053, During analysis, the system comes across the existing planned route for A. So, for planning routes for B, the system optimizes the route by avoiding the routes already planned in A. This tree structure of the routes planned is stored in the path coordinator 204 and queried by the system to get information on already planned routes as part of the analysis process. After route B is planned, the tree structure within the path coordinator 204 resembles FIG. 3(A) till the construction of node B. Inside each node, starting root node to node B, the information stored in the path coordinator 204 is not restricted to only the paths. In the path coordinator 204, the system also stores information like statistics of the plan, for example—how much time and how long does a route takes, other information like details related to an unavoidable collision, for example, with A, etc., ¶0047).
Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention (AIA ) to modify the invention of Ebrahimi with the teaching of Li of building a k-dimensional data structure during developing route planning to store potential routes, to obtain, storing the first path using a k-dimensional tree, because, combining prior art elements ready to be improved according to known method to yield predictable results is obvious.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to NURUN FLORA whose telephone number is (571)272-5742. The examiner can normally be reached M-F 9:30 am -5:00 pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Jason Chan can be reached at (571) 272-3022. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/NURUN FLORA/Primary Examiner, Art Unit 2619