DETAILED ACTION
This is a non-final Office Action on the merits in response to communications filed by Applicant on March 11th, 2026. Claims 1-26 are currently pending and examined below.
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 .
Response to Amendment
The amendments to the Claims filed on February 27th, 2026 have been entered. Claims 1, 13, and 25 are currently amended and pending, claims 4, 6, 11, 14, and 21, 26 are previously presented and pending, and claims 2-3, 5, 7-10, 12, 15-20, and 22-24 ae original, unamended, and pending.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are:
Claim 13 – 3D costmap receiving interface, start and end positions receiving interface, consecutive positions selecting module, planned path outputting interface
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
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 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, 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.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claim(s) 1-10, 13-14, 16-19, 21-23, 25, and 26 is/are rejected under 35 U.S.C. 103 as being unpatentable over US 10899008 B2 ("Sinyavskiy") in view of US 8515612 B2 ("Tanaka") in further view of US 10946521 B2 ("Yabushita").
Regarding claim 1, Sinyavskiy teaches a computer-implemented method of path planning for a mobile non-circular robot in an environment including obstacles, the computer-implemented method comprising (Sinyavskiy: Figures 1B-C and 7A-C robot 200, Abstract, “Systems and methods for robotic path planning are disclosed. In some implementations of the present disclosure, a robot can generate a cost map associated with an environment of the robot. The cost map can comprise a plurality of pixels each corresponding to a location in the environment, where each pixel can have an associated cost. The robot can further generate a plurality of masks having projected path portions for the travel of the robot within the environment, where each mask comprises a plurality of mask pixels that correspond to locations in the environment. The robot can then determine a mask cost associated with each mask based at least in part on the cost map and select a mask based at least in part on the mask cost. Based on the projected path portions within the selected mask, the robot can navigate a space.”, Column 21 lines 12-35, “The actual body shape of robot 200 is illustrated; however, footprint 702 can be the size of robot 200 configured in the software and/or hardware of robot 200 for determining how robot 200 can navigate and/or perform tasks. By way of illustration, footprint 702 can extend (as illustrated) beyond front side 704A, right side 704C, left side 704D, and/or back side 704B, creating a difference between what robot 200 perceives is the size of robot 200 in software and/or hardware (e.g., footprint 702) and what the actual size/shape of robot 200 is in reality.”, Column lines, “By way of illustration, FIG. 7B illustrates an elevated left side view of robot 200 with three wheels in accordance to some implementations of the present disclosure. Similarly, FIG. 7C illustrates an elevated right side view of robot 200 with three wheels in accordance to some implementations of the present disclosure. As illustrated, in some implementations, robot 200 can have three wheels, where two wheels (e.g., wheels 710Aand 710C) can be positioned proximal to back side 704B and one wheel (e.g., wheel 710B) can be positioned proximal to front side 704A.”. From the cited figures and passages, on of ordinary skill in the art would clearly see that the robot the path planning method is implemented on is non-circular.):
receiving a three-dimensional (3D) costmap (Sinyavskiy: Column 17 lines 35-56, “By way of illustration, the cost map can be a two-, three-, four- or more dimensional data structure wherein portions of the cost map correlate to locations (e.g., relative and/or absolute) in an environment. In some cases, those locations can be correlated to time, where the characteristics of the locations can change over time. For example, in a two-dimensional ("2D") map, each pixel can correlate at least in part to a physical location in the environment in which robot 200 navigates. Similarly, in a three-dimensional ("3D") map, each voxel can correlate at least in part to a physical location in the environment in which robot 200 navigates. In some implementations, a 2D map can be used where robot 200 operates in substantially planar operations (e.g., where the movements of robot 200, whether on a level surface or otherwise, operate within a plane, such as left, right, forward, back, and/or combinations thereof). In some implementations, a 3D map can be used where robot 200 operates in more than planar operations, such as up, down, row, pitch, and/or yaw in addition to left, right, forward, and back). Where a space has more characteristics associated with locations (e.g., temperature, time, complexity, etc.), there can be more dimensions to the map.”),
wherein the 3D costmap includes a two-dimensional (2D) map of a plane in which the mobile non-circular robot is movable (Sinyavskiy: Figure 5A, Column 18 lines 4-18, “FIG. 5A is an overhead view graphical representation of a cost map in accordance to some implementations of this disclosure. Cost map 502 includes a map that correlates with an environment of robot 200. For example, robot indicator 500 indicates the position of robot 200. In some cases, robot indicator 500 may not be actually present on cost map 502. Indicators 506A-506C can indicate at least in part the position of obstacles, such as walls. Indicator 504 can be indicative at least in part of a desirable travel path portion, wherein it is desirable for robot 200 to travel within indicator 504.”. One of ordinary skill in the art would see from the cited passage that, if the cost map is 3D, then the overhead view would be a 2D plane representing the environment in which the robot operates.)
and wherein the 3D costmap further includes a cost value for each position on the 2D map, the cost value indicative of a cost of at least one of a positioning or a movement of the mobile non-circular robot in a presence of one or more obstacles in an environment of the position (Sinyavskiy: Abstract, “Systems and methods for robotic path planning are disclosed. In some implementations of the present disclosure, a robot can generate a cost map associated with an environment of the robot. The cost map can comprise a plurality of pixels each corresponding to a location in the environment, where each pixel can have an associated cost. The robot can further generate a plurality of masks having projected path portions for the travel of the robot within the environment, where each mask comprises a plurality of mask pixels that correspond to locations in the environment. The robot can then determine a mask cost associated with each mask based at least in part on the cost map and select a mask based at least in part on the mask cost. Based on the projected path portions within the selected mask, the robot can navigate a space.”, Column 1 lines 61-67, “In one exemplary implementation, the method includes: generating a cost map associated with an environment of the robot, the cost map comprising a plurality of cost map pixels, each cost map pixel of the plurality corresponding to a respective location in the environment and each cost map pixel of the plurality having an associated cost;”, Column 17 line 57 – Column 18 line 3, Column 18 lines 4-18, Column 18 lines 19-25, “Indicators 506A-506C can have values associated with the pixels contained therein. These values can be indicative at least in part of a preference for robot 200 not to go to those locations (e.g., crash into the obstacles). Similarly, values can be associated with the pixels contained in indicator 504, indicating a preference for robot 200 to travel to those locations.”, “In some implementations, a value can be associated with one or more pixels (while pixel is used here, the principles are readily applicable to voxels and/or any other analog in different dimensions) of the cost map, indicative at least in part of the relative value associated with the pixel. For example, the cost map can comprise binary values, where one value can be indicative at least in part of areas to which it is desirable for a robot 200 to travel, and another indicative at least in part of places where it is not desirable for robot 200 to travel. As another example, the cost map may have different values associated with a pixel, wherein the magnitude of the value can be indicative at least in part of how desirable and/or undesirable it is for robot 200 to travel to the pixel.”, Column 34 lines 29-52, “FIG. 10 is a process flow diagram of an exemplary method 1000 for path planning in accordance with some implementations of this disclosure. Block 1002 includes Generating a cost map associated with an environment of the robot, the cost map comprising a plurality of cost map pixels each corresponding to a location in the environment and each cost map pixel having an associated cost.” Column 34 lines 53-67, “FIG. 11 is a process flow diagram of an exemplary method 1100 for path planning in accordance with some implementations of this disclosure. Block 1102 includes generating a cost map associated with at least a portion of the generated map of the environment, the cost map comprising a plurality of cost map pixels wherein each cost map pixel corresponds to a location in the environment and each cost map pixel has an associated cost.”, Column 35 lines 8-24, “FIG. 12 is a process flow diagram of an exemplary method 1200 for path planning in accordance with some implementations of this disclosure. Block 1202 includes generating a cost map associated with an environment of the robot, the cost map comprising a plurality of cost map pixels each corresponding to a location in the environment and each cost map pixel having an associated cost based at least in part on a desire to clean the location.”. The cited passages clearly teach that the cost map has a cost associated with each pixel of the cost map.),
wherein the at least one of the positioning or the movement includes an orientation of the mobile non-circular robot (Sinyavskiy: Column 10 lines 22-41, “In some cases, the path can include a route for travelling. For example, the route can include translation of a robot from a first location to a second location. The route can include a plurality of positions, orientations, and/or poses of a robot, such as a plurality of positions, orientations, and/or poses associated with locations in an environment.”, Column 25 lines 4-26, “For example, a plurality of path portions can be determined. FIG. 8B is a graphical representation of a three dimensional matrix 800 of path portion diagrams in accordance to some implementations of the present disclosure. Matrix 800 can include N path portions, where N can correlate to the desirable number of path portions to consider. In some cases, N can correlate with the number of trajectories ( e.g., 5000 trajectories and/or any other number), control characteristics, and/or be predetermined based at least in part by memory and/or processing power, speed of processing, complexity of the environment through which robot 200 navigates, the number of possible orientations of robot 200, the DOF of robot 200, the amount of space covered in the control characteristics, the amount of time covered in the control characteristics, and/or other factors.”, Column 27 lines 9-20, “In some cases, the relevant information from the shortest path field is the vector ( e.g., direction, orientation, pose, position, speed, etc.) of robot 200 at that point in order to travel the shortest path (e.g., shortest non-colliding path) to the selected point. Accordingly, a vector field can be generated showing the vector at each discretized point. FIG. 8F is an overhead diagram showing vectors for shortest paths associated with discretized points illustrated in FIG. 8D in accordance to some implementations of this disclosure. For example, point 830B corresponds to vector 838B, which gives the vector of robot 200 to travel the shortest path to point 830A.”. The cited passages clearly show that the orientation is included in the positioning and movement of the robot.);
receiving a start position and an end position of the mobile non-circular robot on the 3D costmap (Sinyavskiy: Column 26 lines 1-12, “As another example, the shortest path field can be computed. For example, an end point can be determined for robot 200. For every path, the shortest path to the end point can be determined given the present orientation of the robot. In this way, the shortest path can be determined for every point in a map. Such shortest path to the end point can be used to adjust values of the cost map thereby making shorter paths (and/or realistic paths) more favorable. In some cases, the map comprising shortest paths can be an additional map, essentially forming a cost map. In some implementations, the shortest paths can further take into account obstacles, such as by using known algorithms in the art.”, Column 32 lines 20-55, “For example, the interface can allow a user to edit a map, adjust a path, move a starting position (e.g., home marker), delete path/path segment, add operations (e.g., cleaning, manipulating, actuating, etc.), and/or any other manipulation a user could desire. For example, option 934A can allow a user to delete a path segment. For example, after selecting option 934A, a user can then select a portion of a path displayed in map 932 and/or path portions 940. Robot 200 can then delete such selected path portion. As another example, option 934B can allow a user to adjust a path. For example, a user can select a path portion included in map 932 and/or path portions 940 and move/manipulate that path portion. As another example, option 934C can allow a user to move a home marker (e.g., a starting position). For example, the starting position can be where robot 200 begins and/or ends a robotic operation.”. The cited passages clearly teach receiving a starting and ending point of the robot.),
wherein the start position includes a start orientation of the mobile non-circular robot, and wherein the end position includes an end orientation of the mobile non-circular robot (Sinyavskiy: Column 10 lines 22-41, “In some cases, the path can include a route for travelling. For example, the route can include translation of a robot from a first location to a second location. The route can include a plurality of positions, orientations, and/or poses of a robot, such as a plurality of positions, orientations, and/or poses associated with locations in an environment.”, Column 27 lines 21-61, “The vector can reflect the orientation, speed, position, pose, etc. of robot 200 as it begins the planned path portion and or trajectory. In some implementations, this vector can be of unit length in order to ease computation.”. One of ordinary skill in the art would see from the cited passages that the start and end positions include an orientation of the robot.);
iteratively selecting consecutive positions for a path to be planned, starting at the start position and terminating at the end position (Sinyavskiy: Column 26 lines 38-48, “In order to determine the shortest path, map portion 818 can be discretized, such as by looking at a plurality of points. FIG. 8D is an overhead diagram illustrating a discretized version of map portion 818, wherein each point is a discrete location in accordance with implementations of this disclosure. For example, point 830A can be a discretized point in map portion 818. In some implementations, non-navigable points can be included in the discretization, such as point 834, which can be within obstacle 822. In some implementations, non-navigable points may not be included. In some cases, each discretized point can also be called a cell.”, Column 26 lines 49-58, “In order to determine the shortest path (e.g., in a shortest path field), a point can be selected. Any point can be used, however, in some implementations, the point is a point along the horizon of robot 200, such as the substantially furthest point robot 200 can seeing going forward along the path (e.g., furthest in distance and/or time). Advantageously, this can allow robot 200 to plan the path going forward for when it travels. Robot 200 can then find the shortest non-colliding point from each discretized point (such as the discretized points illustrated in FIG. SD) to that selected point.”. The cited passages clearly teach iteratively selecting consecutive points for a path from a start point to an end point.),
and wherein the cumulative cost value further includes a stress value, wherein the stress value is indicative of a change in a movement direction along the path (Sinyavskiy: Column 27 lines 22-61, “In other cases, a penalty can be assigned to path portions and/or trajectories corresponding to vectors that substantially differ from the angle of the trajectory associated with the shortest path. Such a penalty can be realized in a recovery matrix, cost map, and/or matrix (e.g., matrix 800), such as through a cost value, multiplier and/or additive. In some cases, the comparison can be computed by examining the dot product between the vector of the shortest path and the vector of the vector of a path portion and/or trajectory calculated by robot 200. In this way, when a trajectory and/or path portion has the appropriate direction that is substantially similar to the direction of the shortest path, it will be reflected in the dot product. This dot product can be a dependency of the cost function such that the value of trajectories and/or path portions that have the same initial direction as the shortest path are favored.”. The cited passage clearly teaches that the change in direction of the robot along potential path portions is taken into account in the cost function. Specifically, the cost function can have a penalty that quantifies the difference in angle between the path potions and favours those without a significant change in direction.);
and outputting the path based on the iteratively selected consecutive positions (Sinyavskiy: Column 25 lines 43-55, “Block 410 can include selecting a first path portion from the plurality of path portions based at least in part on the cost of each of the path portions. For example, the dot product between the cost map and a mask can be taken in order to find the cost associated with a mask. Where higher values in the cost map are assigned to places to which it is desirable for robot 200 to travel, finding the substantial maximum and/or higher values as a result of the dot product can be indicative of an optimal path. As another example, where lower values in the cost map are assigned to places to which it is desirable that robot 200 travels, finding the substantial minimum and/or lower values as a result of the dot product can be indicative of an optimal path.”, Column 33 lines 21-29, “Returning to FIG. 4, block 412 can include determining actuator commands for the first path portions. The actuator commands can allow robot 200 to travel along the path portion, such as in accordance to one or more control characteristics.”).
Sinyavskiy does not teach wherein the iteratively selecting includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap,
and the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions.
Tanaka, in the same field of endeavor, teaches wherein the iteratively selecting includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap (Tanaka: Figure 6 and 7, Column 13 lines 38-65, “Next, the route planning unit 35 performs the shortest route search using a search algorithm such as the well-known A* algorithm (A star algorithm) or the like and decides the travel route. Specifically, the route planning unit 35 decides the travel route 350 by using, as shown in FIG. 7, the A* algorithm with the starting position 351 and the goal position 352 as the base points, and computing through which node 342 and which link 343 on the integrated map need to be travelled in order to achieve the minimum cost (shortest route).”. As can be seen from the cited passages and figures, the nodes are iteratively selected such that they minimize a cost. Furthermore, one of ordinary skill in the would see that this cost is a cumulative cost because it calculates the cost of each node travelled to between the start and end nodes.).
Sinyavskiy teaches a computer-implemented method of path planning for a mobile non-circular robot in an environment including obstacles, the computer-implemented method comprising: receiving a three-dimensional (3D) costmap wherein the 3D costmap includes a two-dimensional (2D) map of a plane in which the mobile non-circular robot is movable and wherein the 3D costmap further includes a cost value for each position on the 2D map, the cost value indicative of a cost of at least one of a positioning or a movement of the mobile non-circular robot in the presence of one or more obstacles in an environment of the position, wherein the at least one of the positioning or the movement includes an orientation of the mobile non-circular robot; receiving a start position and an end position of the mobile non-circular robot on the 3D costmap, wherein the start position includes a start orientation of the mobile non-circular robot, and wherein the end position includes an end orientation of the mobile non-circular robot; iteratively selecting consecutive positions for a path to be planned, starting at the start position and terminating at the end position, and wherein the cumulative cost value further includes a stress value, wherein the stress value is indicative of a change in a movement direction along the path; and outputting the path based on the iteratively selected consecutive positions. Sinyavskiy does not teach wherein the iteratively selecting includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap. Tanaka teaches wherein the iteratively selecting includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap. A person of ordinary skill in the art would have had the technological capabilities required to have modified the computer computer-implemented method of path planning for a mobile non-circular robot taught in Sinyavskiy with wherein the iteratively selecting includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap taught in Tanaka. Furthermore, the method of path planning taught in Sinyavskiy teaches selecting the path potions that minimize the cost from the start point to the end point, but does not explicitly teach minimizing the cost when iteratively selecting the discretized points of the cost map. Therefore, a person of ordinary skill in the art would have been able to modify the iterative selection of points taught in Sinyavskiy with the method of minimizing the cumulative cost function during the iterative selection of points as taught in Tanaka without changing or introducing new functionality. No inventive effort would have been required. The combination would have yielded the predictable result of a computer-implemented method of path planning for a mobile non-circular robot wherein the iteratively selecting includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to have combine the computer-implemented method of path planning for a mobile non-circular robot taught in Sinyavskiy with wherein the iteratively selecting includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap taught in Tanaka with a reasonable expectation of success. One of ordinary skill in the art would have been motivated to make this modification because the combination would have yielded predictable results.
Sinyavskiy in view of Tanaka does not teach the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions.
Yabushita, in the same field of endeavor, teaches the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions (Yabushita: Column 11 lines 1-20, “Alternatively, a plurality of provisional moving paths in which the continuity of the change in the turning angle has been guaranteed are found, then a preferable provisional moving path may be selected from among them, and the selected provisional moving path may be determined to be the determined moving path. In this case, the provisional moving path in which the path cost calculated for each provisional moving path becomes minimum may be selected. Specifically, the cost for the movement between grids that are adjacent to each other on the xy plane may be determined in advance, and the provisional moving path in which the total cost accumulated up to the timing when the robot reaches the destination point becomes minimum is selected. The cost for the movement between predetermined grids is determined, for example, in proportion to the distance between these grids. As a matter of course, a further adjustment may be added. For example, a higher cost may be imposed when the grid is close to the obstacle.”, Column 11 lines 49-64, “Various methods may be employed to select the grid trajectory. In this example, by selecting the grid trajectory in which the turning angle cost added to the change in the turning angle in the path layer becomes minimum, the turning angle during the movement is determined. The turning angle cost is a predetermined cost accumulated when the robot moves between the grids adjacent to each other in the path layer, and is set in such a way that the cost is in proportion to, for example, the magnitude of the turning angle. The cost to be set may be adjusted in such a way that, for example, a large cost is added when a grid is close to the obstacle, a smaller cost is added in a case where the robot turns by a great degree by one change than the cost added in a case where the robot turns by a small degree frequently, or a large cost is added to a specific turning angle due to hardware restrictions of the moving robot 100.”, Column 13 lines 1-26, “When a plurality of provisional moving paths have been found, the process goes to Step S108, where one of the provisional moving paths is selected in accordance with a predetermined condition and the selected path is determined to be the moving path along which the moving robot 100 moves. Specifically, as described above, the provisional moving path in which the path cost calculated for each provisional moving path becomes minimum may be, for example, selected.”, Column 13 lines 35-46, “When a plurality of grid trajectories have been found, the process goes to Step S111, where one grid trajectory is selected in accordance with a predetermined condition and this grid trajectory is determined to be the turning angle during the movement. Specifically, as described above, for example, the grid trajectory in which the turning angle cost added to the change in the turning angle in the path layer becomes minimum may be selected.”. The cited passage clearly teaches that, in determining a path for the robot, the system minimizes a cumulative cost function. This cost function is based on both the cost of movement between girds on the cost map (i.e. the shortest most direct path that requires the least grids traversed would be minimum) and both the magnitude of the turning angle and the frequency of the turning angle (Column 11 lines 49-64 describes the cost function of the turning angle being larger the larger the magnitude of the turning angle and being larger if the robot makes frequent small turns.). One of ordinary skill in the art would recognize that these two aspects quantify a movement shift of the robot and because they are cumulative are based on both a current movement shift and previous movement shift.).
Sinyavskiy in view of Tanaka teaches a computer-implemented method of path planning for a mobile non-circular robot in an environment including obstacles, the computer- implemented method comprising: receiving a three-dimensional (3D) costmap, wherein the 3D costmap includes a two-dimensional (2D) map of a plane in which the mobile non-circular robot is movable, and wherein the 3D costmap further includes a cost value for each position on the 2D map, the cost value indicative of a cost of at least one of a positioning or a movement of the mobile non-circular robot in a presence of one or more obstacles in an environment of the position, wherein the at least one of the positioning or the movement includes an orientation of the mobile non-circular robot; receiving a start position and an end position of the mobile non-circular robot on the 3D costmap, wherein the start position includes a start orientation of the mobile non-circular robot, and wherein the end position includes an end orientation of the mobile non-circular robot; iteratively selecting consecutive positions for a path to be planned, starting at the start position and terminating at the end position, wherein the iteratively selecting includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap, and wherein the cumulative cost value further includes a stress value, wherein the stress value is indicative of a change in a movement direction along the path; and outputting the path based on the iteratively selected consecutive positions. Sinyavskiy in view of Tanaka does not teach the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions. Yabushita teaches the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions. A person of ordinary skill in the art would have had the technological capabilities to have modified the method taught in Sinyavskiy in view of Tanaka with the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions taught in Yabushita. Furthermore, the method taught in Sinyavskiy in view of Tanaka teaches selecting the path by minimizing the movement shift between the potential route and the shortest determined route. This is accomplished by comparing the vectors at each point in the cost grid, wherein each vector includes the state of the robot (position, orientation, speed, velocity, etc.) and minimizing the difference between the vectors. Additionally, the cost function used is cumulative. As such, one of ordinary skill in the art would have been able to modify the method of Sinyavskiy in view of Tanaka with the method of determining the stress value based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions of the potential trajectory as taught in Yabushita because the method of Sinyavskiy in view of Tanaka teaches a similar process but performed between two trajectories rather than just the potential trajectory itself. Such a modification would not have changed or introduced new functionality. No inventive effort would have been required. The combination would have yielded the predictable result of a computer-implemented method of path planning for a mobile non-circular robot in an environment including the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to have combine the method taught in Sinyavskiy in view of Tanaka with the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions taught in Yabushita with a reasonable expectation of success. One of ordinary skill in the art would have been motivated to make this modification because the combination would have yielded predictable results.
Regarding claim 2, Sinyavskiy in view of Tanaka in further view of Yabushita teaches wherein the 2D map of the plane includes a grid, and wherein nodes on the grid include selectable positions (Sinyavskiy: Figure 8D, Column 26 lines 38-48, “In order to determine the shortest path, map portion 818 can be discretized, such as by looking at a plurality of points. FIG. 8D is an overhead diagram illustrating a discretized version of map portion 818, wherein each point is a discrete location in accordance with implementations of this disclosure. For example, point 830A can be a discretized point in map portion 818. In some implementations, non-navigable points can be included in the discretization, such as point 834, which can be within obstacle 822. In some implementations, non-navigable points may not be included. In some cases, each discretized point can also be called a cell.”.).
Regarding claim 3, Sinyavskiy in view of Tanaka in further view of Yabushita teaches wherein the 3D costmap includes a number of copies per node of the grid wherein each copy includes a differently rotated orientation of the mobile non-circular robot, and wherein the differently rotated orientation is rotated by a fraction k/N of a full angle 2[Symbol font/0x70]k/N for any integer k less than N (Yabushita: Figures 7 and 9, Column 7 lines 58-67, “When the spatial layer AL is created for each turning angle, the spatial layers AL are layered on one another in the order of the turning angle to complete the environmental map. FIG. 7 is a diagram for describing the three-dimensional structure of the environmental map. While "1" or "0" is associated with each grid GD in the spatial layer AL as shown in FIG. 6B, FIG. 7 shows a diagram in which the no-entry area NA overlaps the grid GD, as shown in FIG. 6A, for conceptual understanding. In the following several drawings, the spatial layer AL is expressed in this way.”, Column 8 lines 1-10, “The step angle of the turning angle 8 is determined while the amount of calculation that can be allowed or the like is being taken into consideration. In this example, the step angle is set to 5°. That is, 72 spatial layers AL whose turning angle 8 is from 0° to 355° are created and are layered on one another. Since the turning angle 8 is 360°, which is equal to 0°, it can be considered that the spatial layer AL with the turning angle 8 of 0° and the spatial layer AL with the turning angle 8 of 355° are layered on one another in such a way that they are adjacent to each other.”, Column 9 lines 5-14, “FIG. 9 is a diagram showing a relation between the provisional moving path and the spatial layer AL for each turning angle. In FIG. 9, the trajectory shown by the grid GD surrounded by the thick frame indicates the provisional moving path set for the m (m is an integer equal to or larger than two)-th time. That is, it means that the robot could not reach from the departure point grid GDs to the destination point grid GDg in the provisional moving paths set from the first time to the (m-1)-th time no matter which angle the robot has.”. The cited passages clearly teach generating a number of copies of the grid for each angle of rotation from 0 to 355. In each copy, each grid will have the same rotation value. Furthermore, it is clear that the angle of rotation for each copy is rotated by a fraction k/N of a full angle 2[Symbol font/0x70]k/N, because in the example provided, there are 72 copies, each rotated by 5 degrees. This means k = 1 and N = 72 in the given example.).
Regarding claim 4, Sinyavskiy in view of Tanaka in further view of Yabushita teaches wherein the iteratively selecting the consecutive positions comprises applying a greedy search algorithm (Sinyavskiy: Column 25 lines 56-67, “However, there can be other factors considered in addition to the cost and/or modifying the cost. For example, the maneuvering time for path portions can be considered. By way of illustration, a predetermined maneuvering time threshold can be predetermined. If maneuvering to complete a path portion takes longer than the predetermined maneuvering time threshold, the path portion can be disregarded and/or given a penalty (e.g., increasing the cost by a multiplier and/or additive). As another example, the cost map can be adjusted to reflect time saving maneuvers. By way of illustration, robot 200 can take a greedy approach in finding paths to maximize speed of maneuvering.”. The robot is clearly configured to use a greedy algorithm in the path planning determination.).
Regarding claim 5, Sinyavskiy in view of Tanaka in further view of Yabushita teaches wherein the greedy search algorithm is one of an A-star (A*) algorithm; a Dijkstra’s algorithm; or a D-star-Lite (D*-Lite) algorithm (Tanaka: Column 13 lines 38-65, “Next, the route planning unit 35 performs the shortest route search using a search algorithm such as the well-known A* algorithm (A star algorithm) or the like and decides the travel route. Specifically, the route planning unit 35 decides the travel route 350 by using, as shown in FIG. 7, the A* algorithm with the starting position 351 and the goal position 352 as the base points, and computing through which node 342 and which link 343 on the integrated map need to be travelled in order to achieve the minimum cost (shortest route).”).
Regarding claim 6, Sinyavskiy in view of Tanaka in further view of Yabushita teaches further comprising at least one of: generating the 3D costmap; or updating the 3D costmap in response to a change in positions of the one or more obstacles (Sinyavskiy: Column 1 lines 61-67, “In one exemplary implementation, the method includes: generating a cost map associated with an environment of the robot, the cost map comprising a plurality of cost map pixels, each cost map pixel of the plurality corresponding to a respective location in the environment and each cost map pixel of the plurality having an associated cost;”, Column 16 lines 54-67, “Block 404 includes generating a cost map associated with an environment of a robot.”, Column 17 lines 35-56, “By way of illustration, the cost map can be a two-, three-, four- or more dimensional data structure wherein portions of the cost map correlate to locations (e.g., relative and/or absolute) in an environment. In some cases, those locations can be correlated to time, where the characteristics of the locations can change over time. For example, in a two-dimensional ("2D") map, each pixel can correlate at least in part to a physical location in the environment in which robot 200 navigates. Similarly, in a three-dimensional ("3D") map, each voxel can correlate at least in part to a physical location in the environment in which robot 200 navigates. In some implementations, a 2D map can be used where robot 200 operates in substantially planar operations (e.g., where the movements of robot 200, whether on a level surface or otherwise, operate within a plane, such as left, right, forward, back, and/or combinations thereof). In some implementations, a 3D map can be used where robot 200 operates in more than planar operations, such as up, down, row, pitch, and/or yaw in addition to left, right, forward, and back). Where a space has more characteristics associated with locations (e.g., temperature, time, complexity, etc.), there can be more dimensions to the map.”, Column 18 lines 57-67, “In some implementations, the cost map can be dynamic, changing over time and as robot 200 moves. For example, objects in the environment (e.g., as indicated by indicators 506A-506C) can move over time. Moreover, values of pixels in indicator 504 can also change over time. For example, after robot 200 travels across a pixel, it may become less preferable, or not preferable at all, for robot 200 to travel to the location associated with the pixel again.”. The cited passage clearly teaches that the cost map is dynamic and changes in response to the movement of obstacles.).
Regarding claim 7, Sinyavskiy in view of Tanaka in further view of Yabushita teaches further comprising: executing, by the mobile non-circular robot, the path (Sinyavskiy: Column 33 lines 21-29, “Returning to FIG. 4, block 412 can include determining actuator commands for the first path portions. The actuator commands can allow robot 200 to travel along the path portion, such as in accordance to one or more control characteristics.”).
Regarding claim 8, Sinyavskiy in view of Tanaka in further view of Yabushita teaches wherein the mobile non-circular robot comprises a holonomic robot (Tanaka: Column 10 lines 4-23, “Thus, the autonomous mobile device 1 preferably includes a main body 10 provided with an electric motor 12 at the lower portion thereof and an onmi wheel 13 that is driven with the electric motor 12, and a laser range finder 20 to measure the distance to the obstacles existing in the periphery.”, Column 10 lines 24-35, “An onmi wheel 13 is mounted to a drive shaft 12A of each of the four electric motors 12. Specifically, the four onmi wheels 13 are mounted by being spaced at 90° intervals along the circumferential direction in a concyclic manner.”, Column 10 lines 36-52, “Based on this configuration, when the electric motor 12 is driven and the wheel 14 is rotated, the six free rollers 15 rotate integrally with the wheels 14. Meanwhile, as a result of the grounded free rollers 15 rotating, the omni wheel 13 can also move in a direction that is parallel with the rotating shaft of that wheel 14. Thus, by independently controlling the four electric motors 12 and independently adjusting the rotating direction and rotating speed of the respective four omni wheels 13, the autonomous mobile device 1 can be moved in an arbitrary direction (omni directionally).”. One of ordinary skill in the art would see from the cited passages that the robot is a holonomic robot, as it can move in any direction without first having to rotate.).
Regarding claim 9, Sinyavskiy in view of Tanaka in further view of Yabushita teaches wherein the 3D costmap is based on a convex hull of a footprint of the mobile non-circular robot onto the 2D map of the plane (Sinyavskiy: Figure 7A, Column 20 lines 48-67, “Block 406 then includes projecting a plurality of path portions relative to robot 200. These trajectories can comprise possible trajectories of robot 200 in a space. In some implementations, these trajectories can take into account the shape of robot 200. For example, robot 200 can have a size and shape as determined by the chassis and/or external elements of robot 200. Moreover, robot 200 can have a predetermined footprint, which can include the size and shape in which robot 200 perceives itself. In order to illustrate a robot's predefined footprint of itself, FIG. 7A is a top view diagram illustrating robot footprint 702 of robot 200 in accordance with some implementations of this disclosure.”. One of ordinary skill in the art would see that the footprint of the robot is clearly convex.),
and wherein the 3D costmap is further based on a safety area around the convex hull (Sinyavskiy: Column 21 lines 12-53, “The actual body shape of robot 200 is illustrated; however, footprint 702 can be the size of robot 200 configured in the software and/or hardware of robot 200 for determining how robot 200 can navigate and/or perform tasks. By way of illustration, footprint 702 can extend (as illustrated) beyond front side 704A, right side 704C, left side 704D, and/or back side 704B, creating a difference between what robot 200 perceives is the size of robot 200 in software and/or hardware (e.g., footprint 702) and what the actual size/shape of robot 200 is in reality. This can allow clearance between robot 200 and/or objects in an environment. Advantageously, footprint 702 can allow a safety buffer for navigation. The size and/or shape of footprint 702 can be based at least in part on a number of factors, including desired clearance, complexity of environments, tolerance to assists, risk of collision (e.g., the occurrence of, the amount of damage of, etc.), and/or other factors. As illustrated, foot print 702 is rectangular; however, footprint 702 can take on any shape desirable, such as square, triangular, rectangular, parallelogram asymmetric shapes, curves, etc. Moreover, footprint 702 is illustrated from a top view, seen as two dimensional.”. From the cited passage, one of ordinary skill in the art would see that, because the footprint can be extended to a size larger than the robot in order to provide a safety buffer, this is a form of safety area around the convex hull.).
Regarding claim 10, Sinyavskiy in view of Tanaka in further view of Yabushita teaches wherein the cumulative cost value further increases with at least one of: a change of orientation of the mobile non-circular robot; a veering away from at least one of the end position or the start position; and a repeated traversal of a position along the path (Sinyavskiy: Column 27 lines 22-61, “In other cases, a penalty can be assigned to path portions and/or trajectories corresponding to vectors that substantially differ from the angle of the trajectory associated with the shortest path. Such a penalty can be realized in a recovery matrix, cost map, and/or matrix (e.g., matrix 800), such as through a cost value, multiplier and/or additive. In some cases, the comparison can be computed by examining the dot product between the vector of the shortest path and the vector of the vector of a path portion and/or trajectory calculated by robot 200. In this way, when a trajectory and/or path portion has the appropriate direction that is substantially similar to the direction of the shortest path, it will be reflected in the dot product. This dot product can be a dependency of the cost function such that the value of trajectories and/or path portions that have the same initial direction as the shortest path are favored.”. The cited passage clearly teaches that the change in direction of the robot along potential path portions is taken into account in the cost function. Specifically, the cost function can have a penalty that quantifies the difference in angle between the path potions and favours those without a significant change in direction.).
Regarding claim 13, Sinyavskiy teaches a computing device for path planning for a mobile non-circular robot in an environment including obstacles, the computing device comprising (Sinyavskiy: Figures 1B-C and 7A-C robot 200, Abstract, “Systems and methods for robotic path planning are disclosed. In some implementations of the present disclosure, a robot can generate a cost map associated with an environment of the robot. The cost map can comprise a plurality of pixels each corresponding to a location in the environment, where each pixel can have an associated cost. The robot can further generate a plurality of masks having projected path portions for the travel of the robot within the environment, where each mask comprises a plurality of mask pixels that correspond to locations in the environment. The robot can then determine a mask cost associated with each mask based at least in part on the cost map and select a mask based at least in part on the mask cost. Based on the projected path portions within the selected mask, the robot can navigate a space.”, Column 11 lines 64-67, “Controller 204 can control the various operations performed by robot 200.”, Column 12 lines 13-42, “Controller 204 can be operatively and/or communicatively coupled to memory 202. … . Memory 202 can provide instructions and data to controller 204. For example, memory 202 can be a non-transitory, computer-readable storage apparatus and/or medium having a plurality of instructions stored thereon, the instructions being executable by a processing apparatus ( e.g., controller 204) to operate robot 200.”, Column 21 lines 12-35, “The actual body shape of robot 200 is illustrated; however, footprint 702 can be the size of robot 200 configured in the software and/or hardware of robot 200 for determining how robot 200 can navigate and/or perform tasks. By way of illustration, footprint 702 can extend (as illustrated) beyond front side 704A, right side 704C, left side 704D, and/or back side 704B, creating a difference between what robot 200 perceives is the size of robot 200 in software and/or hardware (e.g., footprint 702) and what the actual size/shape of robot 200 is in reality.”, Column lines, “By way of illustration, FIG. 7B illustrates an elevated left side view of robot 200 with three wheels in accordance to some implementations of the present disclosure. Similarly, FIG. 7C illustrates an elevated right side view of robot 200 with three wheels in accordance to some implementations of the present disclosure. As illustrated, in some implementations, robot 200 can have three wheels, where two wheels (e.g., wheels 710Aand 710C) can be positioned proximal to back side 704B and one wheel (e.g., wheel 710B) can be positioned proximal to front side 704A.”. From the cited figures and passages, on of ordinary skill in the art would clearly see that the robot the path planning method is implemented on is non-circular.):
a 3D costmap receiving interface configured to receive a three-dimensional (3D) costmap (Sinyavskiy: Column 11 lines 64-67, “Controller 204 can control the various operations performed by robot 200.”, Column 12 lines 13-42, “Controller 204 can be operatively and/or communicatively coupled to memory 202. … . Memory 202 can provide instructions and data to controller 204. For example, memory 202 can be a non-transitory, computer-readable storage apparatus and/or medium having a plurality of instructions stored thereon, the instructions being executable by a processing apparatus ( e.g., controller 204) to operate robot 200.”, Column 17 lines 35-56, “By way of illustration, the cost map can be a two-, three-, four- or more dimensional data structure wherein portions of the cost map correlate to locations (e.g., relative and/or absolute) in an environment. In some cases, those locations can be correlated to time, where the characteristics of the locations can change over time. For example, in a two-dimensional ("2D") map, each pixel can correlate at least in part to a physical location in the environment in which robot 200 navigates. Similarly, in a three-dimensional ("3D") map, each voxel can correlate at least in part to a physical location in the environment in which robot 200 navigates. In some implementations, a 2D map can be used where robot 200 operates in substantially planar operations (e.g., where the movements of robot 200, whether on a level surface or otherwise, operate within a plane, such as left, right, forward, back, and/or combinations thereof). In some implementations, a 3D map can be used where robot 200 operates in more than planar operations, such as up, down, row, pitch, and/or yaw in addition to left, right, forward, and back). Where a space has more characteristics associated with locations (e.g., temperature, time, complexity, etc.), there can be more dimensions to the map.”. The processor clearly functions as the 3D costmap receiving interface),
wherein the 3D costmap includes a two-dimensional (2D) map of a plane in which the mobile non-circular robot is movable (Sinyavskiy: Figure 5A, Column 18 lines 4-18, “FIG. 5A is an overhead view graphical representation of a cost map in accordance to some implementations of this disclosure. Cost map 502 includes a map that correlates with an environment of robot 200. For example, robot indicator 500 indicates the position of robot 200. In some cases, robot indicator 500 may not be actually present on cost map 502. Indicators 506A-506C can indicate at least in part the position of obstacles, such as walls. Indicator 504 can be indicative at least in part of a desirable travel path portion, wherein it is desirable for robot 200 to travel within indicator 504.”. One of ordinary skill in the art would see from the cited passage that, if the cost map is 3D, then the overhead view would be a 2D plane representing the environment in which the robot operates.)
and wherein the 3D costmap further includes a cost value for each position on the 2D map, the cost value indicative of a cost of at least one of a positioning or a movement of the mobile non-circular robot in a presence of one or more obstacles in an environment of the position (Sinyavskiy: Abstract, “Systems and methods for robotic path planning are disclosed. In some implementations of the present disclosure, a robot can generate a cost map associated with an environment of the robot. The cost map can comprise a plurality of pixels each corresponding to a location in the environment, where each pixel can have an associated cost. The robot can further generate a plurality of masks having projected path portions for the travel of the robot within the environment, where each mask comprises a plurality of mask pixels that correspond to locations in the environment. The robot can then determine a mask cost associated with each mask based at least in part on the cost map and select a mask based at least in part on the mask cost. Based on the projected path portions within the selected mask, the robot can navigate a space.”, Column 1 lines 61-67, “In one exemplary implementation, the method includes: generating a cost map associated with an environment of the robot, the cost map comprising a plurality of cost map pixels, each cost map pixel of the plurality corresponding to a respective location in the environment and each cost map pixel of the plurality having an associated cost;”, Column 17 line 57 – Column 18 line 3, Column 18 lines 4-18, Column 18 lines 19-25, “Indicators 506A-506C can have values associated with the pixels contained therein. These values can be indicative at least in part of a preference for robot 200 not to go to those locations (e.g., crash into the obstacles). Similarly, values can be associated with the pixels contained in indicator 504, indicating a preference for robot 200 to travel to those locations.”, “In some implementations, a value can be associated with one or more pixels (while pixel is used here, the principles are readily applicable to voxels and/or any other analog in different dimensions) of the cost map, indicative at least in part of the relative value associated with the pixel. For example, the cost map can comprise binary values, where one value can be indicative at least in part of areas to which it is desirable for a robot 200 to travel, and another indicative at least in part of places where it is not desirable for robot 200 to travel. As another example, the cost map may have different values associated with a pixel, wherein the magnitude of the value can be indicative at least in part of how desirable and/or undesirable it is for robot 200 to travel to the pixel.”, Column 34 lines 29-52, “FIG. 10 is a process flow diagram of an exemplary method 1000 for path planning in accordance with some implementations of this disclosure. Block 1002 includes Generating a cost map associated with an environment of the robot, the cost map comprising a plurality of cost map pixels each corresponding to a location in the environment and each cost map pixel having an associated cost.” Column 34 lines 53-67, “FIG. 11 is a process flow diagram of an exemplary method 1100 for path planning in accordance with some implementations of this disclosure. Block 1102 includes generating a cost map associated with at least a portion of the generated map of the environment, the cost map comprising a plurality of cost map pixels wherein each cost map pixel corresponds to a location in the environment and each cost map pixel has an associated cost.”, Column 35 lines 8-24, “FIG. 12 is a process flow diagram of an exemplary method 1200 for path planning in accordance with some implementations of this disclosure. Block 1202 includes generating a cost map associated with an environment of the robot, the cost map comprising a plurality of cost map pixels each corresponding to a location in the environment and each cost map pixel having an associated cost based at least in part on a desire to clean the location.”. The cited passages clearly teach that the cost map has a cost associated with each pixel of the cost map.),
wherein the at least one of the positioning or the movement includes an orientation of the mobile non-circular robot (Sinyavskiy: Column 10 lines 22-41, “In some cases, the path can include a route for travelling. For example, the route can include translation of a robot from a first location to a second location. The route can include a plurality of positions, orientations, and/or poses of a robot, such as a plurality of positions, orientations, and/or poses associated with locations in an environment.”, Column 25 lines 4-26, “For example, a plurality of path portions can be determined. FIG. 8B is a graphical representation of a three dimensional matrix 800 of path portion diagrams in accordance to some implementations of the present disclosure. Matrix 800 can include N path portions, where N can correlate to the desirable number of path portions to consider. In some cases, N can correlate with the number of trajectories ( e.g., 5000 trajectories and/or any other number), control characteristics, and/or be predetermined based at least in part by memory and/or processing power, speed of processing, complexity of the environment through which robot 200 navigates, the number of possible orientations of robot 200, the DOF of robot 200, the amount of space covered in the control characteristics, the amount of time covered in the control characteristics, and/or other factors.”, Column 27 lines 9-20, “In some cases, the relevant information from the shortest path field is the vector ( e.g., direction, orientation, pose, position, speed, etc.) of robot 200 at that point in order to travel the shortest path (e.g., shortest non-colliding path) to the selected point. Accordingly, a vector field can be generated showing the vector at each discretized point. FIG. 8F is an overhead diagram showing vectors for shortest paths associated with discretized points illustrated in FIG. 8D in accordance to some implementations of this disclosure. For example, point 830B corresponds to vector 838B, which gives the vector of robot 200 to travel the shortest path to point 830A.”. The cited passages clearly show that the orientation is included in the positioning and movement of the robot.);
a start and end positions receiving interface configured to receive a start position and an end position of the mobile non-circular robot on the 3D costmap (Sinyavskiy: Column 11 lines 64-67, “Controller 204 can control the various operations performed by robot 200.”, Column 12 lines 13-42, “Controller 204 can be operatively and/or communicatively coupled to memory 202. … . Memory 202 can provide instructions and data to controller 204. For example, memory 202 can be a non-transitory, computer-readable storage apparatus and/or medium having a plurality of instructions stored thereon, the instructions being executable by a processing apparatus ( e.g., controller 204) to operate robot 200.”, Column 26 lines 1-12, “As another example, the shortest path field can be computed. For example, an end point can be determined for robot 200. For every path, the shortest path to the end point can be determined given the present orientation of the robot. In this way, the shortest path can be determined for every point in a map. Such shortest path to the end point can be used to adjust values of the cost map thereby making shorter paths (and/or realistic paths) more favorable. In some cases, the map comprising shortest paths can be an additional map, essentially forming a cost map. In some implementations, the shortest paths can further take into account obstacles, such as by using known algorithms in the art.”, Column 32 lines 20-55, “For example, the interface can allow a user to edit a map, adjust a path, move a starting position (e.g., home marker), delete path/path segment, add operations (e.g., cleaning, manipulating, actuating, etc.), and/or any other manipulation a user could desire. For example, option 934A can allow a user to delete a path segment. For example, after selecting option 934A, a user can then select a portion of a path displayed in map 932 and/or path portions 940. Robot 200 can then delete such selected path portion. As another example, option 934B can allow a user to adjust a path. For example, a user can select a path portion included in map 932 and/or path portions 940 and move/manipulate that path portion. As another example, option 934C can allow a user to move a home marker (e.g., a starting position). For example, the starting position can be where robot 200 begins and/or ends a robotic operation.”. The cited passages clearly teach receiving a starting and ending point of the robot. Furthermore, the processor clearly functions as the start and end positions receiving interface.),
wherein the start position includes a start orientation of the mobile non-circular robot, and wherein the end position includes an end orientation of the mobile non-circular robot (Sinyavskiy: Column 10 lines 22-41, “In some cases, the path can include a route for travelling. For example, the route can include translation of a robot from a first location to a second location. The route can include a plurality of positions, orientations, and/or poses of a robot, such as a plurality of positions, orientations, and/or poses associated with locations in an environment.”, Column 27 lines 21-61, “The vector can reflect the orientation, speed, position, pose, etc. of robot 200 as it begins the planned path portion and or trajectory. In some implementations, this vector can be of unit length in order to ease computation.”. One of ordinary skill in the art would see from the cited passages that the start and end positions include an orientation of the robot.);
a consecutive positions selecting module configured to iteratively select consecutive positions for a path to be planned, starting at the start position and terminating at the end position (Sinyavskiy: Column 11 lines 64-67, “Controller 204 can control the various operations performed by robot 200.”, Column 12 lines 13-42, “Controller 204 can be operatively and/or communicatively coupled to memory 202. … . Memory 202 can provide instructions and data to controller 204. For example, memory 202 can be a non-transitory, computer-readable storage apparatus and/or medium having a plurality of instructions stored thereon, the instructions being executable by a processing apparatus ( e.g., controller 204) to operate robot 200.”, Column 26 lines 38-48, “In order to determine the shortest path, map portion 818 can be discretized, such as by looking at a plurality of points. FIG. 8D is an overhead diagram illustrating a discretized version of map portion 818, wherein each point is a discrete location in accordance with implementations of this disclosure. For example, point 830A can be a discretized point in map portion 818. In some implementations, non-navigable points can be included in the discretization, such as point 834, which can be within obstacle 822. In some implementations, non-navigable points may not be included. In some cases, each discretized point can also be called a cell.”, Column 26 lines 49-58, “In order to determine the shortest path (e.g., in a shortest path field), a point can be selected. Any point can be used, however, in some implementations, the point is a point along the horizon of robot 200, such as the substantially furthest point robot 200 can seeing going forward along the path (e.g., furthest in distance and/or time). Advantageously, this can allow robot 200 to plan the path going forward for when it travels. Robot 200 can then find the shortest non-colliding point from each discretized point (such as the discretized points illustrated in FIG. SD) to that selected point.”. The cited passages clearly teach iteratively selecting consecutive points for a path from a start point to an end point. Furthermore, the processor clearly functions as the consecutive positions selecting module.),
and wherein the cumulative cost value further includes a stress value, wherein the stress value is indicative of a change in a movement direction along the path (Sinyavskiy: Column 27 lines 22-61, “In other cases, a penalty can be assigned to path portions and/or trajectories corresponding to vectors that substantially differ from the angle of the trajectory associated with the shortest path. Such a penalty can be realized in a recovery matrix, cost map, and/or matrix (e.g., matrix 800), such as through a cost value, multiplier and/or additive. In some cases, the comparison can be computed by examining the dot product between the vector of the shortest path and the vector of the vector of a path portion and/or trajectory calculated by robot 200. In this way, when a trajectory and/or path portion has the appropriate direction that is substantially similar to the direction of the shortest path, it will be reflected in the dot product. This dot product can be a dependency of the cost function such that the value of trajectories and/or path portions that have the same initial direction as the shortest path are favored.”. The cited passage clearly teaches that the change in direction of the robot along potential path portions is taken into account in the cost function. Specifically, the cost function can have a penalty that quantifies the difference in angle between the path potions and favours those without a significant change in direction.);
and a planned path outputting interface configured to output the path based on the iteratively selected consecutive positions (Sinyavskiy: Column 11 lines 64-67, “Controller 204 can control the various operations performed by robot 200.”, Column 12 lines 13-42, “Controller 204 can be operatively and/or communicatively coupled to memory 202. … . Memory 202 can provide instructions and data to controller 204. For example, memory 202 can be a non-transitory, computer-readable storage apparatus and/or medium having a plurality of instructions stored thereon, the instructions being executable by a processing apparatus ( e.g., controller 204) to operate robot 200.”, Column 25 lines 43-55, “Block 410 can include selecting a first path portion from the plurality of path portions based at least in part on the cost of each of the path portions. For example, the dot product between the cost map and a mask can be taken in order to find the cost associated with a mask. Where higher values in the cost map are assigned to places to which it is desirable for robot 200 to travel, finding the substantial maximum and/or higher values as a result of the dot product can be indicative of an optimal path. As another example, where lower values in the cost map are assigned to places to which it is desirable that robot 200 travels, finding the substantial minimum and/or lower values as a result of the dot product can be indicative of an optimal path.”, Column 33 lines 21-29, “Returning to FIG. 4, block 412 can include determining actuator commands for the first path portions. The actuator commands can allow robot 200 to travel along the path portion, such as in accordance to one or more control characteristics.”. Form the cited passages, the processor clearly functions as the planned path outputting interface.).
Sinyavskiy does not teach wherein the iterative selection includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap,
and the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions.
Tanaka, in the same field of endeavor, teaches wherein the iterative selection includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap (Tanaka: Figure 6 and 7, Column 13 lines 38-65, “Next, the route planning unit 35 performs the shortest route search using a search algorithm such as the well-known A* algorithm (A star algorithm) or the like and decides the travel route. Specifically, the route planning unit 35 decides the travel route 350 by using, as shown in FIG. 7, the A* algorithm with the starting position 351 and the goal position 352 as the base points, and computing through which node 342 and which link 343 on the integrated map need to be travelled in order to achieve the minimum cost (shortest route).”. As can be seen from the cited passages and figures, the nodes are iteratively selected such that they minimize a cost. Furthermore, one of ordinary skill in the would see that this cost is a cumulative cost because it calculates the cost of each node travelled to between the start and end nodes.).
Sinyavskiy teaches a computing device for path planning for a mobile non-circular robot in an environment including obstacles, the computing device comprising: a 3D costmap receiving interface configured to receive a three-dimensional (3D) costmap, wherein the 3D costmap includes a two-dimensional (2D) map of a plane in which the mobile non-circular robot is movable and wherein the 3D costmap further includes a cost value for each position on the 2D map, the cost value indicative of a cost of at least one of a positioning or a movement of the mobile non-circular robot in a presence of one or more obstacles in an environment of the position, wherein the at least one of the positioning or the movement includes an orientation of the mobile non-circular robot; a start and end positions receiving interface configured to receive a start position and an end position of the mobile non-circular robot on the 3D costmap, wherein the start position includes a start orientation of the mobile non-circular robot, and wherein the end position includes an end orientation of the mobile non-circular robot; a consecutive positions selecting module configured to iteratively select consecutive positions for a path to be planned,, starting at the start position and terminating at the end position, and wherein the cumulative cost value further includes a stress value, wherein the stress value is indicative of a change in a movement direction along the path; and a planned path outputting interface configured to output the path based on the iteratively selected consecutive positions. Sinyavskiy does not teach wherein the iterative selection includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap. Tanaka teaches wherein the iterative selection includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap. A person of ordinary skill in the art would have had the technological capabilities required to have modified the computing device for path planning for a mobile non-circular robot taught in Sinyavskiy with wherein the iterative selection includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmaptaught in Tanaka. Furthermore, the method of path planning taught in Sinyavskiy teaches selecting the path potions that minimize the cost from the start point to the end point, but does not explicitly teach minimizing the cost when iteratively selecting the discretized points of the cost map. Therefore, a person of ordinary skill in the art would have been able to modify the iterative selection of points taught in Sinyavskiy with the method of minimizing the cumulative cost function during the iterative selection of points as taught in Tanaka without changing or introducing new functionality. No inventive effort would have been required. The combination would have yielded the predictable result of a computing device for path planning for a mobile non-circular robot wherein the iterative selection includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to have combine the computing device for path planning for a mobile non-circular robot taught in Sinyavskiy with wherein the iterative selection includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap taught in Tanaka with a reasonable expectation of success. One of ordinary skill in the art would have been motivated to make this modification because the combination would have yielded predictable results.
Sinyavskiy in view of Tanaka does not teach the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions.
Yabushita, in the same field of endeavor, teaches the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions (Yabushita: Column 11 lines 1-20, “Alternatively, a plurality of provisional moving paths in which the continuity of the change in the turning angle has been guaranteed are found, then a preferable provisional moving path may be selected from among them, and the selected provisional moving path may be determined to be the determined moving path. In this case, the provisional moving path in which the path cost calculated for each provisional moving path becomes minimum may be selected. Specifically, the cost for the movement between grids that are adjacent to each other on the xy plane may be determined in advance, and the provisional moving path in which the total cost accumulated up to the timing when the robot reaches the destination point becomes minimum is selected. The cost for the movement between predetermined grids is determined, for example, in proportion to the distance between these grids. As a matter of course, a further adjustment may be added. For example, a higher cost may be imposed when the grid is close to the obstacle.”, Column 11 lines 49-64, “Various methods may be employed to select the grid trajectory. In this example, by selecting the grid trajectory in which the turning angle cost added to the change in the turning angle in the path layer becomes minimum, the turning angle during the movement is determined. The turning angle cost is a predetermined cost accumulated when the robot moves between the grids adjacent to each other in the path layer, and is set in such a way that the cost is in proportion to, for example, the magnitude of the turning angle. The cost to be set may be adjusted in such a way that, for example, a large cost is added when a grid is close to the obstacle, a smaller cost is added in a case where the robot turns by a great degree by one change than the cost added in a case where the robot turns by a small degree frequently, or a large cost is added to a specific turning angle due to hardware restrictions of the moving robot 100.”, Column 13 lines 1-26, “When a plurality of provisional moving paths have been found, the process goes to Step S108, where one of the provisional moving paths is selected in accordance with a predetermined condition and the selected path is determined to be the moving path along which the moving robot 100 moves. Specifically, as described above, the provisional moving path in which the path cost calculated for each provisional moving path becomes minimum may be, for example, selected.”, Column 13 lines 35-46, “When a plurality of grid trajectories have been found, the process goes to Step S111, where one grid trajectory is selected in accordance with a predetermined condition and this grid trajectory is determined to be the turning angle during the movement. Specifically, as described above, for example, the grid trajectory in which the turning angle cost added to the change in the turning angle in the path layer becomes minimum may be selected.”. The cited passage clearly teaches that, in determining a path for the robot, the system minimizes a cumulative cost function. This cost function is based on both the cost of movement between girds on the cost map (i.e. the shortest most direct path that requires the least grids traversed would be minimum) and both the magnitude of the turning angle and the frequency of the turning angle (Column 11 lines 49-64 describes the cost function of the turning angle being larger the larger the magnitude of the turning angle and being larger if the robot makes frequent small turns.). One of ordinary skill in the art would recognize that these two aspects quantify a movement shift of the robot and because they are cumulative are based on both a current movement shift and previous movement shift.).
Sinyavskiy in view of Tanaka teaches a computing device for path planning for a mobile non-circular robot in an environment including obstacles, the computing device comprising: a 3D costmap receiving interface configured to receive a three-dimensional (3D) costmap, wherein the 3D costmap includes a two-dimensional (2D) map of a plane in which the mobile non-circular robot is movable, and wherein the 3D costmap further includes a cost value for each position on the 2D map, the cost value indicative of a cost of at least one of a positioning or a movement of the mobile non-circular robot in a presence of one or more obstacles in an environment of the position, wherein the at least one of the positioning or the movement includes an orientation of the mobile non-circular robot; a start and end positions receiving interface configured to receive a start position and an end position of the mobile non-circular robot on the 3D costmap, wherein the start position includes a start orientation of the mobile non-circular robot, and wherein the end position includes an end orientation of the mobile non-circular robot; a consecutive positions selecting module configured to iteratively select consecutive positions for a path to be planned, starting at the start position and terminating at the end position, wherein the iterative selection includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap, and wherein the cumulative cost value further includes a stress value, wherein the stress value is indicative of a change in a movement direction along the path; and a planned path outputting interface configured to output the path based on the iteratively selected consecutive positions. Sinyavskiy in view of Tanaka does not teach the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions. Yabushita teaches the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions. A person of ordinary skill in the art would have had the technological capabilities to have modified the device taught in Sinyavskiy in view of Tanaka with the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions taught in Yabushita. Furthermore, the device taught in Sinyavskiy in view of Tanaka teaches selecting the path by minimizing the movement shift between the potential route and the shortest determined route. This is accomplished by comparing the vectors at each point in the cost grid, wherein each vector includes the state of the robot (position, orientation, speed, velocity, etc.) and minimizing the difference between the vectors. Additionally, the cost function used is cumulative. As such, one of ordinary skill in the art would have been able to modify the device of Sinyavskiy in view of Tanaka with the method of determining the stress value based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions of the potential trajectory as taught in Yabushita because the device of Sinyavskiy in view of Tanaka teaches a similar process but performed between two trajectories rather than just the potential trajectory itself. Such a modification would not have changed or introduced new functionality. No inventive effort would have been required. The combination would have yielded the predictable result of a computing device for path planning for a mobile non-circular robot in an environment including the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to have combine the device taught in Sinyavskiy in view of Tanaka with the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions taught in Yabushita with a reasonable expectation of success. One of ordinary skill in the art would have been motivated to make this modification because the combination would have yielded predictable results.
Regarding claim 14, Sinyavskiy in view of Tanaka in further view of Yabushita teaches a system for path planning for a mobile non-circular robot in an environment including obstacles, the system comprising: a computing device according to claim 13; and the mobile non-circular robot (Sinyavskiy: Column 11 lines 49-63, “FIG. 2 is a functional block diagram of a robot 200 in accordance with some principles of this disclosure. As illustrated in FIG. 2, robot 200 can include controller 204, memory 202, user interface unit 218, sensors unit 212, actuators unit 220, and communications unit 222, as well as other components and subcomponents (e.g., some of which may not be illustrated).”, Column 11 lines 64-67, “Controller 204 can control the various operations performed by robot 200.”, Column 12 lines 13-42, “Controller 204 can be operatively and/or communicatively coupled to memory 202. … . Memory 202 can provide instructions and data to controller 204. For example, memory 202 can be a non-transitory, computer-readable storage apparatus and/or medium having a plurality of instructions stored thereon, the instructions being executable by a processing apparatus ( e.g., controller 204) to operate robot 200.”, Column 21 lines 12-35, “The actual body shape of robot 200 is illustrated; however, footprint 702 can be the size of robot 200 configured in the software and/or hardware of robot 200 for determining how robot 200 can navigate and/or perform tasks. By way of illustration, footprint 702 can extend (as illustrated) beyond front side 704A, right side 704C, left side 704D, and/or back side 704B, creating a difference between what robot 200 perceives is the size of robot 200 in software and/or hardware (e.g., footprint 702) and what the actual size/shape of robot 200 is in reality.”, Column lines, “By way of illustration, FIG. 7B illustrates an elevated left side view of robot 200 with three wheels in accordance to some implementations of the present disclosure. Similarly, FIG. 7C illustrates an elevated right side view of robot 200 with three wheels in accordance to some implementations of the present disclosure. As illustrated, in some implementations, robot 200 can have three wheels, where two wheels (e.g., wheels 710Aand 710C) can be positioned proximal to back side 704B and one wheel (e.g., wheel 710B) can be positioned proximal to front side 704A.”. From the cited figures and passages, on of ordinary skill in the art would clearly see that the robot the path planning method is implemented on is non-circular.).
Regarding claim 16, Sinyavskiy in view of Tanaka in further view of Yabushita teaches wherein the mobile non-circular robot comprises at least one sensor configured for collision avoidance (Sinyavskiy: Column 12 lines 44-67, “In some implementations, sensors unit 212 can comprise systems and/or methods that can detect characteristics within and/or around robot 200. Sensors unit 212 can comprise a plurality and/or a combination of sensors. Sensors unit 212 can include sensors that are internal to robot 200 or external, and/or have components that are partially internal and/or partially external. In some cases, sensors unit 212 can include one or more exteroceptive sensors, such as sonars, light detection and ranging ("LIDAR") sensors, radars, lasers, cameras (including video cameras (e.g., red blue green ("RBG") cameras, infrared cameras, three-dimensional ("3D") cameras, thermal cameras, etc.), time of flight ("TOF") cameras, structured light cameras, antennas, motion detectors, microphones, and/or any other sensor known in the art.”, Column 13 lines 32-49, “In some implementations, robot 200 can map and learn routes through a learning process. For example, an operator can teach robot 200 where to travel in an environment by driving robot 200 along a route in an environment. Through a combination of sensor data from sensor units 212, robot 200 can determine the relative poses of robot 200 and the poses of items in the environment. In this way, robot 200 can determine where it is in an environment and where it has travelled. Robot 200 can later recall where it travelled and travel in a substantially similar way (though it may avoid certain obstacles in subsequent travels).”. As can be seen from the cited passages, the robot is configured with sensors to aid in collision avoidance.).
Regarding claim 17, Sinyavskiy in view of Tanaka in further view of Yabushita teaches a non-transitory computer-readable storage medium storing computer-executable instructions that, when executed at a computing device, cause the computing device to perform a computer-implemented method according to claim 1 (Sinyavskiy: Column 11 lines 64-67, “Controller 204 can control the various operations performed by robot 200.”, Column 12 lines 13-42, “Controller 204 can be operatively and/or communicatively coupled to memory 202. … . Memory 202 can provide instructions and data to controller 204. For example, memory 202 can be a non-transitory, computer-readable storage apparatus and/or medium having a plurality of instructions stored thereon, the instructions being executable by a processing apparatus ( e.g., controller 204) to operate robot 200.”).
Regarding claim 18, Sinyavskiy in view of Tanaka in further view of Yabushita teaches wherein the 3D costmap includes a number of copies per node of the grid wherein each copy includes a differently rotated orientation of the mobile non-circular robot (Yabushita: Figures 7 and 9, Column 7 lines 58-67, “When the spatial layer AL is created for each turning angle, the spatial layers AL are layered on one another in the order of the turning angle to complete the environmental map. FIG. 7 is a diagram for describing the three-dimensional structure of the environmental map. While "1" or "0" is associated with each grid GD in the spatial layer AL as shown in FIG. 6B, FIG. 7 shows a diagram in which the no-entry area NA overlaps the grid GD, as shown in FIG. 6A, for conceptual understanding. In the following several drawings, the spatial layer AL is expressed in this way.”, Column 8 lines 1-10, “The step angle of the turning angle 8 is determined while the amount of calculation that can be allowed or the like is being taken into consideration. In this example, the step angle is set to 5°. That is, 72 spatial layers AL whose turning angle 8 is from 0° to 355° are created and are layered on one another. Since the turning angle 8 is 360°, which is equal to 0°, it can be considered that the spatial layer AL with the turning angle 8 of 0° and the spatial layer AL with the turning angle 8 of 355° are layered on one another in such a way that they are adjacent to each other.”, Column 9 lines 5-14, “FIG. 9 is a diagram showing a relation between the provisional moving path and the spatial layer AL for each turning angle. In FIG. 9, the trajectory shown by the grid GD surrounded by the thick frame indicates the provisional moving path set for the m (m is an integer equal to or larger than two)-th time. That is, it means that the robot could not reach from the departure point grid GDs to the destination point grid GDg in the provisional moving paths set from the first time to the (m-1)-th time no matter which angle the robot has.”. The cited passages clearly teach generating a number of copies of the grid for each angle of rotation from 0 to 355. In each copy, each grid will have the same rotation value.).
Regarding claim 19, Sinyavskiy in view of Tanaka in further view of Yabushita teaches wherein the 3D costmap is based on a convex hull of a footprint of the mobile non-circular robot onto the 2D map of the plane (Sinyavskiy: Figure 7A, Column 20 lines 48-67, “Block 406 then includes projecting a plurality of path portions relative to robot 200. These trajectories can comprise possible trajectories of robot 200 in a space. In some implementations, these trajectories can take into account the shape of robot 200. For example, robot 200 can have a size and shape as determined by the chassis and/or external elements of robot 200. Moreover, robot 200 can have a predetermined footprint, which can include the size and shape in which robot 200 perceives itself. In order to illustrate a robot's predefined footprint of itself, FIG. 7A is a top view diagram illustrating robot footprint 702 of robot 200 in accordance with some implementations of this disclosure.”. One of ordinary skill in the art would see that the footprint of the robot is clearly convex.).
Regarding claim 21, Sinyavskiy in view of Tanaka in further view of Yabushita teaches further comprising at least one of: generating the 3D costmap; or updating the 3D costmap in response to a change in positions of the one or more obstacles (Sinyavskiy: Column 1 lines 59-67, “In one exemplary implementation, the method includes: generating a cost map associated with an environment of the robot, the cost map comprising a plurality of cost map pixels, each cost map pixel of the plurality corresponding to a respective location in the environment and each cost map pixel of the plurality having an associated cost;”, Column 16 lines 54-67, “Block 404 includes generating a cost map associated with an environment of a robot.”, Column 17 lines 35-56, “By way of illustration, the cost map can be a two-, three-, four- or more dimensional data structure wherein portions of the cost map correlate to locations (e.g., relative and/or absolute) in an environment. In some cases, those locations can be correlated to time, where the characteristics of the locations can change over time. For example, in a two-dimensional ("2D") map, each pixel can correlate at least in part to a physical location in the environment in which robot 200 navigates. Similarly, in a three-dimensional ("3D") map, each voxel can correlate at least in part to a physical location in the environment in which robot 200 navigates. In some implementations, a 2D map can be used where robot 200 operates in substantially planar operations (e.g., where the movements of robot 200, whether on a level surface or otherwise, operate within a plane, such as left, right, forward, back, and/or combinations thereof). In some implementations, a 3D map can be used where robot 200 operates in more than planar operations, such as up, down, row, pitch, and/or yaw in addition to left, right, forward, and back). Where a space has more characteristics associated with locations (e.g., temperature, time, complexity, etc.), there can be more dimensions to the map.”, Column 18 lines 57-67, “In some implementations, the cost map can be dynamic, changing over time and as robot 200 moves. For example, objects in the environment (e.g., as indicated by indicators 506A-506C) can move over time. Moreover, values of pixels in indicator 504 can also change over time. For example, after robot 200 travels across a pixel, it may become less preferable, or not preferable at all, for robot 200 to travel to the location associated with the pixel again.”. The cited passage clearly teaches that the cost map is dynamic and changes in response to the movement of obstacles.).
Regarding claim 22, Sinyavskiy in view of Tanaka in further view of Yabushita teaches wherein the cumulative cost value further increases with at least one of: a change of orientation of the mobile non-circular robot; a veering away from at least one of the end position or the start position; and a repeated traversal of a position along the path (Sinyavskiy: Column 27 lines 22-61, “In other cases, a penalty can be assigned to path portions and/or trajectories corresponding to vectors that substantially differ from the angle of the trajectory associated with the shortest path. Such a penalty can be realized in a recovery matrix, cost map, and/or matrix (e.g., matrix 800), such as through a cost value, multiplier and/or additive. In some cases, the comparison can be computed by examining the dot product between the vector of the shortest path and the vector of the vector of a path portion and/or trajectory calculated by robot 200. In this way, when a trajectory and/or path portion has the appropriate direction that is substantially similar to the direction of the shortest path, it will be reflected in the dot product. This dot product can be a dependency of the cost function such that the value of trajectories and/or path portions that have the same initial direction as the shortest path are favored.”. The cited passage clearly teaches that the change in direction of the robot along potential path portions is taken into account in the cost function. Specifically, the cost function can have a penalty that quantifies the difference in angle between the path potions and favours those without a significant change in direction.).
Regarding claim 23, Sinyavskiy in view of Tanaka in further view of Yabushita teaches wherein the 3D costmap is based on a convex hull of a footprint of the mobile non-circular robot onto the 2D map of the plane (Sinyavskiy: Figure 7A, Column 20 lines 48-67, “Block 406 then includes projecting a plurality of path portions relative to robot 200. These trajectories can comprise possible trajectories of robot 200 in a space. In some implementations, these trajectories can take into account the shape of robot 200. For example, robot 200 can have a size and shape as determined by the chassis and/or external elements of robot 200. Moreover, robot 200 can have a predetermined footprint, which can include the size and shape in which robot 200 perceives itself. In order to illustrate a robot's predefined footprint of itself, FIG. 7A is a top view diagram illustrating robot footprint 702 of robot 200 in accordance with some implementations of this disclosure.”. One of ordinary skill in the art would see that the footprint of the robot is clearly convex.).
Regarding claim 25, Sinyavskiy teaches a computing device for path planning for a mobile non-circular robot in an environment including obstacles, the computing device comprising (Sinyavskiy: Figures 1B-C and 7A-C robot 200, Abstract, “Systems and methods for robotic path planning are disclosed. In some implementations of the present disclosure, a robot can generate a cost map associated with an environment of the robot. The cost map can comprise a plurality of pixels each corresponding to a location in the environment, where each pixel can have an associated cost. The robot can further generate a plurality of masks having projected path portions for the travel of the robot within the environment, where each mask comprises a plurality of mask pixels that correspond to locations in the environment. The robot can then determine a mask cost associated with each mask based at least in part on the cost map and select a mask based at least in part on the mask cost. Based on the projected path portions within the selected mask, the robot can navigate a space.”, Column 21 lines 12-35, “The actual body shape of robot 200 is illustrated; however, footprint 702 can be the size of robot 200 configured in the software and/or hardware of robot 200 for determining how robot 200 can navigate and/or perform tasks. By way of illustration, footprint 702 can extend (as illustrated) beyond front side 704A, right side 704C, left side 704D, and/or back side 704B, creating a difference between what robot 200 perceives is the size of robot 200 in software and/or hardware (e.g., footprint 702) and what the actual size/shape of robot 200 is in reality.”, Column lines, “By way of illustration, FIG. 7B illustrates an elevated left side view of robot 200 with three wheels in accordance to some implementations of the present disclosure. Similarly, FIG. 7C illustrates an elevated right side view of robot 200 with three wheels in accordance to some implementations of the present disclosure. As illustrated, in some implementations, robot 200 can have three wheels, where two wheels (e.g., wheels 710Aand 710C) can be positioned proximal to back side 704B and one wheel (e.g., wheel 710B) can be positioned proximal to front side 704A.”. From the cited figures and passages, on of ordinary skill in the art would clearly see that the robot the path planning method is implemented on is non-circular.):
a memory (Sinyavskiy: Column 12 lines 13-42, “Controller 204 can be operatively and/or communicatively coupled to memory 202. … . Memory 202 can provide instructions and data to controller 204. For example, memory 202 can be a non-transitory, computer-readable storage apparatus and/or medium having a plurality of instructions stored thereon, the instructions being executable by a processing apparatus ( e.g., controller 204) to operate robot 200.”);
and at least one processor configured to execute computer-readable instructions to cause the computing device to (Sinyavskiy: Column 11 lines 64-67, “Controller 204 can control the various operations performed by robot 200.”, Column 12 lines 13-42.)
receive a three-dimensional (3D) costmap (Sinyavskiy: Column 17 lines 35-56, “By way of illustration, the cost map can be a two-, three-, four- or more dimensional data structure wherein portions of the cost map correlate to locations (e.g., relative and/or absolute) in an environment. In some cases, those locations can be correlated to time, where the characteristics of the locations can change over time. For example, in a two-dimensional ("2D") map, each pixel can correlate at least in part to a physical location in the environment in which robot 200 navigates. Similarly, in a three-dimensional ("3D") map, each voxel can correlate at least in part to a physical location in the environment in which robot 200 navigates. In some implementations, a 2D map can be used where robot 200 operates in substantially planar operations (e.g., where the movements of robot 200, whether on a level surface or otherwise, operate within a plane, such as left, right, forward, back, and/or combinations thereof). In some implementations, a 3D map can be used where robot 200 operates in more than planar operations, such as up, down, row, pitch, and/or yaw in addition to left, right, forward, and back). Where a space has more characteristics associated with locations (e.g., temperature, time, complexity, etc.), there can be more dimensions to the map.”),
wherein the 3D costmap includes a two-dimensional (2D) map of a plane in which the mobile non-circular robot is movable (Sinyavskiy: Figure 5A, Column 18 lines 4-18, “FIG. 5A is an overhead view graphical representation of a cost map in accordance to some implementations of this disclosure. Cost map 502 includes a map that correlates with an environment of robot 200. For example, robot indicator 500 indicates the position of robot 200. In some cases, robot indicator 500 may not be actually present on cost map 502. Indicators 506A-506C can indicate at least in part the position of obstacles, such as walls. Indicator 504 can be indicative at least in part of a desirable travel path portion, wherein it is desirable for robot 200 to travel within indicator 504.”. One of ordinary skill in the art would see from the cited passage that, if the cost map is 3D, then the overhead view would be a 2D plane representing the environment in which the robot operates.)
and wherein the 3D costmap further includes a cost value for each position on the 2D map, the cost value indicative of a cost of at least one of a positioning or a movement of the mobile non-circular robot in the presence of one or more obstacles in an environment of the position (Sinyavskiy: Abstract, “Systems and methods for robotic path planning are disclosed. In some implementations of the present disclosure, a robot can generate a cost map associated with an environment of the robot. The cost map can comprise a plurality of pixels each corresponding to a location in the environment, where each pixel can have an associated cost. The robot can further generate a plurality of masks having projected path portions for the travel of the robot within the environment, where each mask comprises a plurality of mask pixels that correspond to locations in the environment. The robot can then determine a mask cost associated with each mask based at least in part on the cost map and select a mask based at least in part on the mask cost. Based on the projected path portions within the selected mask, the robot can navigate a space.”, Column 1 lines 61-67, “In one exemplary implementation, the method includes: generating a cost map associated with an environment of the robot, the cost map comprising a plurality of cost map pixels, each cost map pixel of the plurality corresponding to a respective location in the environment and each cost map pixel of the plurality having an associated cost;”, Column 17 line 57 – Column 18 line 3, Column 18 lines 4-18, Column 18 lines 19-25, “Indicators 506A-506C can have values associated with the pixels contained therein. These values can be indicative at least in part of a preference for robot 200 not to go to those locations (e.g., crash into the obstacles). Similarly, values can be associated with the pixels contained in indicator 504, indicating a preference for robot 200 to travel to those locations.”, “In some implementations, a value can be associated with one or more pixels (while pixel is used here, the principles are readily applicable to voxels and/or any other analog in different dimensions) of the cost map, indicative at least in part of the relative value associated with the pixel. For example, the cost map can comprise binary values, where one value can be indicative at least in part of areas to which it is desirable for a robot 200 to travel, and another indicative at least in part of places where it is not desirable for robot 200 to travel. As another example, the cost map may have different values associated with a pixel, wherein the magnitude of the value can be indicative at least in part of how desirable and/or undesirable it is for robot 200 to travel to the pixel.”, Column 34 lines 29-52, “FIG. 10 is a process flow diagram of an exemplary method 1000 for path planning in accordance with some implementations of this disclosure. Block 1002 includes Generating a cost map associated with an environment of the robot, the cost map comprising a plurality of cost map pixels each corresponding to a location in the environment and each cost map pixel having an associated cost.” Column 34 lines 53-67, “FIG. 11 is a process flow diagram of an exemplary method 1100 for path planning in accordance with some implementations of this disclosure. Block 1102 includes generating a cost map associated with at least a portion of the generated map of the environment, the cost map comprising a plurality of cost map pixels wherein each cost map pixel corresponds to a location in the environment and each cost map pixel has an associated cost.”, Column 35 lines 8-24, “FIG. 12 is a process flow diagram of an exemplary method 1200 for path planning in accordance with some implementations of this disclosure. Block 1202 includes generating a cost map associated with an environment of the robot, the cost map comprising a plurality of cost map pixels each corresponding to a location in the environment and each cost map pixel having an associated cost based at least in part on a desire to clean the location.”. The cited passages clearly teach that the cost map has a cost associated with each pixel of the cost map.),
wherein the at least one of the positioning or the movement includes an orientation of the mobile non-circular robot (Sinyavskiy: Column 10 lines 22-41, “In some cases, the path can include a route for travelling. For example, the route can include translation of a robot from a first location to a second location. The route can include a plurality of positions, orientations, and/or poses of a robot, such as a plurality of positions, orientations, and/or poses associated with locations in an environment.”, Column 25 lines 4-26, “For example, a plurality of path portions can be determined. FIG. 8B is a graphical representation of a three dimensional matrix 800 of path portion diagrams in accordance to some implementations of the present disclosure. Matrix 800 can include N path portions, where N can correlate to the desirable number of path portions to consider. In some cases, N can correlate with the number of trajectories ( e.g., 5000 trajectories and/or any other number), control characteristics, and/or be predetermined based at least in part by memory and/or processing power, speed of processing, complexity of the environment through which robot 200 navigates, the number of possible orientations of robot 200, the DOF of robot 200, the amount of space covered in the control characteristics, the amount of time covered in the control characteristics, and/or other factors.”, Column 27 lines 9-20, “In some cases, the relevant information from the shortest path field is the vector ( e.g., direction, orientation, pose, position, speed, etc.) of robot 200 at that point in order to travel the shortest path (e.g., shortest non-colliding path) to the selected point. Accordingly, a vector field can be generated showing the vector at each discretized point. FIG. 8F is an overhead diagram showing vectors for shortest paths associated with discretized points illustrated in FIG. 8D in accordance to some implementations of this disclosure. For example, point 830B corresponds to vector 838B, which gives the vector of robot 200 to travel the shortest path to point 830A.”. The cited passages clearly show that the orientation is included in the positioning and movement of the robot.);
receive a start position and an end position of the mobile non-circular robot on the 3D costmap (Sinyavskiy: Column 26 lines 1-12, “As another example, the shortest path field can be computed. For example, an end point can be determined for robot 200. For every path, the shortest path to the end point can be determined given the present orientation of the robot. In this way, the shortest path can be determined for every point in a map. Such shortest path to the end point can be used to adjust values of the cost map thereby making shorter paths (and/or realistic paths) more favorable. In some cases, the map comprising shortest paths can be an additional map, essentially forming a cost map. In some implementations, the shortest paths can further take into account obstacles, such as by using known algorithms in the art.”, Column 32 lines 20-55, “For example, the interface can allow a user to edit a map, adjust a path, move a starting position (e.g., home marker), delete path/path segment, add operations (e.g., cleaning, manipulating, actuating, etc.), and/or any other manipulation a user could desire. For example, option 934A can allow a user to delete a path segment. For example, after selecting option 934A, a user can then select a portion of a path displayed in map 932 and/or path portions 940. Robot 200 can then delete such selected path portion. As another example, option 934B can allow a user to adjust a path. For example, a user can select a path portion included in map 932 and/or path portions 940 and move/manipulate that path portion. As another example, option 934C can allow a user to move a home marker (e.g., a starting position). For example, the starting position can be where robot 200 begins and/or ends a robotic operation.”. The cited passages clearly teach receiving a starting and ending point of the robot.),
wherein the start position includes a start orientation of the mobile non-circular robot, and wherein the end position includes an end orientation of the mobile non-circular robot (Sinyavskiy: Column lines, Column 10 lines 22-41, “In some cases, the path can include a route for travelling. For example, the route can include translation of a robot from a first location to a second location. The route can include a plurality of positions, orientations, and/or poses of a robot, such as a plurality of positions, orientations, and/or poses associated with locations in an environment.”, Column 27 lines 21-61, “The vector can reflect the orientation, speed, position, pose, etc. of robot 200 as it begins the planned path portion and or trajectory. In some implementations, this vector can be of unit length in order to ease computation.”. One of ordinary skill in the art would see from the cited passages that the start and end positions include an orientation of the robot.);
iteratively select consecutive positions for a path to be planned, starting at the start position and terminating at the end position (Sinyavskiy: Column 26 lines 38-48, “In order to determine the shortest path, map portion 818 can be discretized, such as by looking at a plurality of points. FIG. 8D is an overhead diagram illustrating a discretized version of map portion 818, wherein each point is a discrete location in accordance with implementations of this disclosure. For example, point 830A can be a discretized point in map portion 818. In some implementations, non-navigable points can be included in the discretization, such as point 834, which can be within obstacle 822. In some implementations, non-navigable points may not be included. In some cases, each discretized point can also be called a cell.”, Column 26 lines 49-58, “In order to determine the shortest path (e.g., in a shortest path field), a point can be selected. Any point can be used, however, in some implementations, the point is a point along the horizon of robot 200, such as the substantially furthest point robot 200 can seeing going forward along the path (e.g., furthest in distance and/or time). Advantageously, this can allow robot 200 to plan the path going forward for when it travels. Robot 200 can then find the shortest non-colliding point from each discretized point (such as the discretized points illustrated in FIG. SD) to that selected point.”. The cited passages clearly teach iteratively selecting consecutive points for a path from a start point to an end point.),
and wherein the cumulative cost value further includes a stress value, wherein the stress value is indicative of a change in a movement direction along the path (Sinyavskiy: Column 27 lines 22-61, “In other cases, a penalty can be assigned to path portions and/or trajectories corresponding to vectors that substantially differ from the angle of the trajectory associated with the shortest path. Such a penalty can be realized in a recovery matrix, cost map, and/or matrix (e.g., matrix 800), such as through a cost value, multiplier and/or additive. In some cases, the comparison can be computed by examining the dot product between the vector of the shortest path and the vector of the vector of a path portion and/or trajectory calculated by robot 200. In this way, when a trajectory and/or path portion has the appropriate direction that is substantially similar to the direction of the shortest path, it will be reflected in the dot product. This dot product can be a dependency of the cost function such that the value of trajectories and/or path portions that have the same initial direction as the shortest path are favored.”. The cited passage clearly teaches that the change in direction of the robot along potential path portions is taken into account in the cost function. Specifically, the cost function can have a penalty that quantifies the difference in angle between the path potions and favours those without a significant change in direction.);
and output the path based on the iteratively selected consecutive positions (Sinyavskiy: Column 25 lines 43-55, “Block 410 can include selecting a first path portion from the plurality of path portions based at least in part on the cost of each of the path portions. For example, the dot product between the cost map and a mask can be taken in order to find the cost associated with a mask. Where higher values in the cost map are assigned to places to which it is desirable for robot 200 to travel, finding the substantial maximum and/or higher values as a result of the dot product can be indicative of an optimal path. As another example, where lower values in the cost map are assigned to places to which it is desirable that robot 200 travels, finding the substantial minimum and/or lower values as a result of the dot product can be indicative of an optimal path.”, Column 33 lines 21-29, “Returning to FIG. 4, block 412 can include determining actuator commands for the first path portions. The actuator commands can allow robot 200 to travel along the path portion, such as in accordance to one or more control characteristics.”).
Sinyavskiy does not teach wherein the iterative selection includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap;
and the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions.
Tanaka, in the same field of endeavor, teaches wherein the iterative selection includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap (Tanaka: Figure 6 and 7, Column 13 lines 38-65, “Next, the route planning unit 35 performs the shortest route search using a search algorithm such as the well-known A* algorithm (A star algorithm) or the like and decides the travel route. Specifically, the route planning unit 35 decides the travel route 350 by using, as shown in FIG. 7, the A* algorithm with the starting position 351 and the goal position 352 as the base points, and computing through which node 342 and which link 343 on the integrated map need to be travelled in order to achieve the minimum cost (shortest route).”. As can be seen from the cited passages and figures, the nodes are iteratively selected such that they minimize a cost. Furthermore, one of ordinary skill in the would see that this cost is a cumulative cost because it calculates the cost of each node travelled to between the start and end nodes.).
Sinyavskiy teaches a computing device for path planning for a mobile non-circular robot in an environment including obstacles, the computing device comprising: a memory; and at least one processor configured to execute computer-readable instructions to cause the computing device to receive a three-dimensional (3D) costmap wherein the 3D costmap includes a two-dimensional (2D) map of a plane in which the mobile non-circular robot is movable and wherein the 3D costmap further includes a cost value for each position on the 2D map, the cost value indicative of a cost of at least one of a positioning or a movement of the mobile non-circular robot in the presence of one or more obstacles in an environment of the position, wherein the at least one of the positioning or the movement includes an orientation of the mobile non-circular robot; receive a start position and an end position of the mobile non-circular robot on the 3D costmap, wherein the start position includes a start orientation of the mobile non-circular robot, and wherein the end position includes an end orientation of the mobile non-circular robot; iteratively select consecutive positions for a path to be planned, starting at the start position and terminating at the end position, and wherein the cumulative cost value further includes a stress value, wherein the stress value is indicative of a change in a movement direction along the path; and output the path based on the iteratively selected consecutive positions. Sinyavskiy does not teach wherein the iterative selection includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap. Tanaka teaches wherein the iterative selection includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap. A person of ordinary skill in the art would have had the technological capabilities required to have modified the computing device for path planning for a mobile non-circular robot taught in Sinyavskiy with wherein the iterative selection includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap taught in Tanaka. Furthermore, the method of path planning taught in Sinyavskiy teaches selecting the path potions that minimize the cost from the start point to the end point, but does not explicitly teach minimizing the cost when iteratively selecting the discretized points of the cost map. Therefore, a person of ordinary skill in the art would have been able to modify the iterative selection of points taught in Sinyavskiy with the method of minimizing the cumulative cost function during the iterative selection of points as taught in Tanaka without changing or introducing new functionality. No inventive effort would have been required. The combination would have yielded the predictable result of a computing device for path planning for a mobile non-circular robot wherein the iterative selection includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to have combine the computing device for path planning for a mobile non-circular robot taught in Sinyavskiy with wherein the iterative selection includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap taught in Tanaka with a reasonable expectation of success. One of ordinary skill in the art would have been motivated to make this modification because the combination would have yielded predictable results.
Yabushita, in the same field of endeavor, teaches the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions (Yabushita: Column 11 lines 1-20, “Alternatively, a plurality of provisional moving paths in which the continuity of the change in the turning angle has been guaranteed are found, then a preferable provisional moving path may be selected from among them, and the selected provisional moving path may be determined to be the determined moving path. In this case, the provisional moving path in which the path cost calculated for each provisional moving path becomes minimum may be selected. Specifically, the cost for the movement between grids that are adjacent to each other on the xy plane may be determined in advance, and the provisional moving path in which the total cost accumulated up to the timing when the robot reaches the destination point becomes minimum is selected. The cost for the movement between predetermined grids is determined, for example, in proportion to the distance between these grids. As a matter of course, a further adjustment may be added. For example, a higher cost may be imposed when the grid is close to the obstacle.”, Column 11 lines 49-64, “Various methods may be employed to select the grid trajectory. In this example, by selecting the grid trajectory in which the turning angle cost added to the change in the turning angle in the path layer becomes minimum, the turning angle during the movement is determined. The turning angle cost is a predetermined cost accumulated when the robot moves between the grids adjacent to each other in the path layer, and is set in such a way that the cost is in proportion to, for example, the magnitude of the turning angle. The cost to be set may be adjusted in such a way that, for example, a large cost is added when a grid is close to the obstacle, a smaller cost is added in a case where the robot turns by a great degree by one change than the cost added in a case where the robot turns by a small degree frequently, or a large cost is added to a specific turning angle due to hardware restrictions of the moving robot 100.”, Column 13 lines 1-26, “When a plurality of provisional moving paths have been found, the process goes to Step S108, where one of the provisional moving paths is selected in accordance with a predetermined condition and the selected path is determined to be the moving path along which the moving robot 100 moves. Specifically, as described above, the provisional moving path in which the path cost calculated for each provisional moving path becomes minimum may be, for example, selected.”, Column 13 lines 35-46, “When a plurality of grid trajectories have been found, the process goes to Step S111, where one grid trajectory is selected in accordance with a predetermined condition and this grid trajectory is determined to be the turning angle during the movement. Specifically, as described above, for example, the grid trajectory in which the turning angle cost added to the change in the turning angle in the path layer becomes minimum may be selected.”. The cited passage clearly teaches that, in determining a path for the robot, the system minimizes a cumulative cost function. This cost function is based on both the cost of movement between girds on the cost map (i.e. the shortest most direct path that requires the least grids traversed would be minimum) and both the magnitude of the turning angle and the frequency of the turning angle (Column 11 lines 49-64 describes the cost function of the turning angle being larger the larger the magnitude of the turning angle and being larger if the robot makes frequent small turns.). One of ordinary skill in the art would recognize that these two aspects quantify a movement shift of the robot and because they are cumulative are based on both a current movement shift and previous movement shift.).
Sinyavskiy in view of Tanaka teaches a computing device for path planning for a mobile non-circular robot in an environment including obstacles, the computing device comprising: a memory; and at least one processor configured to execute computer-readable instructions to cause the computing device to receive a three-dimensional (3D) costmap, wherein the 3D costmap includes a two-dimensional (2D) map of a plane in which the mobile non- circular robot is movable, and wherein the 3D costmap further includes a cost value for each position on the 2D map, the cost value indicative of a cost of at least one of a positioning or a movement of the mobile non-circular robot in a presence of one or more obstacles in an environment of the position, wherein the at least one of the positioning or the movement includes an orientation of the mobile non-circular robot, receive a start position and an end position of the mobile non-circular robot on the 3D costmap, wherein the start position includes a start orientation of the mobile non-circular robot, and wherein the end position includes an end orientation of the mobile non-circular robot, iteratively select consecutive positions for a path to be planned, starting at the start position and terminating at the end position, wherein the iterative selection includes minimizing a cumulative cost value of the consecutive positions, wherein the cumulative cost value includes a sum of cost values of the consecutive positions according to the 3D costmap, and wherein the cumulative cost value further includes a stress value, wherein the stress value is indicative of a change in a movement direction along the path; and output the path based on the iteratively selected consecutive positions. Sinyavskiy in view of Tanaka does not teach the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions. Yabushita teaches the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions. A person of ordinary skill in the art would have had the technological capabilities to have modified the device taught in Sinyavskiy in view of Tanaka with the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions taught in Yabushita. Furthermore, the device taught in Sinyavskiy in view of Tanaka teaches selecting the path by minimizing the movement shift between the potential route and the shortest determined route. This is accomplished by comparing the vectors at each point in the cost grid, wherein each vector includes the state of the robot (position, orientation, speed, velocity, etc.) and minimizing the difference between the vectors. Additionally, the cost function used is cumulative. As such, one of ordinary skill in the art would have been able to modify the device of Sinyavskiy in view of Tanaka with the method of determining the stress value based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions of the potential trajectory as taught in Yabushita because the device of Sinyavskiy in view of Tanaka teaches a similar process but performed between two trajectories rather than just the potential trajectory itself. Such a modification would not have changed or introduced new functionality. No inventive effort would have been required. The combination would have yielded the predictable result of a computing device for path planning for a mobile non-circular robot in an environment including the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to have combine the device taught in Sinyavskiy in view of Tanaka with the stress value is and the stress value is determined based on a movement shift between consecutive positions and a previous movement shift between previous consecutive positions taught in Yabushita with a reasonable expectation of success. One of ordinary skill in the art would have been motivated to make this modification because the combination would have yielded predictable results.
Regarding claim 26, Sinyavskiy in view of Tanaka in further view of Yabushita teaches further comprising: updating the 3D costmap in response to a change in positions of the one or more obstacles (Sinyavskiy: Column 18 lines 57-67, “In some implementations, the cost map can be dynamic, changing over time and as robot 200 moves. For example, objects in the environment (e.g., as indicated by indicators 506A-506C) can move over time. Moreover, values of pixels in indicator 504 can also change over time. For example, after robot 200 travels across a pixel, it may become less preferable, or not preferable at all, for robot 200 to travel to the location associated with the pixel again.”. The cited passage clearly teaches that the cost map is dynamic and changes in response to the movement of obstacles.).
Claim(s) 11 is/are rejected under 35 U.S.C. 103 as being unpatentable over US 10899008 B2 ("Sinyavskiy") in view of US 8515612 B2 ("Tanaka") in further view of US 10946521 B2 ("Yabushita") in further view of US 10899006 B2 ("Holson").
Regarding claim 11, Sinyavskiy in view of Tanaka in further view of Yabushita does not teach wherein the 3D costmap further comprises a height constraint in relation to a height of the mobile non-circular robot.
Holson, in the same field of endeavor, teaches wherein the 3D costmap further comprises a height constraint in relation to a height of the mobile non-circular robot (Holson: Column 8 line 54 – Column 9 line 16, “The planning module 140 also accesses robot data 136. The robot data 136 includes information describing the physical shape and size of the robot 110. For example, the robot data 136 may include one or more 2D profiles of the robot 110. The 2D profiles can be, for example, the outer dimensions of the robot 110 in one or more horizontal planes that are parallel to the floor ( e.g., horizontal cross-sections of the robot 110). In some examples the robot data 136 include a maximum 2D profile and a minimum 2D profile. The maximum 2D profile can represent a maximum dimension, circumference, or span of the robot 110 that must be accommodated for the robot 110 to maneuver through a particular space. For example, the maximum profile may be a projection of the outer dimensions of the robot 110 onto a plane parallel to the floor that indicates the largest footprint of the robot 110, e.g., reflecting the maximum dimensions of the robot 110 in any horizontal plane along the height of the robot 110. In the example of FIG. 1, the maximum profile corresponds to a cross-section of the robot 110 across its base 111. The maximum profile may represent a maximum dimension across all potential poses or configurations of the robot 110, for example, showing the width of the arms when the arms are at their maximum outward extension. Alternatively, the maximum profile may represent the maximum dimensions for the current pose or configuration of the robot, e.g., based on the actual current position of the arms. If the robot 110 is carrying an object that extends away from the robot 110, the extent of the object can also be included in the current maximum profile of the robot 110 to avoid collision with the carried object.”, Column 11 lines 1-9, “The 3D planner 144 performs a more fine-grained analysis using 3D techniques to identify a collision-free route for the robot 110 that is generally along the global path 126. The 3D techniques implemented by the 3D planner 144 account for the 3D shape of the robot 110 (e.g., accounting for the differing dimensions of the robot 110 along its height), as well as the 3D shapes of the obstacles detected in the robot's local environment to more accurately evaluate the potential for collision along a candidate path segment.”. The cited passages clearly show that the method takes into account the 3D shape of the robot when planning its path, which includes its height.).
Sinyavskiy in view of Tanaka in further view of Yabushita teaches a computer-implemented method of path planning for a mobile non-circular robot. Sinyavskiy in view of Tanaka in further view of Yabushita does not teach wherein the 3D costmap further comprises a height constraint in relation to a height of the mobile non-circular robot. Holson teaches wherein the 3D costmap further comprises a height constraint in relation to a height of the mobile non-circular robot. A person of ordinary skill in the art would have had the technological capabilities required to have combine the computer-implemented method of path planning for a mobile non-circular robot taught in Sinyavskiy in view of Tanaka in further view of Yabushita with wherein the 3D costmap further comprises a height constraint in relation to the height of the mobile non-circular robot taught in Holson. Furthermore, the method taught in Sinyavskiy in view of Tanaka in further view of Yabushita is already configured to taken into account the dimensions of the robot (Sinyavskiy: Column 23 lines 38-67, “As another example, in some implementations, the control characteristics can recognize the footprint of robot 200 and only include maneuvers that give robot 200 sufficient clearance and/or are physically realistic given the size and shape of robot 200.”), but does not explicitly teach using a height of the robot as well. Therefore, a person of ordinary skill in the art could have easily modified the method taught in Sinyavskiy in view of Tanaka in further view of Yabushita with the method of considering the height of the robot taught in Holson without changing or introducing new functionality. No inventive effort would have been required. The combination would have yielded the predictable result of a computer-implemented method of path planning for a mobile non-circular robot wherein the 3D costmap further comprises a height constraint in relation to the height of the mobile non-circular robot.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to have combine the computer-implemented method of path planning for a mobile non-circular robot taught in Sinyavskiy in view of Tanaka in further view of Yabushita with wherein the 3D costmap further comprises a height constraint in relation to a height of the mobile non-circular robot taught in Holson with a reasonable expectation of success. One of ordinary skill in the art would have been motivated to make this modification because the combination would have yielded predictable results.
Claim(s) 12 and 24 is/are rejected under 35 U.S.C. 103 as being unpatentable over US 10899008 B2 ("Sinyavskiy") in view of US 8515612 B2 ("Tanaka") in further view of US 10946521 B2 ("Yabushita") in further view of US 6259988 B1 ("Galkowski").
Regarding claim 12, Sinyavskiy in view of Tanaka in further view of Yabushita does not teach wherein determining the cumulative cost value comprises performing a weighted sum of the cost values.
Galkowski, in the same field of endeavor, teaches wherein determining the cumulative cost value comprises performing a weighted sum of the cost values (Galkowski: Equation 1, Column 7 lines 28-38, “A* is an optimal, best-first search heuristic that computes a cost function for various locations in an environment. A* explores the search space by computing a cost function for each possible next position to search, and then selects the lowest-cost position to add to the path. The addition of this new location to the search space is then used to generate more path possibilities. All paths in the search space are explicitly represented using pointers from each position back to the previous position from which that position was derived. The cost function that is minimized at each step of the A* propagation is shown below.”, Column 7 lines 40-51, “In Equation 1, g(x) can be any function which expresses the actual cost from the start position to the intermediate position x. The value h(x) similarly can be any function which expresses the estimated cost from position x to the desired goal position. The values a and b are parameters used to weight the actual and estimated costs and are usually set to 1. At each step in the A* propagation, the lowest f(x) value is selected and inserted into a sorted list of possible paths. It has been proven that if the actual cost from x to the goal is greater than or equal to the estimate, h(x), of this cost, then the solution produced by A* is guaranteed to be a minimum cost
solution.”. The cited passages clearly show modifying the cost of each node by a weight. Furthermore, the A* algorithm that is used calculates the cost as it passes through each node from the start to the goal, which is clearly a cumulative cost.).
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to have combine the computer-implemented method of path planning for a mobile non-circular robot taught in Sinyavskiy in view of Tanaka in further view of Yabushita with wherein determining the cumulative cost value comprises performing a weighted sum of the cost values taught in Galkowski with a reasonable expectation of success. One of ordinary skill in th art would have been motivated to make this modification because it would have been obvious to try. A person of ordinary skill in the art would have had the knowledge that a weighted sum is used to give priority to different components of an equation using the weights. Furthermore, a person of ordinary skill in the art would have recognized the utility of such a method in the use of a cost function where the total cost is comprised of different factors. A person of ordinary skill in the art would have had the technological capabilities required to have modified the computer-implemented method of path planning for a mobile non-circular robot taught in Sinyavskiy in view of Tanaka in further view of Yabushita with the use of a weighted sum when determining the cumulative cost as taught in Galkowski. Such a modification would not change or introduce new functionality. No inventive effort would have been required.
Regarding claim 24, Sinyavskiy in view of Tanaka in further view of Yabushita does not teach wherein determining the cumulative cost value comprises performing a weighted sum of the cost values.
Galkowski, in the same field of endeavor, teaches wherein determining the cumulative cost value comprises performing a weighted sum of the cost values (Galkowski: Equation 1, Column 7 lines 28-38, “A* is an optimal, best-first search heuristic that computes a cost function for various locations in an environment. A* explores the search space by computing a cost function for each possible next position to search, and then selects the lowest-cost position to add to the path. The addition of this new location to the search space is then used to generate more path possibilities. All paths in the search space are explicitly represented using pointers from each position back to the previous position from which that position was derived. The cost function that is minimized at each step of the A* propagation is shown below.”, Column 7 lines 40-51, “In Equation 1, g(x) can be any function which expresses the actual cost from the start position to the intermediate position x. The value h(x) similarly can be any function which expresses the estimated cost from position x to the desired goal position. The values a and b are parameters used to weight the actual and estimated costs and are usually set to 1. At each step in the A* propagation, the lowest f(x) value is selected and inserted into a sorted list of possible paths. It has been proven that if the actual cost from x to the goal is greater than or equal to the estimate, h(x), of this cost, then the solution produced by A* is guaranteed to be a minimum cost
solution.”. The cited passages clearly show modifying the cost of each node by a weight. Furthermore, the A* algorithm that is used calculates the cost as it passes through each node from the start to the goal, which is clearly a cumulative cost.).
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to have combine the computer-implemented method of path planning for a mobile non-circular robot taught in Sinyavskiy in view of Tanaka in further view of Yabushita with wherein determining the cumulative cost value comprises performing a weighted sum of the cost values taught in Galkowski with a reasonable expectation of success. One of ordinary skill in the art would have been motivated to make this modification because it would have been obvious to try. A person of ordinary skill in the art would have had the knowledge that a weighted sum is used to give priority to different components of an equation using the weights. Furthermore, a person of ordinary skill in the art would have recognized the utility of such a method in the use of a cost function where the total cost is comprised of different factors. A person of ordinary skill in the art would have had the technological capabilities required to have modified the computer-implemented method of path planning for a mobile non-circular robot taught in Sinyavskiy in view of Tanaka in further view of Yabushita with the use of a weighted sum when determining the cumulative cost as taught in Galkowski. Such a modification would not change or introduce new functionality. No inventive effort would have been required.
Claim(s) 15 and 20 is/are rejected under 35 U.S.C. 103 as being unpatentable over US 10899008 B2 ("Sinyavskiy") in view of US 8515612 B2 ("Tanaka") in further view of US 10946521 B2 ("Yabushita") in further view of US 11199853 B1 ("Afrouzi").
Regarding claim 15, Sinyavskiy in view of Tanaka in further view of Yabushita does not teach wherein the mobile non-circular robot comprises four mecanum wheels.
Afrouzi, in the same field of endeavor, teaches wherein the mobile non-circular robot comprises four mecanum wheels (Afrouzi: Figure 88B, Column 62 lines 40-60, “In some embodiments, the springs of the different suspension systems described herein may be replaced by other elastic elements such as rubber or with other mechanisms that provide similar function as the springs (e.g., magnets as described above). In some embodiments, the wheels used with the different suspension systems are mecanum wheels, allowing the VMP robot to move in any direction. For example, the VMP robot can travel diagonally by moving a front wheel and opposite rear wheel at one speed while the other wheels turn at a different speed, moving all four wheels in the same direction straight moving, running the wheels on one side in the opposite direction to those on the other side causing rotation, and running the wheels on one diagonal in the opposite direction to those on the other diagonal causes sideways movement. FIGS. 87A and 87B illustrate examples of a mecanum wheel 8700 attached to an arm 8701 of a robotic device. The arm may be coupled to a chassis of the robotic device. FIGS. 88A and 88B illustrate a front and bottom view of an example of a robotic device with mecanum wheels 8800, respectively, that allow the robotic device to move in any direction.”).
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to have combine the computing device for path planning for a mobile non-circular robot taught in Sinyavskiy in view of Tanaka in further view of Yabushita wherein the mobile non-circular robot comprises four mecanum wheels taught in Afrouzi with a reasonable expectation of success. One of ordinary skill in the art would have been motivated to make this modification because it is a simple substitution of known components. The mobile non-circular robot already taught in Sinyavskiy in view of Tanaka in further view of Yabushita is configured to be holonomic through the use of four omni wheels (Tanaka: Column 10 lines 4-23, “Thus, the autonomous mobile device 1 preferably includes a main body 10 provided with an electric motor 12 at the lower portion thereof and an onmi wheel 13 that is driven with the electric motor 12, and a laser range finder 20 to measure the distance to the obstacles existing in the periphery.”, Column 10 lines 24-35, “An onmi wheel 13 is mounted to a drive shaft 12A of each of the four electric motors 12. Specifically, the four onmi wheels 13 are mounted by being spaced at 90° intervals along the circumferential direction in a concyclic manner.”, Column 10 lines 36-52, “Based on this configuration, when the electric motor 12 is driven and the wheel 14 is rotated, the six free rollers 15 rotate integrally with the wheels 14. Meanwhile, as a result of the grounded free rollers 15 rotating, the omni wheel 13 can also move in a direction that is parallel with the rotating shaft of that wheel 14. Thus, by independently controlling the four electric motors 12 and independently adjusting the rotating direction and rotating speed of the respective four omni wheels 13, the autonomous mobile device 1 can be moved in an arbitrary direction (omni directionally).”). A person of ordinary skill in the art would have had the technological capabilities to know that omni wheel and mecanum wheels, while structed differently, allow a robot to move in any direction. Therefore, the omni wheel could be changed for mecanum wheels without changing or introducing new functionality. No inventive effort would have been required.
Regarding claim 20, Sinyavskiy in view of Tanaka in further view of Yabushita does not teach wherein the mobile non-circular robot comprises at least one mecanum wheel.
Afrouzi, in the same field of endeavor, teaches wherein the mobile non-circular robot comprises at least one mecanum wheel (Afrouzi: Figure 88B, Column 62 lines 40-60, “In some embodiments, the springs of the different suspension systems described herein may be replaced by other elastic elements such as rubber or with other mechanisms that provide similar function as the springs (e.g., magnets as described above). In some embodiments, the wheels used with the different suspension systems are mecanum wheels, allowing the VMP robot to move in any direction. For example, the VMP robot can travel diagonally by moving a front wheel and opposite rear wheel at one speed while the other wheels turn at a different speed, moving all four wheels in the same direction straight moving, running the wheels on one side in the opposite direction to those on the other side causing rotation, and running the wheels on one diagonal in the opposite direction to those on the other diagonal causes sideways movement. FIGS. 87A and 87B illustrate examples of a mecanum wheel 8700 attached to an arm 8701 of a robotic device. The arm may be coupled to a chassis of the robotic device. FIGS. 88A and 88B illustrate a front and bottom view of an example of a robotic device with mecanum wheels 8800, respectively, that allow the robotic device to move in any direction.”).
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to have combine the computing device for path planning for a mobile non-circular robot taught in Sinyavskiy in view of Tanaka in further view of Yabushita wherein the mobile non-circular robot comprises at least one mecanum wheel taught in Afrouzi with a reasonable expectation of success. One of ordinary skill in the art would have been motivated to make this modification because it is a simple substitution of known components. The mobile non-circular robot already taught in Sinyavskiy in view of Tanaka in further view of Yabushita is configured to be holonomic through the use of four omni wheels (Tanaka: Column 10 lines 4-23, “Thus, the autonomous mobile device 1 preferably includes a main body 10 provided with an electric motor 12 at the lower portion thereof and an onmi wheel 13 that is driven with the electric motor 12, and a laser range finder 20 to measure the distance to the obstacles existing in the periphery.”, Column 10 lines 24-35, “An onmi wheel 13 is mounted to a drive shaft 12A of each of the four electric motors 12. Specifically, the four onmi wheels 13 are mounted by being spaced at 90° intervals along the circumferential direction in a concyclic manner.”, Column 10 lines 36-52, “Based on this configuration, when the electric motor 12 is driven and the wheel 14 is rotated, the six free rollers 15 rotate integrally with the wheels 14. Meanwhile, as a result of the grounded free rollers 15 rotating, the omni wheel 13 can also move in a direction that is parallel with the rotating shaft of that wheel 14. Thus, by independently controlling the four electric motors 12 and independently adjusting the rotating direction and rotating speed of the respective four omni wheels 13, the autonomous mobile device 1 can be moved in an arbitrary direction (omni directionally).”). A person of ordinary skill in the art would have had the technological capabilities to know that omni wheel and mecanum wheels, while structed differently, allow a robot to move in any direction. Therefore, the omni wheel could be changed for mecanum wheels without changing or introducing new functionality. No inventive effort would have been required.
Response to Arguments
Applicant’s arguments with respect to claim(s) 1, 13, and 25 have been considered but are moot because the new ground of rejection does not rely on any reference applied in the prior rejection of record for any teaching or matter specifically challenged in the argument.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Noah W Stiebritz whose telephone number is (571)272-3414. The examiner can normally be reached Monday thru Friday 7-5 EST.
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, Ramon Mercado can be reached at (571) 270-5744. 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.
/N.W.S./Examiner, Art Unit 3658
/Ramon A. Mercado/Supervisory Patent Examiner, Art Unit 3658
Prosecution Insights