Notice of Pre-AIA or AIA Status
1. The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
2. Claim 10 rejected under 35 U.S.C. 101 because the claimed invention does not fall within one of the four statutory categories of invention.
The determination of whether a claim recites patent ineligible subject matter is a two-step inquiry.
STEP 1: the claim does not fall within one of the four statutory categories of invention (process, machine, manufacture or composition of matter), see MPEP 2106.03, or
STEP 2: the claim recites a judicial exception, e.g. an abstract idea, without reciting additional elements that amount to significantly more than the judicial exception, as determined using the following analysis: see MPEP 2106.04
STEP 2A (PRONG 1): Does the claim recite an abstract idea, law of nature, or natural phenomenon? see MPEP 2106.04(II)(A)(1)
STEP 2A (PRONG 2): Does the claim recite additional elements that integrate the judicial exception into a practical application? see MPEP 2106.04(II)(A)(2)
STEP 2B: Does the claim recite additional elements that amount to significantly more than the judicial exception? see MPEP 2106.05
101 Analysis – Step 1
Claim 10 is directed to a computer program, i.e. “software per se”. “Software per se”, when claimed without any structural limitations, does not have a physical or tangible form. Therefore, it does not fall within one of the four categories of patent eligible subject matter and is ineligible under 35 USC 101. see MPEP 2106.03.
If support is found within the specification, Applicant is advised to amend the claim(s) to recite “A non-transitory computer readable medium comprising a computer program comprising machine readable instructions that, when executed by a processor, performs: [the claimed functions]”, or equivalent language. see MPEP 2106.03 (I). A claim directed toward a non-transitory computer readable medium would comprise an article of manufacture and thus fall within one of the four categories of patent eligible subject matter.
Therefore, claim 10 is rejected under 35 USC §101 as being directed toward ineligible subject matter.
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
3. Claim 1, 9, and 10 are rejected under 35 U.S.C 102(a)(1) as being anticipated by Missura et al. (“Polygonal Perception for Mobile Robots”, https://ieeexplore.ieee.org/abstract/document/9341742).
Regarding claim 1, Missura teaches a control device (see [pg 10476] where a robot, i.e. an object or vehicle with a control device, to move and determine occupancy grid.) comprising:
a recognition part configured to recognize a position of an object present around a moving body on the basis of an image obtained by imaging a state around the moving body (see [pg 10477] where an ASUS Xtion Pro Live RGB-D sensor is used to deliver image of objects around a moving robot and is indicated that other cameras and higher resolutions are possible.);
an occupancy grid diagram generation part configured to generate an occupancy grid diagram including a plurality of grid cells on the basis of the position of the object present around the moving body (see Figs 2 and 5, [pg 10480] where floor samples are taken and occupancy grid is formed to show occupied areas on the floor nearby a moving robot with cells marked with 1s and 0s.); and
a route generation part configured to generate a route, which the moving body follows, on the basis of a contour of the object shown in the occupancy grid diagram (see Fig. 7 and [pg 10482] where motion planning of a moving robot is done based on polygons, which are contours, of objects provided on a grid diagram.),
wherein the occupancy grid diagram generation part determines whether the object is present for each of the plurality of grid cells in the occupancy grid diagram on the basis of the position of the object present around the moving body (see [pg 10476] where points that belong to a floor plane are removed and remaining points are sorted to an occupancy map, which is a 2D grid structure, i.e. determining object present for grid cells in an occupancy grid diagram.),
the occupancy grid diagram generation part generates a first contour showing a contour of a first region including a grid cell in which it is determined that the object is present (see [pg 10480] where 2D grid diagram have grid cells marked with 0s and 1s depending on whether or not it contains an occupancy point, then this binary image is used to detect contours of contiguous groups of cells, i.e. first region with first contour that contains occupancy points.), and
the occupancy grid diagram generation part generates a second contour, which includes the first region and which has an apex number smaller than that of the first contour, as the contour of the object (see [pg 10480], Figs 2 and 5 where initial valid polygons, i.e. contours, which are first region and first contours are reduced in complexity using Douglas Peucker algorithm, which joins line segments and reduce vertexes, i.e. apexes, of the first contours to generate second contours.).
Regarding claim 9, Missura teaches a control method of causing a computer to (see [pg 10476] where a robot, which is an object or vehicle with a control device and computing system, i.e. computer, to move and determine occupancy grid.):
recognize a position of an object present around a moving body on the basis of an image obtained by imaging a state around the moving body (see [pg 10477] where an ASUS Xtion Pro Live RGB-D sensor is used to deliver image of objects around a moving robot and is indicated that other cameras and higher resolutions are possible.);
generate an occupancy grid diagram including a plurality of grid cells on the basis of the position of the object present around the moving body (see Figs 2 and 5, [pg 10480] where floor samples are taken and occupancy grid is formed to show occupied areas on the floor nearby a moving robot with cells marked with 1s and 0s.);
generate a route, which the moving body follows, on the basis of a contour of the object shown in the occupancy grid diagram (see Fig. 7 and [pg 10482] where motion planning of a moving robot is done based on polygons, which are contours, of objects provided on a grid diagram.);
determine whether the object is present for each of the plurality of grid cells in the occupancy grid diagram on the basis of the position of the object present around the moving body (see [pg 10476] where points that belong to a floor plane are removed and remaining points are sorted to an occupancy map, which is a 2D grid structure, with cells marked with 1s and 0s for occupied and unoccupied area, i.e. determining object present for grid cells in an occupancy grid diagram.);
generate a first contour showing a contour of a first region including a grid cell in which it is determined that the object is present (see [pg 10480] where 2D grid diagram have grid cells marked with 0s and 1s depending on whether or not it contains an occupancy point, then this binary image is used to detect contours of contiguous groups of cells, i.e. first region with first contour that contains occupancy points.); and
generate a second contour, which includes the first region and which has an apex number smaller than that of the first contour, as the contour of the object (see [pg 10480], Figs 2 and 5 where initial valid polygons, i.e. contours, which are first region and first contours are reduced in complexity using Douglas Peucker algorithm, which joins line segments and reduce vertexes, i.e. apexes, of the first contours to generate second contours.).
Regarding claim 10, Missura teaches a program that causes a computer to execute (see [pg 10476] where a robot, which is an object or vehicle with a control device and computing system, i.e. computer with a program to execute instructions, to move and determine occupancy grid.):
processing of recognizing a position of an object present around a moving body on the basis of an image obtained by imaging a state around the moving body (see [pg 10477] where an ASUS Xtion Pro Live RGB-D sensor is used to deliver image of objects around a moving robot and is indicated that other cameras and higher resolutions are possible.);
processing of generating an occupancy grid diagram including a plurality of grid cells on the basis of the position of the object present around the moving body (see Figs 2 and 5, [pg 10480] where floor samples are taken and occupancy grid is formed to show occupied areas on the floor nearby a moving robot with cells marked with 1s and 0s.);
processing of generating a route, which the moving body follows, on the basis of a contour of the object shown in the occupancy grid diagram (see Fig. 7 and [pg 10482] where motion planning of a moving robot is done based on polygons, which are contours, of objects provided on a grid diagram.);
processing of determining whether the object is present for each of the plurality of grid cells in the occupancy grid diagram on the basis of the position of the object present around the moving body (see [pg 10476] where points that belong to a floor plane are removed and remaining points are sorted to an occupancy map, which is a 2D grid structure, with cells marked with 1s and 0s for occupied and unoccupied area, i.e. determining object present for grid cells in an occupancy grid diagram.);
processing of generating a first contour showing a contour of a first region including a grid cell in which it is determined that the object is present (see [pg 10480] where 2D grid diagram have grid cells marked with 0s and 1s depending on whether or not it contains an occupancy point, then this binary image is used to detect contours of contiguous groups of cells, i.e. first region with first contour that contains occupancy points.); and
processing of generating a second contour, which includes the first region and which has an apex number smaller than that of the first contour, as the contour of the object (see [pg 10480], Figs 2 and 5 where initial valid polygons, i.e. contours, which are first region and first contours are reduced in complexity using Douglas Peucker algorithm, which joins line segments and reduce vertexes, i.e. apexes, of the first contours to generate second contours.).
Claim Rejections - 35 USC § 103
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.
4. Claim 2 is rejected under pre-35 U.S.C. as being unpatentable over Missura in view of Musk et al. (US 20200257317A1).
Regarding claim 2, Missura teaches the control device according to claim 1,
wherein the route generation part generates the route which the moving body follows in a second region that is a region not surrounded by the second contour in the occupancy grid diagram (see [pg 10481] and Fig. 7 where motion planning uses polygons, i.e. second contour that shows occupancy, to avoid obstacles and move within an area not occupied by polygons, i.e. route in a second region that is a region not surrounded by second contour.)
Missura does not particularly teach:
a drive controller configured to control a drive device that drives the moving body such that the moving body moves along the route is further provided.
However, Musk teaches a vehicle controller to navigate along a path goal that was determined using occupancy grid generated (see Fig. 3 and [0043]-[0045]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the application to modify motion planning using occupancy grid that generates polygons of obstacle of Missura by incorporating teaching of Musk such that a controller drives a vehicle or moving robot moves along a path goal.
The motivation to have a controller that drives a vehicle or a moving robot to move a vehicle or robot along a planned path within a non-occupied second region is that, as indicated by Musk, this would allow for autonomous control and movement of a vehicle to ease and safely maneuver complex and often exhausting driving tasks (see [0001]).
5. Claim 8 is rejected under pre-35 U.S.C. as being unpatentable over Missura in view of Fistelmann et al. (EP3040909A1).
Regarding claim 8, Missura teaches the control device according to claim 1,
the occupancy grid diagram generation part generates the second contour by connecting the expanded first region with a concave hull (see Figs 2 and 5, [pg 10480] where removal of floor plane and determining occupancy grid with 1s and 0s. Then, occupancy cells are dilated to form a valid polygon in which the polygon is second contour that connects plurality of vertexes, which are apexes, from cells that contains points marked with 1s.),
Missura alone does not teach: wherein the occupancy grid diagram generation part generates the first contour by connecting the plurality of apexes of the first region with a convex hull,
the occupancy grid diagram generation part generates a plurality of parallel lines corresponding to each of a plurality of straight lines included in the first contour,
the occupancy grid diagram generation part expands the first region by connecting the plurality of parallel lines with each other.
However, Fistelmann does teach both convex hull and concave hull where convex hull encompasses all points within its boundary and concave hull adapts to form an object represented by a cluster of points (see Figs 2-4 and [0024]-[0025]).
Further, it would have been obvious to one of ordinary skill in the art before the effective filing date of the application to modify all points of cells in an occupancy grid marked with 1 of Missura by incorporating teaching of Fistelmann such that the points of cells in the occupancy grid marked with 1 to initially form a polygon connecting the outer cells as how a convex hull encompasses all points within its boundary to first form a first contour (Note that Missura already teaches in [pg 10480] to use points in cell with a Suzuki method to for a polygon, which therefore indicates that a polygon is formed before dilation if combined with convex hull teachings to form a boundary of cluster of points.). Then, dilation of the cells to form a polygon, i.e. a second contour, as also taught in Missura includes plurality of parallel lines corresponding to a plurality of straight lines included in the first contour since dilation is a transformation to resize a figure, which, in the case of Missura shown in [pg 10480], is to make it larger by radius of a robot.
The motivation to produce a convex hull initially with cells marked with 1 an occupancy grid is that, as indicated by Fistelmann, this would allow for smaller and less complex envelopes that are closer to actual size of objects surrounding a vehicle or robot which increases processing power and time and further provide space available for a vehicle to maneuver into (see [0006]-[0008]).
Allowable Subject Matter
6. Claims 3-7 objected to as being dependent upon rejected based claims, but would be allowable if rewritten in independent form including all of the limitations of the base claims and any intervening claims.
In regards to claim 3, the claim recites:
“the control device according to claim 1, wherein the occupancy grid diagram generation part selects a first apex from the plurality of apexes included in the first contour, and
the occupancy grid diagram generation part determines whether to delete the first apex from the first contour on the basis of a proportion occupied by the first region in a first range about the first apex.”
No single prior art reference has been found to anticipate these limitations particularly of “determines whether to delete the first apex from the first contour on the basis of a proportion occupied by the first region in a first range about the first apex”, nor any combination of prior art reference to render these limitations obvious, when viewed in the context of the remaining limitations of the claim. Therefore, claim 3 is found to be allowable if rewritten in independent form.
The dependent claims 4-7 would also be allowable by virtue of its dependency on allowable based claim 3 if claim 3 is rewritten in independent form.
Conclusion
7. The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
a. Park et al. (US 20220282977A1), method of reducing noise on a map. Generates a grid map and simplifies a contour of the grid map by getting rid of apexes.
b. Nagori et al. (US 20230202524A1), driver assistance system that reduces vertices, which are apexes, until bitmap exceeds pixel margin threshold.
c. Kuhnert et al. (US 11209539B2), a computer that detects objects around a vehicle and develops a map based on polygon having sides extending between objects.
d. Kazmaier et al. (US 20160005141A1), determines if removing a vertex, which is an apex, is within maximum allowable error value.
e. Cervelli et al. (EP 2575107A2), deletes a vertex, which is an apex, if a distance between a vertex and a new suggested line is within a given threshold.
f. Koning (“Douglas-Peucker”, https://psimpl.sourceforge.net/douglas-peucker.html), a website that shows how Douglas Peucker method works to reduce vertex, which is apex, of a contour.
g. Atul et al. (“Suzuki Contour Algorithm Opencv”, https://theailearner.com/tag/suzuki-contour-algorithm-opencv/), shows how Suzuki algorithm works to create a contour using grid cells.
8. Any inquiry concerning this communication or earlier communications from the examiner should be directed to HYANG AHN whose telephone number is (571)272-4162. The examiner can normally be reached M-F 9-5.
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, Ramya Burgess can be reached at 571-272-6011. 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.
/H.A./Examiner, Art Unit 3661
/MATTHIAS S WEISFELD/Examiner, Art Unit 3661