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 .
Summary of claims
Claims1-4, 7-10, 12-14, 18-26 are pending
Claims 5, 6, 11, 15-17 are canceled
Claims 1, 4, 7, 8, 9, 10, 12-14, 18-20 are amended
Claims 21-26 are new
Response to Arguments
Objections to the Specification
Applicant’s arguments regarding the objections to the specification have been considered and are persuasive. Given the applicants amendments, the objections to the specification have been withdrawn.
Objections to the Claims
Applicant’s arguments regarding the objections to claims 4, 15-17, and 20 have been considered and are persuasive. Given the applicants amendments, the objections to the claims have been withdrawn.
Claim Rejections – 35 U.S.C. § 112
Applicant’s arguments regarding the 35 U.S.C. 112(b) to claims 6 and 7 have been considered and are persuasive. Given the applicants amendments, the objections to the claims have been withdrawn.
Claim Rejections – 35 U.S.C. § 101
Regarding applicant’s arguments for the 35 U.S.C. 101, the examiner respectfully disagrees. Given the current claims, the addition of the electronic device as a robot or independent device in communication with the robot is insignificant extra-solution activity. The current claims language directs the electronic device to merely gather data and generating navigation commands and does not cover the actual execution of the of the commands. Furthermore, the addition of elements relating to the preset search do not represent a judicial exception as the current claims language does not sufficiently represent the argued text. Instead, the currently amended claims merely processes the data collected and process the data through an algorithm to determine the best path based on the robot’s mobility abilities.
The examiner recommends amending the claims language to have an active step such as having the electronic device execute or direct the robot to execute the generated control instruction.
Claim Rejections – 35 U.S.C. § 102 and § 103
Regarding applicant’s argument that LIU fails to disclose a “does not involve the concept of "a control step"”, the examiner respectfully disagrees. The broadest reasonable interpretation for a control step would be the calculation of the next movement of the robot, which LIU discloses in ¶ 0052, “A controller is configured to formulate an action instruction for the mobile robot based on the speed and the 2D local cost map image through a learning-based planner, so that the mobile robot executes the action instruction.”. A person having ordinary skill in the art would recognize that a control step as written in the claims would be the same as an action instruction in that both direct the robot on what the next move should be.
Regarding applicant’s argument that LIU “does not involve a model predictive control algorithm”, the examiner respectfully disagrees. From the specification, the applicant defines a model predictive control algorithm as “Exemplarily, in the process of determining the navigation control instruction based on the model predictive control algorithm, it is possible to, in conjunction with the preset robot model, such as a kinematics model, use a control cost (such as a relatively small steering angle change, a relatively small accelerated velocity change or a relatively small retarded velocity change, or the like) as low as possible, and track as much as possible, i.e. drive according to the local planning path as much as possible to obtain the navigation control instruction.” (Pg. 15 lines1-6). Broadest reasonable interpretation of the specification would be that a “model predictive control algorithm” would encompass the planning algorithm to account for the kinematic model of the robot, which LIU discloses in ¶ 0276, “Based on accurate frame-by-frame action prediction, in this section we evaluate the performance of the trained planner in navigation simulation. To check the ability to avoid obstacles, the global reference path for the robot’s navigation is set to approach or cross obstacles. At each sampling time, the trained planner receives a local cost map and returns a velocity vector, which drives the robot to a new state according to the kinematic model”. The learning based-planner within LIU discloses the analysis of the kinematic model in the process of determining the next instruction for the robot.
Regarding applicant’s argument that LIU does “not involve the construction of a cost function and constraint conditions, let alone the construction of a cost function and constraint conditions based on a model predictive control algorithm”, the examiner respectfully disagrees. Firstly, LIU relies on a cost map for determining the path for the robot, this is disclosed by LIU in ¶ 0035. LIU anticipates that the cost map is generated from a cost function in ¶ 0292 wherein “As an embodiment, the computer executable instructions are used to perform: determining a 2D local cost map according to formula (2), wherein the 2D local cost map is constructed as the sum of a local target reward and an obstacle penalty”. A person having ordinary skill in the art would recognize the formula in LIU generating the cost map to be a cost function. The cost map would then be inputted to the learning model in LIU for path planning as disclosed in ¶ 0300.
Likewise, LIU anticipates the implementation of constraints wherein motion instructions are calculated “according to formulas (5a), (5b), and (5c), wherein formulas (5b) and (5c) are constraints” (LIU, ¶ 0081) and implements the calculations into local path planning within ¶ 0244. Furthermore, within ¶ 0005 of LIU, LIU recognizes that determining the optimal trajectory requires the “solving the optimization problem is a challenge: since the objective function involves the robot dynamics model and the constraints may consist of components related to complex geometry”.
Regarding construction, the specification of the current application views construction as a combination of multiple variables to yield a single function. Within LIU, the cost function resulting from the analysis of multiple variables results in a cost map as within ¶ 0292. Formulas (5b)-(5c) of LIU demonstrate the constraint calculations that are provided to the path planner and as described within ¶ 0085 are derived from the vehicle robot kinematic model, which is consistent with the given specification of the current application wherein “a constraint condition is constructed by using the local planning path, the first robot state, the second robot state, the preset kinematics model corresponding to the robot, and the control step based on the model predictive control algorithm, where the constraint condition includes a third expression for representing a kinematics constraint manner of the robot and a fourth expression for representing a value range of the control signal of the robot.” (Pg 19 lines 15-19).
LIU additionally fulfills the requirement for the implementation of a model predictive control algorithm by calculating the robot control instruction based on the vehicle kinematic model as in ¶ 0276 and previously argued above.
Regarding the applicant’s arguments that “this kinematic model is not used during the process of outputting the action commands”, the examiner respectfully disagrees. The learning-based planner within LIU is used for generating action instructions as disclosed in ¶ 0013 (“Based on the speed and the 2D local cost map image, an action instruction is formulated for the mobile robot through a learning-based planner so that the mobile robot executes the action instruction.”). Given LIU anticipates the robot kinematics model being implemented for generating motion instructions within the demonstrator (LIU, ¶ 0081, “The demonstrator determines motion instructions for the mobile robot according to formulas (5a), (5b), and (5c), wherein formulas (5b) and (5c) are constraints;”), it is obvious that the robot model is implemented in generating action instructions.
Regarding applicants fifth argument that the learning-based planner is “essentially different” from the claimed application, the examiner respectfully disagrees. During patent examination, the pending claims must be "given their broadest reasonable interpretation consistent with the specification." The Federal Circuit’s en banc decision in Phillips v. AWH Corp., 415 F.3d 1303, 1316, 75 USPQ2d 1321, 1329 (Fed. Cir. 2005) expressly recognized that the USPTO employs the "broadest reasonable interpretation" standard:
The Patent and Trademark Office ("PTO") determines the scope of claims in patent applications not solely on the basis of the claim language, but upon giving claims their broadest reasonable construction "in light of the specification as it would be interpreted by one of ordinary skill in the art." In re Am. Acad. of Sci. Tech. Ctr., 367 F.3d 1359, 1364[, 70 USPQ2d 1827, 1830] (Fed. Cir. 2004). Indeed, the rules of the PTO require that application claims must "conform to the invention as set forth in the remainder of the specification and the terms and phrases used in the claims must find clear support or antecedent basis in the description so that the meaning of the terms in the claims may be ascertainable by reference to the description." 37 CFR 1.75(d)(1)
A broadest reasonable interpretation of “preset search method” would incorporate the inclusion of obstacles into the consideration of the local path planning. LIU discloses the inclusion of obstacles in the path within the cost map ¶ 0057 and accordingly modifies the formulas as shown in ¶ 0085. LIU additionally fulfills the requirement for the implementation of a model predictive control algorithm (method) by calculating the robot control instruction based on the vehicle kinematic model as in ¶ 0276 and previously argued above. The preset search method as described within the current application specification is described as “a graph search method. The graph search method may construct a path from a start point to an end point by using an environment map already known and the obstacle information in the map” (Pg 8 lines 8-10) which is consistent with a cost map generally known in the art and as described by LIU.
Due to the aforementioned arguments, the rejection under 35 U.S.C. 103 is sustained. Please see 35 U.S.C. 103 rejection below.
Claim Objections
Claim 8 is objected to because of the following informalities:
The preamble of claim 8 as amended (“The method of any one of claim 1, wherein”) is unclear as to which claims of claim 1 claim 8 would be dependent to.
The office recommends removing the “of any one” language from the claim preamble.
Appropriate correction is required.
Claim Rejections - 35 USC § 101
The text of those sections of Title 35, U.S. Code not included in this action can be found in a prior Office action.
Claims 1-26 are rejected under 35 U.S.C. 101 because the claimed invention recites an abstract idea without significantly more. See MPEP 2106 (III)
Step 1: Does the Claim Fall within a Statutory category?
Yes, with respect to claims 1-26, a method, apparatus, and non-transitory computer readable medium for generating navigation instructions for a robot based on path planning decisions for avoiding obstacles.
Step 2A, Prong One: Does the claim recite an abstract idea, law of nature, or natural phenomenon?
The following claims identify the limitations that recite an abstract idea in italics and that recite additional elements in bold:
(Currently Amended) A navigation method, comprising: determining, by an electronic device, a global planning path in a target map according to a current position of a robot and an end position in a navigation request, wherein the electronic device is the robot or an independent device having a navigation function and capable of communicating with the robot; determining, by the electronic device, an initial local path corresponding to the global planning path based on a local planning range, wherein the local planning range corresponds to a boundary of a local costmap, and the local costmap comprises obstacle information within the local planning range; generating, by the electronic device, a local planning path corresponding to the initial local path based on a preset search method according to the initial local path and the local costmap; acquiring, by the electronic device, a first robot state corresponding to a local start point in the local planning path and a second robot state corresponding to a local end point in the local planning path; constructing, by the electronic device, a cost function and a constraint condition by using the local planning path, the first robot state, the second robot state, a preset robot model corresponding to the robot, and a control step based on a model predictive control algorithm, wherein the cost function comprises a parameter corresponding to a navigation control instruction, the navigation control instruction comprises a control instruction corresponding to a velocity, a control instruction corresponding to an accelerated velocity, a control instruction corresponding to an angular velocity, a control instruction corresponding to an angular acceleration, or a control instruction corresponding to an orientation rotation angle; and solving, by the electronic device, the cost function based on the constraint condition with an objective in which the cost function has a minimum value to obtain the navigation control instruction corresponding to the final navigation path in a next control step of the robot.
(Original) The method of claim 1, before the determining a global planning path in a target map according to a current position of a robot and an end position in a navigation request, further comprising: acquiring a topology road network corresponding to an environment where the robot is located, and determining the target map according to the topology road network.
(Original) The method of claim 1, before the determining a global planning path in a target map according to a current position of a robot and an end position in a navigation request, further comprising: acquiring a grid corresponding to an environment where the robot is located, and determining the target map according to the grid.
(Currently Amended) The method of claim 1, wherein the preset search method performs a search with an objective in which the local planning path approaches the initial local path and avoids an obstacle, and the preset search method comprises at least one of an A* algorithm, a D* algorithm, or a shortest path algorithm Dijkstra.
(Canceled).
(Canceled).
(Currently Amended) The method of claim 1,wherein the robot comprises a differential drive robot; and the cost function comprises a first expression for representing tracking accuracy of the robot and a second expression for representing a size of a navigation control signal of the robot and a change rate of the navigation control signal of the robot; and the constraint condition comprises a third expression for representing a kinematics constraint manner of the robot and a fourth expression for representing a value range of a control signal of the robot.
(Currently Amended) The method of any one of claim 1, wherein the preset robot model comprises at least one of a preset robot mechanical model, a preset robot kinematics model, or a preset robot dynamic model.
(Currently Amended) An electronic device, the electronic device being a robot or an independent device having a navigation function and capable of communicating with the robot, comprising: at least one processor; and a memory configured to store at least one program; wherein the at least one program, when executed by the at least one processor, causes the at least one processor to: determine a global planning path in a target map according to a current position of the robot and an end position in a navigation request; and determine an initial local path corresponding to the global planning path based on a local planning range, wherein the local planning range corresponds to a boundary of a local costmap, and the local costmap comprises obstacle information within the local planning range; generate a local planning path corresponding to the initial local path based on a preset search method according to the initial local path and the local costmap; acquire a first robot state corresponding to a local start point in the local planning path and a second robot state corresponding to a local end point in the local planning path; construct a cost function and a constraint condition by using the local planning path, the first robot state, the second robot state, a preset robot model corresponding to the robot, and a control step based on a model predictive control algorithm, wherein the cost function comprises a parameter corresponding to a navigation control instruction, the navigation control instruction comprises a control instruction corresponding to a velocity, a control instruction corresponding to an accelerated velocity, a control instruction corresponding to an angular velocity, a control instruction corresponding to an angular acceleration, or a control instruction corresponding to an orientation rotation angle; and solve the cost function based on the constraint condition with an objective in which the cost function has a minimum value to obtain the navigation control instruction corresponding to the final navigation path in a next control step of the robot.
(Currently Amended) A non-transitory computer-readable storage medium storing a computer program which, when executed by an electronic device, implements the following: determining a global planning path in a target map according to a current position of a robot and an end position in a navigation request; determining an initial local path corresponding to the global planning path based on a local planning range, wherein the local planning range corresponds to a boundary of a local costmap, and the local costmap comprises obstacle information within the local planning range; generating a local planning path corresponding to the initial local path based on a preset search method according to the initial local path and the local costmap; acquiring a first robot state corresponding to a local start point in the local planning path and a second robot state corresponding to a local end point in the local planning path; constructing a cost function and a constraint condition by using the local planning path, the first robot state, the second robot state, a preset robot model corresponding to the robot, and a control step based on a model predictive control algorithm, wherein the cost function comprises a parameter corresponding to a navigation control instruction, the navigation control instruction comprises a control instruction corresponding to a velocity, a control instruction corresponding to an accelerated velocity, a control instruction corresponding to an angular velocity, a control instruction corresponding to an angular acceleration, or a control instruction corresponding to an orientation rotation angle; and solving the cost function based on the constraint condition with an objective in which the cost function has a minimum value to obtain the navigation control instruction corresponding to the final navigation path in a next control step of the robot; wherein the electronic device is the robot or an independent device having a navigation function and capable of communicating with the robot.
(Canceled).
(Currently Amended) The method of claim 2, wherein the preset robot model comprises at least one of a preset robot mechanical model, a preset robot kinematics model, or a preset robot dynamic model.
(Currently Amended) The method of claim 3, wherein the preset robot model comprises at least one of a preset robot mechanical model, a preset robot kinematics model, or a preset robot dynamic model.
(Currently Amended) The method of claim 4, wherein the preset robot model comprises at least one of a preset robot mechanical model, a preset robot kinematics model, or a preset robot dynamic model.
(Canceled)
(Canceled)
(Canceled)
(Currently Amended) The electronic device of claim 9, the at least one processor is further caused to: acquire a topology road network corresponding to an environment where the robot is located, and determine the target map according to the topology road network.
(Currently Amended) The electronic device of claim 9, the at least one processor is further caused to: acquire a grid corresponding to an environment where the robot is located, and determine the target map according to the grid.
(Currently Amended) The electronic device of claim 9, wherein the preset search method based on the constraint condition with an objective in which the cost function has a minimum value the local planning path approaches the initial local path and avoids an obstacle, and the preset search method comprises at least one of an A* algorithm, a D* algorithm, or a shortest path algorithm Dijkstra.
(New) The electronic device of claim 9, wherein the robot comprises a differential drive robot; and the cost function comprises a first expression for representing tracking accuracy of the robot and a second expression for representing a size of a navigation control signal of the robot and a change rate of the navigation control signal of the robot; and the constraint condition comprises a third expression for representing a kinematics constraint manner of the robot and a fourth expression for representing a value range of a control signal of the robot.
(New) The electronic device of claim 9, wherein the preset robot model comprises at least one of a preset robot mechanical model, a preset robot kinematics model, or a preset robot dynamic model.
(New) The non-transitory computer-readable storage medium of claim 10, the program computer, when executed by the electronic device, further implements: acquiring a topology road network corresponding to an environment where the robot is located, and determining the target map according to the topology road network.
(New) The non-transitory computer-readable storage medium of claim 10, the program computer, when executed by the electronic device, further implements: acquiring a grid corresponding to an environment where the robot is located, and determining the target map according to the grid.
(New) The non-transitory computer-readable storage medium of claim 10, wherein the preset search method based on the constraint condition with an objective in which the cost function has a minimum value the local planning path approaches the initial local path and avoids an obstacle, and the preset search method comprises at least one of an A* algorithm, a D* algorithm, or a shortest path algorithm Dijkstra.
(New) The non-transitory computer-readable storage medium of claim 10, wherein the robot comprises a differential drive robot; and the cost function comprises a first expression for representing tracking accuracy of the robot and a second expression for representing a size of a navigation control signal of the robot and a change rate of the navigation control signal of the robot; and the constraint condition comprises a third expression for representing a kinematics constraint manner of the robot and a fourth expression for representing a value range of a control signal of the robot.
Yes, except for the recited additional elements above shown in bold, the remaining limitations claim an abstract idea. The methods put forth by the applicant in the claimed invention recite a concept which can be performed in the human mind (such as observations, evaluations, and judgement opinions). The claims within the claimed invention directed towards the generation of robot control instructions based on path planning decisions for avoiding obstacles represent an abstract idea.
Step 2A, Prong Two: Does the claim recite additional elements that integrate the judicial exception into a practical application?
No. The claims as a whole merely recites a method which performs an abstract idea. The structural components claimed (i.e., additional elements that are bolded above) are recited at a high level of generality and are merely invoked tools for implementing the steps of generating robot instructions based upon collected data. The methods for generating robot instructions based on path planning, obstacle avoidance, and robot characteristics are recited at a high level of generality such that they could practically be performed in the human mind (Electric Power Group v. Alstom, S.A., 830 F.3d 1350, 1353-54, 119 USPQ2d 1739, 1741-42 (Fed. Cir. 2016);).
The addition of the electronic device as a robot or independent device in communication with the robot is insignificant extra-solution activity. The amended claims language directs the electronic device to merely gather data, process the data through an algorithm to determine the best path based on the robot’s mobility abilities, and generating navigation commands. However, the current language does not cover the execution of the command.
Simply implementing the abstract idea of path planning onto robot instruction is not a practical application of the abstract idea. Additionally, there is no improvement to the functioning of the computer or technology. Therefore, the abstract idea is not integrated into a practical application. See MPEP 2106.05(f)
Step 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception?
No. as discussed in Step 2A, prong 2, the additional elements in the claim, both individually and in combination, amount no more than tools to perform the abstract idea. Merely performing the abstract idea using a specialized algorithm cannot provide an inventive concept. Therefore, the claims do not provide an inventive concept.
Dependent claims 2-8,12-26 do not recite any further limitations that cause the claim(s) to be patent eligible. Rather, the limitations of dependent claims further narrow the abstract idea and can be performed in the human mind. Therefore, dependent claims 2-8,12-26 are not patent eligible under the same rationale as provided for in the rejection of independent claims 1, 9, 10.
Therefore, claims 1-26 are ineligible under 35 USC §101
The examiner recommends amending the claims language to have an active step such as having the electronic device execute or direct the robot to execute the generated control instruction.
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 (i.e., changing from AIA to pre-AIA ) 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 text of those sections of Title 35, U.S. Code not included in this action can be found in a prior Office action.
Claims 1, 3, 9, 10, 19, and 24 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by LIU (WO2019076044).
Regarding claim 1:
LIU discloses:
A navigation method, comprising: determining, by an electronic device, a global planning path in a target map according to a current position of a robot and an end position in a navigation request, (see at least LIU, ¶ 0276, “Based on accurate frame-by-frame action prediction, in this section we evaluate the performance of the trained planner in navigation simulation. To check the ability to avoid obstacles, the global reference path for the robot’s navigation is set to approach or cross obstacles. At each sampling time, the trained planner receives a local cost map and returns a velocity vector, which drives the robot to a new state according to the kinematic model. The resulting trajectory is shown in Figure 10. In Figure 10, the dashed line represents the global reference path, and the solid and dotted lines correspond to the trajectories of the learning-based planner and the optimization-based demonstrator, respectively. As can be seen in Figure 10, the trajectory of the well-trained planner successfully avoids obstacles when the global reference is close, while smoothly following the reference in open space.”)
wherein the electronic device is the robot or an independent device having a navigation function and capable of communicating with the robot; (see at least LIU, ¶ 0009, "In view of this, the embodiments of the present application provide a local motion planning method and apparatus for a mobile robot, and a computer storage medium, which provide a new imitation learning method for local motion planning and obstacle avoidance of a mobile robot, which can efficiently avoid obstacles, accelerate the local motion planning decision of the mobile robot, and make the made decision as optimized, secure and general as possible.")
determining, by the electronic device, an initial local path corresponding to the global planning path based on a local planning range, (see at least LIU, ¶ ¶ 0017, “Determine a local target point and a local obstacle map according to a given global path and the surrounding environment map;”; ¶ 0280, “As shown in Figure 11, the robot makes local planning decisions based on the local occupancy map constructed online. Although the map is relatively small in scale, it provides rich information about the surrounding environment. When encountering obstacles that impede the global trajectory, the trained planner successfully provides action instructions to drive the robot into an open area.”; ¶ 0288, “As an implementation method, the computer executable instructions are used to execute: obtaining data collected by predetermined sensors on the mobile robot; positioning the mobile robot based on the data, and establishing a surrounding environment map of the mobile robot; determining local target points and local obstacle maps based on a given global path and the surrounding environment map; and determining a 2D local cost map image based on the local target points and the local obstacle map.”)
wherein the local planning range corresponds to a boundary of a local costmap, and (see at least LIU, ¶ 0026, “Wherein, m<sub>obs</sub> is a local obstacle map of obstacle probability, m<sub>goal</sub> is a binary target map, wherein in the binary target map, the pixel value of the local target point is set to 1, and the other pixel values are set to 0, λ is a hyperparameter about the reward coefficient; and if the nearest valid sub-target point on the reference path is outside the 2d local cost map window, the projection point of the valid target point to the map border is used to replace the valid target point.”; ¶ 0276, “Based on accurate frame-by-frame action prediction, in this section we evaluate the performance of the trained planner in navigation simulation. To check the ability to avoid obstacles, the global reference path for the robot’s navigation is set to approach or cross obstacles. At each sampling time, the trained planner receives a local cost map and returns a velocity vector, which drives the robot to a new state according to the kinematic model. The resulting trajectory is shown in Figure 10. In Figure 10, the dashed line represents the global reference path, and the solid and dotted lines correspond to the trajectories of the learning-based planner and the optimization-based demonstrator, respectively. As can be seen in Figure 10, the trajectory of the well-trained planner successfully avoids obstacles when the global reference is close, while smoothly following the reference in open space.”; ¶ 0280)
the local costmap comprises obstacle information within the local planning range; (see at least LIU, ¶ 0018, “A 2D local cost map image is determined according to the local target point and the local obstacle map.”; ¶ 0252, “This application develops an imitation learning algorithm to achieve real-time near-optimal local motion planning while maintaining good safety and versatility for mobile robot applications. Different from end-to-end imitation, we develop a local planning strategy based on a pretrained 2D local cost map as input. The local costmap can be constructed from a local target point and obstacle map, which contains multiple frames of information received from sensor devices such as lidar, sonar, and depth cameras. At each sampling time, our local motion planning model embedded in a value iteration network produces an action command via feed-forward reasoning, which is computationally efficient and enables plan-based reasoning. To train a robust model, we use a combination of real-world local obstacle maps collected from demonstration experiments and randomly generated artificial maps, which not only speeds up the data collection process but also complements the dangerous observation samples that are rarely encountered in demonstrations. A brief comparison of the proposed method and existing learning methods is summarized in Table 1.”)
generating, by the electronic device, a local planning path corresponding to the initial local path based on a preset search method according to the initial local path and the local costmap; (see at least LIU, ¶ 0276)
acquiring, by the electronic device, a first robot state corresponding to a local start point in the local planning path and a second robot state corresponding to a local end point in the local planning path; (see at least LIU, ¶ 0276)
constructing, by the electronic device, a cost function and a constraint condition by using (see at least LIU, ¶ 0219, “Figure 3 is a block diagram of a local mobile planning system with a policy network. As can be seen from Figure 3, the system mainly includes two major planning blocks. The first planning block is used to preprocess the raw sensor data and generate a local occupancy map describing the surrounding obstacles and local target points extracted from the global path according to the robot posture. These intermediate results are then fed into the second planning block where we employ a deep neural network to model the local planning strategy. Additionally, we provide the robot's velocity as network input to improve the smoothness of sequential decisions. During deployment, the proposed neural network policy generates action commands by performing feed-forward computations at each sampling time, and is therefore computationally efficient and tractable for real-time decision making.”; ¶ 0276; ¶ 0292, “In an implementation, the computer-executable instructions are configured to: determine a 2D local cost map according to a formula (2), where the 2D local cost map is constructed as a sum of a local target reward and an obstacle penalty:”; ¶ 0300, “In an implementation, the computer-executable instructions are configured to: input a 2D local cost map image to a deep neural network embedded with a value iteration module, and the value iteration module extracts a high-level planning feature through recursive operation;”)
the local planning path, the first robot state, the second robot state, a preset robot model corresponding to the robot, and (see at least LIU, ¶ 0052, “A controller is configured to formulate an action instruction for the mobile robot based on the speed and the 2D local cost map image through a learning-based planner, so that the mobile robot executes the action instruction.”; ¶ 0219; ¶ 0276; ¶ 0278, “Finally, we deploy the trained model to real-world navigation experiments. Given a global reference path, the task of the Segway delivery robot is to follow the reference path and avoid obstacles on the way. Pay attention to two aspects: the response to unexpected obstacles on the reference path, and the robustness of the long-term operation.”; ¶ 0280)
a control step based on a model predictive control algorithm, (see at least LIU, ¶ 0052)
wherein the cost function comprises a parameter corresponding to a navigation control instruction, (see at least LIU, ¶ 0058-0065, “In the above solution, optionally, the controller is specifically configured to: Given the 2D local cost map image and the mobile robot speed, the following action commands are provided according to equation (1): u＝f θ(m,u')(1) where U = (V, W) is a vector of linear velocity V and angular velocity W to be performed, U ′ is a velocity vector of the mobile robot, theta is a model weight parameter, and M is a 2D local cost map image. In the above solution, optionally, the pre-processor is specifically configured to: determining a 2D local cost map according to formula (2), wherein the 2D local cost map is constructed as the sum of the local target reward and the obstacle penalty: m＝λm goal-m obs(2) where M is a local obstacle map of the obstacle probability, M is a binary target map, where in the binary target map, the pixel value of the local target point is set to 1, the other pixel values are set to 0, and lambda is a hyperparameter related to the reward coefficient ; If the nearest valid target point on the reference path is outside the 2D local cost map window, the effective target point is replaced with a projection point from the valid target point to the map frame.”; ¶ 0276)
the navigation control instruction comprises (see at least LIU, ¶ 0013, “formulating an action instruction for the mobile robot through a learning-based planner based on the speed and the 2D local cost map image, so as to execute the action instruction by the mobile robot.”)
a control instruction corresponding to a velocity, a control instruction corresponding to an accelerated velocity, a control instruction corresponding to an angular velocity, a control instruction corresponding to an angular acceleration, or (see at least LIU, ¶ 0128-0129, "Here, the action instruction includes: a linear speed and an angular velocity to be executed by the mobile robot.")
a control instruction corresponding to an orientation rotation angle; and (see at least LIU, ¶ 0128-0129; ¶ 0161, "where n is the length of the prediction range, x is the 2D pose of the mobile robot at time step k, d is the distance between the mobile robot and the local target point at time step n, alpha is the absolute angle between the mobile robot orientation and the direction from the mobile robot position to the local target point at time step n, h(x, u) is the robot kinematics model, is the maximum obstacle probability that allows access, W, W, W are cost weight parameters.")
solving, by the electronic device, the cost function based on the constraint condition with an objective in which the cost function has a minimum value to obtain the navigation control instruction corresponding to the final navigation path in a next control step of the robot. (see at least LIU, ¶ 0052, “A controller is configured to formulate an action instruction for the mobile robot based on the speed and the 2D local cost map image through a learning-based planner, so that the mobile robot executes the action instruction.”; ¶ 0081; ¶ 0229, “Note that the cost map can also be learned within the neural network by adding additional convolutional layers in front of the network. However, in our empirical experiments, we observed little difference in inference accuracy. Two possible reasons could be that the cost map calculated from (2) indeed represents the essence of the demonstrator’s cost function, and the value function is eventually learned and adapted to the cost map. In this work, we remove the convolutional layers for cost learning, aiming to reduce model redundancy.”)
EXAMINER's NOTE: Although LIU defines the demonstrator as calculating the robot's moves based on constraints of the robot’s kinematics, LIU anticipates the outgoing results ("motion instructions") to be a cost function for the robot.
Regarding claim 3:
LIU discloses the limitations within claim 1 and LIU further discloses:
The method of claim 1, before the determining a global planning path in a target map according to a current position of a robot and an end position in a navigation request, further comprising: acquiring a grid corresponding to an environment where the robot is located, and determining the target map according to the grid (see at least LIU, ¶ 0189, "where M obs is a local obstacle map of the obstacle probability, M goal is a binary target map, where in the binary target map, the pixel value of the local target point is set to 1, the other pixel values are set to 0, and lambda is a hyper parameter related to the reward coefficient ; If the nearest valid target point on the reference path is outside the 2D local cost map window, the effective target point is replaced with a projection point from the valid target point to the map frame."; Figure 10)
EXAMINERS NOTE: Although LIU does not explicitly generate a grid, LIU effectively generates a grid within the binary target map by assigning 0 and 1 values to square pixels on a map.
Regarding claim 9:
With regards to claim 9, this is the apparatus claim for method claim 1 and is therefore rejected using the same references and rationale.
Regarding claim 10:
With regards to claim 10, this is the computer-readable storage medium claim for method claim 1 and is therefore rejected using the same references and rationale.
Regarding claim 19:
With regards to claim 19, this claim is substantially similar to claim 3 and is therefore rejected using the same references and rationale.
Regarding claim 24:
With regards to claim 24, this claim is substantially similar to claim 3 and is therefore rejected using the same references and rationale.
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 (i.e., changing from AIA to pre-AIA ) 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 text of those sections of Title 35, U.S. Code not included in this action can be found in a prior Office action.
Claims 2, 8, 12, 13, 18, 22, and 23 are rejected under 35 U.S.C. 103 as being unpatentable over LIU (WO2019076044) in view of ZAPHIR (US20180245922A1).
Regarding claim 2:
LIU discloses the limitations within claim 1 and further discloses:
before the determining a global planning path in a target map according to a current position of a robot and an end position in a navigation request, (see at least LIU, ¶ 0276, "On the basis of accurate frame-by-frame motion prediction, in this section we evaluate the performance of a trained planner in the navigation simulation. In order to check the ability to avoid obstacles, a global reference path for robot navigation is set to approach or span an obstacle. At each sampling time, a trained planner receives the local cost map and returns a velocity vector, which causes the robot to be driven to a new state according to the kinematic model. The resulting trajectory is shown in FIG. 10. In FIG. 10, a dashed line represents a global reference path, and a solid line and a dotted line respectively correspond to a learning-based planner and an optimized exemplary trajectory. As can be seen from FIG. 10, the trajectory of a trained planner successfully avoids obstacles when the global reference value approaches while smoothly following the reference in the open space. In addition ,the trajectory of a trained planner is almost the same as the behavior of an exemplary device, which illustrates the high quality of a trained planner in mimicking approximately the best exemplary aspect.")
LIU does not disclose, but ZAPHIR teaches:
further comprising: acquiring a topology road network corresponding to an environment where the robot is located, and determining the target map according to the topology road network. (see at least ZAPHIR, ¶ 0018, “The term “terrain” as used in this application refers to a generalized characterization of a spatial region, as may be reflected by a multitude of GIS (geographic information system) layers and elements applicable to the region, such as height map layers (e.g., DTM—digital terrain model layer, DSM—digital surface model layer etc.), images from different sources (e.g., as raster layers, such as aerial photos, multispectral imaging etc.), vector data (as a vector layer), data relating to materials in the region (material layer, e.g., geological, soil, vegetation and geomorphological maps) as well as other layers (referring e.g., to objects in the region, hydrological data, thermal imaging etc.).”; ¶ 0033, “Physical traversability module 120 may be configured to determine, for classified representation 111 with or without material features 115, a terrain topography 80, optionally vector data 122, optionally historical data 76 and given vehicle parameters 70 (e.g., vehicle dynamic parameters), a degree of traversability of the vehicle through the terrain as represented by classified material map 119 and/or by received image 90, to yield a traversability map 129 as schematically illustrated in FIG. 2C, being an exemplary traversability map 129, according to some embodiments of the invention. Traversability map 129 may comprise e.g., traversable regions 128A (absolutely or with respect to given vehicle parameters 70, e.g., a flat region with stable soil), partly traversable regions 128B (depending on given vehicle parameters 70, e.g., a plantation) or hardly traversable/untraversable regions 128C (e.g., deep ditches or cliffs). The degree of traversability may relate to vehicle parameters 70, topography 80 at large and small scales (an example for the latter—dimensions and characteristics of steps), weather 75 and may be modified in realtime, e.g., by heavy equipment such as a bulldozer or an excavator.”; ¶ 0044, “In certain embodiments, routing module 130 may be configured to derive a navigation mesh 134 from traversability map 129 to enable effective route planning with respect to computing resources and to provide an effective platform for applying traversability updates 137 quickly. Navigation mesh 134 may group regions in traversability map 129, incorporate vector data and provide effective route alternatives (see below) and route adaptations to vehicle types and parameters 70 when required. In certain embodiments, navigation mesh 134 and/or traversability map 129 may have a hierarchical structure to enable quick updating and rout planning.”)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify, with a reasonable expectation of success, the path planning with an environment map within LIU to include the terrain data for route planning of ZAPHIR to yield an effective global path accounting for traversable areas. It should be noted that LIU recognizes the benefits of improved data for path planning by using apps such as Google maps (¶ 0004).
Regarding claim 8:
LIU discloses the limitations within claim 1 and further discloses:
the preset robot model comprises at least one of (see at least LIU, ¶ 0081, "The exemplary device determines a motion instruction for the mobile robot according to formulas (5a), (5b), and(5c), where formulas (5b) and (5c) are constraint conditions;"; ¶ 0085, "where n is the length of the prediction range, x is the 2D pose of the mobile robot at time step k, d is the distance between the mobile robot and the local target point at time step n, alpha is the absolute angle between the mobile robot orientation and the direction from the mobile robot position to the local target point at time step n, h(x, u) is the robot kinematics model, m is the maximum obstacle probability that allows access, W1, W2, W3 are cost weight parameters.")
a preset robot kinematics model, or (see at least LIU, ¶ 0081, ¶ 0085)
LIU does not disclose, but ZAPHIR teaches:
a preset robot mechanical model, (see at least ZAPHIR, ¶ 0029, “As schematically illustrated in FIG. 1B, terrain-related data 90 may be used to extract material features 115 and then be classified 110 (e.g., by applying machine learning algorithms) according to material features 115 with respect to a user defined region 60A. Traversability map 120 may be constructed with respect to classification 110, material mechanical parameters 95, topography 80 and vehicle data 70, e.g., using a physical model 71 that connects vehicle parameters with material mechanical parameters and other parameters to yield traction and traversability data. Traversability map 120 may then be used for route planning 140 under user parameters and rules 60 and possibly involving user interaction 50, for estimation of traversability of user-defined route(s) 60B and/or for estimation of traversability of planned routes 140, e.g., for different vehicles or under changing circumstances (such as weather changes or interventions related to the terrain). In the latter case, traversability map 129 may be partly or fully updated 137, possibly implementing different updating periods according to the extent or priority of the changes. Traversability map 120 may be calculated at different resolution for different types of vehicles. Traversability map 120 may be dynamic in the sense that at least parts or elements of traversability map 120 may be modified in real time or close to real time and according to accumulating information from vehicles moving through the terrain and from other sources. User interaction 50 may also be involved in the dynamic updating of traversability map 120. Alternatively or complementarily, traversability map 120 and/or physical model 71 may be used to create a direct and detailed estimation of traversability 132 along user-defined route(s) 60B and/or points thereof. Physical model 71 may be optimized to handle real time physical complex calculations.”)
a preset robot dynamic model. (see at least ZAPHIR, ¶ 0035, “In certain embodiments, physical traversability module 120 may be further utilized to assess the forces applied to the driver and passengers of the vehicles, and their movements within the vehicle (taking into account the vehicles' suspension systems), e.g., using multi-body dynamic models. The applied forces and movements may also be used to augment the estimation of traversability and the route selection (as some paths may be traversable for the vehicle but not to the passengers with the vehicle, under given physiological constraints). User parameters and rules 60 may be used to enhance traversability map 129, concerning e.g., restrictions concerning passengers well-being and operational requirements that pose additional limitations on traversability beyond the mere vehicular traversability.”)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify, with a reasonable expectation of success, the robotic kinematic model for calculating motion instructions within LIU to include the dynamic and mechanical limitations in robot models of ZAPHIR to yield an effective path planning system which accounts for the anticipated behaviors of different limitations inherent to different robot designs.
Regarding claim 12:
With regards to claim 12, this claim is substantially similar to claim 8 and is therefore rejected using the same references and rationale.
Regarding claim 13:
With regards to claim 13, this claim is substantially similar to claim 8 and is therefore rejected using the same references and rationale.
Regarding claim 18:
With regards to claim 18, this claim is substantially similar to claim 2 and is therefore rejected using the same references and rationale.
Regarding claim 22:
With regards to claim 22, this claim is substantially similar to claim 8 and is therefore rejected using the same references and rationale.
Regarding claim 23:
With regards to claim 23, this claim is substantially similar to claim 2 and is therefore rejected using the same references and rationale.
Claims 4, 20, and 25 are rejected under 35 U.S.C. 103 as being unpatentable over LIU (WO2019076044) in view of YANG (Yang, Liang, Qi, Juntong, Song, Dalei, Xiao, Jizhong, Han, Jianda, Xia, Yong, Survey of Robot 3D Path Planning Algorithms, Journal of Control Science and Engineering, 2016, 7426913, 2016.)
Regarding claim 4:
the preset search method performs a search with an objective in which the local planning path approaches the initial local path and avoids an obstacle, and (see at least LIU, ¶ 0009, "In view of this, the embodiments of the present application provide a local motion planning method and apparatus for a mobile robot, and a computer storage medium, which provide a new imitation learning method for local motion planning and obstacle avoidance of a mobile robot, which can efficiently avoid obstacles, accelerate the local motion planning decision of the mobile robot, and make the made decision as optimized, secure and general as possible.”; ¶ 0091, "The method and apparatus for planning a local motion of a mobile robot, and a computer storage medium provided in this application determine a 2D local cost map image ; determining a speed of the mobile robot; and based on the speed and the 2D local cost map image, formulating an action instruction for the mobile robot by using a learning-based planner, so that the mobile robot executes the action instruction, so that an obstacle can be efficiently avoided, a local motion planning decision of the mobile robot is accelerated, and meanwhile, the made decision is optimized, safe and universal as possible.")
LIU does not disclose, but YANG teaches:
the preset search method comprises at least one of an A* algorithm, (see at least YANG, Pg 10, “Voronoi generates a global graph or local graph, but almost the same as RRG and PRM; it also cannot generate the shortest path at the same time. Thus it seeks help from Dijkstra’s algorithm, A∗, D∗, and so forth. This paper defines three steps to Voronoi path generation methods: (a) sampling the environment or just seeking help from other environment construction methods, (b) generating a 3D Voronoi graph, and (c) employing a search algorithm to find the minimal cost path globally.”; Pg 11, “5. Node Based Optimal Algorithms”, “Node based optimal algorithms are classified by the reason that they deal with nodes’ and arcs’ weight information (but not limited to these, or sometimes called grid); they calculate the cost by exploring through the nodes, thus to find the optimal path. This kind of algorithms is also called network algorithms [99] which means they search through the generated network, and it means the same with node based algorithms.”; Pg 11-12, “5.2 A-Star (𝐴∗).”, “A-star (A∗) [22] is an extension of Dijkstra’s algorithm, which reduces the total number of states by introducing a heuristic estimation of the cost from the current state to the goal state. The heuristic function can be designed to obtain the constraints, while the estimation must never overestimate the actual cost to get the nearest goal node. By applying this guiding like heuristic, A∗ can converge very fast and ensures optimality as well.”)
a D* algorithm, or (see at least YANG, Pg 10, “Voronoi generates a global graph or local graph, but almost the same as RRG and PRM; it also cannot generate the shortest path at the same time. Thus it seeks help from Dijkstra’s algorithm, A∗, D∗, and so forth. This paper defines three steps to Voronoi path generation methods: (a) sampling the environment or just seeking help from other environment construction methods, (b) generating a 3D Voronoi graph, and (c) employing a search algorithm to find the minimal cost path globally.”; Pg 11, “5. Node Based Optimal Algorithms”, “Node based optimal algorithms are classified by the reason that they deal with nodes’ and arcs’ weight information (but not limited to these, or sometimes called grid); they calculate the cost by exploring through the nodes, thus to find the optimal path. This kind of algorithms is also called network algorithms [99] which means they search through the generated network, and it means the same with node based algorithms.”; Pg 12-13, “5.3. D-Star (𝐷∗).”, “D-star (D∗) [23, 52], short for dynamic A∗, is famous for its wide use in the DARPA unmanned ground vehicle programs. D∗ is a sensor based algorithm that deals with dynamic obstacles by real time changing its edge’s weights to form a temporal map and then moves the robot from its current location to the goal location in the shortest unblocked path. D∗, As well as A∗, evaluates the cost by considering the post calculation and forward estimation. D∗ maintains a list of states which is used to propagate information about changes of the arcs cost function.”)
a shortest path algorithm Dijkstra (see at least YANG, Pg 10, “Voronoi generates a global graph or local graph, but almost the same as RRG and PRM; it also cannot generate the shortest path at the same time. Thus it seeks help from Dijkstra’s algorithm, A∗, D∗, and so forth. This paper defines three steps to Voronoi path generation methods: (a) sampling the environment or just seeking help from other environment construction methods, (b) generating a 3D Voronoi graph, and (c) employing a search algorithm to find the minimal cost path globally.”; Pg 11, “5. Node Based Optimal Algorithms”, “Node based optimal algorithms are classified by the reason that they deal with nodes’ and arcs’ weight information (but not limited to these, or sometimes called grid); they calculate the cost by exploring through the nodes, thus to find the optimal path. This kind of algorithms is also called network algorithms [99] which means they search through the generated network, and it means the same with node based algorithms.”; Pg 11, “5.1. Dijkstra’s Algorithm.” “Named after Dijkstra [21], Dijkstra’s algorithm targets for finding the shortest path in a graph where edges’/arcs’ weights are already known. Dijkstra’s algorithm is a special form of dynamic programming and it is also a breath first search method. It finds shortest path which depends purely on local path cost. When applying 3D space, a 3D weighted graph must be built first; then it searches the whole graph to find the minimum cost path. A generalization of Dijkstra’s algorithm is shown below with pseudocode in Algorithm 5.”)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify, with a reasonable expectation of success, the path planner within LIU to include the A*, D*, or Dijkstra path planning models of YANG to yield an effective path planning system.
Regarding claim 20:
With regards to claim 20, this claim is substantially similar to claim 4 and is therefore rejected using the same references and rationale. The additional language regarding the “the preset search method based on the constraint condition with an objective in which the cost function has a minimum value” can be found in LIU ¶ 0085 and ¶ 0229.
Regarding claim 25:
With regards to claim 25, this claim is substantially similar to claim 20 and is therefore rejected using the same references and rationale.
Claim 7, 21, and 26 is rejected under 35 U.S.C. 103 as being unpatentable over LIU (WO2019076044) in view of CHEON (US20220206468A1).
EXAMINERS NOTE: It should be noted that even though CHEON possess a publication date of 6-3-2022, it claims priority to a PCT (WO2020213829) with an international filing date of 2-27-2020, which predates the earliest priority filling date for the current application, 4-19-2021.
Regarding claim 7:
LIU discloses the limitations within claim 1 and LIU further discloses:
the cost function comprises (see at least LIU, ¶ 0276, "On the basis of accurate frame-by-frame motion prediction, in this section we evaluate the performance of a trained planner in the navigation simulation. In order to check the ability to avoid obstacles, a global reference path for robot navigation is set to approach or span an obstacle. At each sampling time, a trained planner receives the local cost map and returns a velocity vector, which causes the robot to be driven to a new state according to the kinematic model. The resulting trajectory is shown in FIG. 10. In FIG. 10, a dashed line represents a global reference path, and a solid line and a dotted line respectively correspond to a learning-based planner and an optimized exemplary trajectory. As can be seen from FIG. 10, the trajectory of a trained planner successfully avoids obstacles when the global reference value approaches while smoothly following the reference in the open space. In addition ,the trajectory of a trained planner is almost the same as the behavior of an exemplary device, which illustrates the high quality of a trained planner in mimicking approximately the best exemplary aspect.")
a first expression for representing tracking accuracy of the robot and (see at least LIU, ¶ 0230, "A set of exemplary action instructions is given û The planner trains the required local motion planning policy based on the error minimization criterion:"; ¶ 0232, "Wherein, (ûi,mi,úi) Is an exemplary tuple, J (theta) represents an error function, which is an exemplary action instruction ûi an accumulation sum of squares of the absolute values of the difference between the actual motion instruction ftheta (mi,úi)"; ¶ 0276)
a second expression for representing a size of a navigation control signal of the robot and (see at least LIU, ¶ 0081, "The exemplary device determines a motion instruction for the mobile robot according to formulas (5a), (5b), and(5c), where formulas (5b) and (5c) are constraint conditions;"; ¶ 0085, "where n is the length of the prediction range, x is the 2D pose of the mobile robot at time step k, d is the distance between the mobile robot and the local target point at time step n, alpha is the absolute angle between the mobile robot orientation and the direction from the mobile robot position to the local target point at time step n, h(x, u) is the robot kinematics model, m is the maximum obstacle probability that allows access, W1, W2, W3 are cost weight parameters."; ¶ 0135, "U = (V, W) is a vector of a linear velocity V and an angular velocity W to be executed, U ′ is a velocity vector of the mobile robot, theta is a model weight parameter, and M is a 2D local cost map image, where the cost map may be determined in a plurality of manners."; ¶ 0233, "Once the training is complete, the model weight parameter theta is fixed and input into equation (1) during deployment so that equation (1) computes the action command based on the model weight parameter theta.")
a change rate of the navigation control signal of the robot; and (see at least LIU, ¶ 0081; ¶ 0085; ¶ 0276)
the constraint condition comprises (see at least LIU, ¶ 0219, "FIG. 3 is a block diagram of a local mobility planning system with a policy network, and it can be seen from FIG. 3that the system mainly includes two large planning blocks, a first planning block, configured to pre-process the original sensing data, and generate, according to the robot posture, a local occupancy map describing surrounding obstacles and a local target point extracted from the global path. These intermediate results are then fed to a second planning block in which we use a deep neural network to simulate the local planning strategy. In addition, we also provide the speed of the robot as a network input to improve the smoothness of the sequential decision. During deployment, the proposed neural network policy generates an action command by performing a feed-forward calculation at each sampling time, so it is computationally efficient and easy to handle for real-time decisions."; ¶ 0276)
a third expression for representing a kinematics constraint manner of the robot and (see at least LIU, ¶ 0081; ¶ 0085; ¶ 0276)
LIU does not disclose, however CHEON teaches:
the robot comprises a differential drive robot; and (see at least CHEON, ¶ 0125, “It goes without saying that, for example, various implementations are possible, such as implementation which is characterized by converting the feasible velocity region of the robot in linear velocity and angular velocity space or the feasible acceleration region of the robot in linear acceleration and angular acceleration space to a linear-scale, dividing and sampling a feasible region at equal intervals, and extracting a set of finite points that fall into the region as the feasible input values or”; ¶ 0126, “implementation which is characterized by converting the feasible velocity region of the robot in linear velocity and angular velocity space or the feasible acceleration region of the robot in linear acceleration and angular acceleration space to a log-scale, exponential-scale, or quadratic-scale scale, dividing and sampling a feasible region at equal intervals, and extracting a set of finite points that fall within the region as the feasible input values.”; ¶ 0127, “When described in more detail under the assumption that a differential drive mobile robot is used and angular acceleration values of both wheels are used as input values,”
a fourth expression for representing a value range of a control signal of the robot. (see at least CHEON, ¶ 0128, “if a feasible angular acceleration value of an n-th left wheel of the differential drive mobile robot is w.sub.l,n, an angular acceleration value of an m-th right wheel is w.sub.r,m, and A is a set of combinations (w.sub.l,n, w.sub.r,m) of all feasible angular acceleration values, A can be represented as follows. A={(w.sub.l,n, w.sub.r,m)|w.sub.l,n ∈ R, n=1, 2, . . . , N and m=1, 2, . . . , M}”; ¶ 0129, “Here, N and M are the number of feasible angular acceleration values of the left and right wheels, respectively, and R denotes a set of real numbers. The following method may be used as a method for determining the acceleration set A.”; ¶ 0130, “The method of converting the feasible acceleration region of the robot to the linear-scale, dividing and sampling the feasible region at equal intervals, and extracting a set of finite points that fall within the region as the input values can be represented as the following equation.”)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify, with a reasonable expectation of success, the demonstrator formula for determining motion instructions accounting for the robot kinematic model within LIU to utilize a differential drive control model accounting for the control limits within CHOEN to effectively yield a more versatile robot control and path planning system tailored to differential drive applications.
EXAMINERS NOTE: Although LIU does not explicitly state that it tracks the “change rate” of the robot’s navigation, LIU instead tracks changes in the robot’s navigation with step time k (¶ 0085).
Regarding claim 21:
With regards to claim 21, this claim is substantially similar to claim 7 and is therefore rejected using the same references and rationale.
Regarding claim 26:
With regards to claim 26, this claim is substantially similar to claim 7 and is therefore rejected using the same references and rationale.
Claim 14 is rejected under 35 U.S.C. 103 as being unpatentable over LIU (WO2019076044) in view of YANG (Yang, Liang, Qi, Juntong, Song, Dalei, Xiao, Jizhong, Han, Jianda, Xia, Yong, Survey of Robot 3D Path Planning Algorithms, Journal of Control Science and Engineering, 2016, 7426913, 2016.) in further view of ZAPHIR (US20180245922A1).
Regarding claim 14:
LIU in view of YANG discloses the limitations within claim 4 and further discloses:
the preset robot model comprises at least one of (see at least LIU, ¶ 0081, ¶ 0085)
a preset robot kinematics model, or (see at least LIU, ¶ 0081, ¶ 0085)
LIU in view of YANG does not disclose, but ZAPHIR teaches:
a preset robot mechanical model, (see at least ZAPHIR, ¶ 0029)
a preset robot dynamic model. (see at least ZAPHIR, ¶ 0035)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify, with a reasonable expectation of success, the robotic kinematic model for calculating motion instructions within LIU in view of YANG to include the dynamic and mechanical limitations in robot models of ZAPHIR to yield an effective path planning system which accounts for the anticipated behaviors of different limitations inherent to different robot designs.
Conclusion
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Vicenti (US 20160271795 A1)
¶ 0074. “The robot controller 190 can use a path planning algorithm known in the art—such as the A* algorithm or Dijkstra's algorithm—to direct the robot 100 to the suspected physical location of the landmark. These algorithms allow the robot 100 to avoid structure or walls that may intervene between the landmark the current position of the robot 100. In one implementation of a robot 100 having the moveable bumper 115, as the robot 100 moves toward the suspected physical location, the controller 190 can compute the contact angle based on an angle of contact with the bumper 115 as the bumper 115 contacts the structure represented by the landmark. Using the contact angle and the known contours of the landmark, the controller 190 can then compute the pose of the robot 100. The controller 190 can compare this computed pose with the estimated pose of the robot 100. Based on the difference between the estimated pose and the computed pose, the controller 190 adjusts the estimated pose of the robot 100 to re-localize the robot 100 within the environment and relative to global occupancy grid coordinates. The discrepancy between the computed pose and the estimated pose can then be used to update the map with this new information. This could involve shifting the most recent parts of the occupancy grid or GraphSLAM map. Examples of updating the map are described in U.S. application Ser. No. 13/632,997 filed on Oct. 1, 2012 and titled “Adaptive mapping with spatial summaries of sensor data,” the content of which is hereby incorporated herein in its entirety.”
Any inquiry concerning this communication or earlier communications from the examiner should be directed to RAFAEL VELASQUEZ VANEGAS whose telephone number is (571)272-6999. The examiner can normally be reached M-F 8 - 4.
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, VIVEK KOPPIKAR can be reached at (571) 272-5109. 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.
/RAFAEL VELASQUEZ VANEGAS/Patent Examiner, Art Unit 3667
/JOAN T GOODBODY/Examiner, Art Unit 3667
Prosecution Insights