DETAILED CORRESPONDENCE
This Office action is in response to the application filed 4/15/2026, with claims 1-18 pending.
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Objections
In light of Applicant’s remarks, the claim objection has been withdrawn
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claim 13 is rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
The phrase “more than a remote distance from the current voxel” in claim 13 renders the claim indefinite. The phrase “more than a remote distance from the current voxel” is not defined by the claim and the standard for ascertaining the requisite degree is unclear, and one of ordinary skill in the art would not be reasonably apprised of the scope of the invention.
Claim 13 recites the limitation “the objects” in line 1. There is insufficient antecedent basis for this limitation in the claim.
Response to Arguments
Applicant's arguments filed on 4/15/2026 have been fully considered but they are not persuasive.
Applicant alleges on page 9 that “Shengdong does not teach this voxel-neighborhood graph structure” and on page 11 that “Shengdong fails to disclose the amended voxel-based graph structure in which vertices represent empty voxels and edges connect empty voxels to adjacent empty neighbor voxels with corresponding voxel-to-voxel travel cost….” The Examiner disagrees.
In response, the Shengdong reference teaches that a three-dimensional (3D) space is divided into octree nodes. Here the spatial region of each octree node represents a 3D cube, which is a voxel. This reference teaches empty 3D space in an octree node in which the node is updated when it occupied by an obstacle (see p. 54, sec. III). Furthermore, adjacency between octree nodes (i.e. neighbor voxels) is determined based on algorithms. At least algorithm 1 addresses neighboring nodes (e.g. voxel) while algorithm 2 addresses both neighboring nodes and empty nodes see p. 55. The Shengdong reference is directed to 3D path planning using an octree nodes (e.g. a voxels) which is taught in at least the Abstract. Lastly, Shengdong teaches that “In our octree-based path planning algorithm, the 3D search space is discretized into an octree data structure based on the 3D occupancy map built by the 3D mapping module….Any edge in the octree-based state lattice can be decomposed into a series of high-resolution primitive motions. The edge corresponds to a feasible path whose costs and decompositions have been pre-computed and stored in the multi-resolution path lookup table described in the previous section. The octree-based state lattice is dynamically changing with constant 3D map updates and as the robot moves”, see pg. 54, col. 1, sec. III, para. 1 and pg. 56, sec. III, C., para. 1.
Claim Rejections - 35 USC § 103
The text of those sections of Title 35, U.S. Code not included in this action can be found in a prior Office action.
Claims 1-4, 8-9 and 12-16 are rejected under 35 U.S.C. 102(a)(1) as being anticipate by Xu, Shengdong, et al. “Real-time 3D navigation for autonomous vision-guided MAVs.” 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2015 hereinafter “Shengdong” in view of S. Hrabar, “Reactive obstacle avoidance for Rotorcraft UAVs,” 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, San Francisco, CA, USA, 2011, pp. 4967-4974, hereinafter “Hrabar”.
Claims 1 and 15. Shengdong teaches a method performed by a computing system for identifying a travel path based on voxels for a vehicle to travel from a current voxel to a target voxel (pg. 53, col. 1, para. 3 describes this element as such—“we come up
with a novel octree-based state lattice which is a memory efficient discrete representation of the search space, and we present a method of finding a near-optimal path based on the octree-partitioned 3D space by using standard graph search algorithms such as A*, or its variants D* [3] and AD*”, fig 2 and fig. 3), the method comprising:
for each empty voxel and each empty neighbor voxel adjacent the empty voxel, calculating a cost of traveling from the empty voxel to the empty neighbor voxel (pg. 52, sec. A discusses a movement cost and reads on this element as such—“The cost of a primitive motion is proportional to its path length except for the turning movement which has a cost corresponding to a 25cm path length. Backward movements are penalized with a weighted factor greater than 1 as obstacles at the rear cannot be observed with a forward-facing camera, and thus, we want to avoid backward movements if possible.” “In our octree-based path planning algorithm, the 3D search space is discretized into an octree data structure based on the 3D occupancy map built by the 3D mapping module”, see pg. 55, sec. III, para. 1. ). Furthermore, adjacency between octree nodes is determined based on algorithms. At least algorithm 1 addresses neighboring nodes (e.g. voxel) while algorithm 2 addresses both neighboring nodes and empty nodes see p. 55. See Abstract); and
applying a minimal cost path algorithm to a graph to determine a travel path between the current voxel and the target voxel, where vertices of the graph represent empty voxels, edges of the graph connect empty voxels to empty neighbor voxels, and the costs are associated with the edges (pg. 56 col. 2, para. 1 teaches “Any edge in the octree-based state lattice can be decomposed into a series of high-resolution primitive motions. The edge corresponds to a feasible path whose costs and decompositions have been pre-computed and stored in the multi-resolution path lookup table described in the previous section. The octree-based state lattice is dynamically changing with constant 3D map updates and as the robot moves.” While pg. 54, col. 1, last para. thru col. 2 along with pg. 55, col. 2, sec. C describes scenario that reads on this element as such—“…then update the octree with information about obstacles from the 3D occupancy map. For each labeled voxel in the 3D occupancy map and whose label either corresponds to free or occupied space, we recursively After creating both the local regular state lattice and the global octree-based state lattice, the next step is to perform graph search to find an optimal path. Any edge in the octree-based state lattice can be decomposed into a series of high-resolution primitive motions. The edge corresponds to a feasible path whose costs and decompositions have been pre-computed and stored in the multi-resolution path lookup table described in the previous section. The octree-based state lattice is dynamically changing with constant 3D map updates and as the robot moves. 1) Optimal Path Finding: To show the efficiency of our octree-based state lattice, we use a simple A* graph search algorithm to generate optimal paths. Of course, it is possible to implement AD* or any other variant of the A* graph search algorithm for the octree-based state lattice. The edge costs between octree node states can be obtained from the multi-resolution path lookup table. The graph search algorithm finds an optimal trajectory that consists of octree node states.” Thus, the cited section taken together reads on this element. ).
Shengdong does not teach empty voxels not associated with objects that the vehicle is to avoid.
Yet, Hrabar teaches accessing indications of object voxels associated with objects that the vehicle is to avoid and empty voxels not associated with objects that the vehicle is to avoid (Hrabar on pg. 4968, sec. II, A—describes a scenario that reads on this element as such –“If an obstacle is detected, an Escape Point (P) is searched for in free space and if found this becomes a new intermediate waypoint between the current position and the goal…. A moving object would produce an elongated volume of occupied voxels along the trajectory it had followed. The algorithm would avoid this entire volume so would be successful but suboptimal since it avoids areas where the obstacle no longer exists.” Here the claim language of “…empty voxels not associated with objects that the vehicle is to avoid” is being interpretated as voxels once occupied by an object that the vehicle is to avoid; however, these voxel are now empty voxels because the obstacle no longer exists in that area.);
Therefore, it would have been obvious to one of ordinary skills in the art before the effective filing date of the claimed invention to combine the teaching of Hrabar with the invention Shengdong because such combination would provide a collision-free path from the current position to next position (see pg. 4969, col. 1, para. 2, Hrabar).
Claim 2. Shengdong teaches the method of claim 1 further comprising specifying a travel direction for the vehicle as the direction of the empty neighbor voxel of the current voxel that is along the travel path (pg. 54, sec. A and pg. 55, col. 1, last para. – pg. 55, col. 2, last para. reads on this element as such—“The pre-computed canonical set of maximum-resolution motion primitives consists of turning on the spot in both the left and right directions, moving up and down vertically, and moving forward and backward in several directions. The cost of a primitive motion is proportional to its path length except for the turning movement which has a cost corresponding to a 25cm path length…. heading direction….” This reference teaches empty 3D space is an octree node in which the node is updated when it occupied by an obstacle (see p. 54, sec. III). Furthermore, adjacency between octree nodes (i.e. neighbor voxels) is determined based on algorithms. At least algorithm 1 addresses neighboring nodes (e.g. voxel) while algorithm 2 addresses both neighboring nodes and empty nodes see p. 55.).
Claim 3. Shengdong teaches the method of claim 2 further comprising directing the vehicle to travel in the travel direction (pg. 54, sec. A, reads on this element as such—“The primitive motions can be seen as a canonical set of short feasible control samples that satisfy the differential constraints of the system.”).
Claims 4 and 16. Shengdong teaches the method of claim 1 wherein the costs are based on a distance transform that identifies the distance from an empty voxel to the nearest object voxel (pg. 55, col 2, para. 1 teaches a scenario that reads on this element as such—“Here, we use a naive method to determine whether two octants are adjacent to each other; we check whether the distance between the centres of the two octants along each of the x, y and z directions exceeds half of the sum of the two octants' cell sizes, and if so, we ascertain that the two octants are not adjacent. Each time a node gets split, we look for adjacency relationships with respect to the node's children.” While, pg. 56, sec. C. col. 2, para. 4 reads on this element as such—“The octree-based path planner is constrained to plan trajectories through the centers of octree node states and states in the local regular 3D state lattice. By using an octree based state lattice, we greatly reduce the number of candidate states for the A* algorithm to expand. As a result, the A* algorithm is able to find the best path in a short time.” Here an octree node is interpreted as a voxel.).
Claim 8. Shengdong teaches the method of claim 1 wherein the minimal cost path algorithm is a Dijkstra-based algorithm (on pg. 55, col. 1, last para. reads on this element as such—“The precomputation step shown in Algorithm 2 can be performed via the Dijkstra's algorithm”).
Claim 9. Shengdong teaches the method of claim 6 wherein the minimal cost path algorithm employs a Fibonacci heap (pg. 55 teaches algorithm 1 and 2. While optimal path finding is taught on pg. 56, col. 2 – pg. 57, col. 1).
Claim 12. Shengdong teaches the method of claim 10 wherein a time interval is adjusted based on risk tolerance of the vehicle colliding with an object (pg. 58, col. 2, second from last para. describes this element as such—“The MAY was able to perceive the environment and incrementally build a 3D map in real-time. At the same time, the octree-state-lattice-based path planner was constantly able to provide near-optimal trajectories which were collision-free and led the MAY to the goal state. Throughout the whole process, our path planner took less than one second to find
a near-optimal path.”).
Claim 13. Shengdong teaches the method of claim 1 wherein the objects exclude objects that are more than a remote distance from the current voxel (pg. 57, col. 1, para. 2 describes a scenario that reads on this element as such—“In the above example, there are only four tree node states along the path but there are many more waypoints along the full path. This is because the actual path from one tree node state to another is decomposed into a series of high-resolution primitive motions.”).
Claim 14. Shengdong teaches the method of claim 13 wherein the remote distance is adjusted based on risk tolerance of the vehicle colliding with the object (pg. 58, col. 2, second para. from bottom reads on this element as such—“At the same time, the
octree-state-lattice-based path planner was constantly able to provide near-optimal trajectories which were collision-free and led the MAY to the goal state.”).
Claim 6 is rejected under 35 U.S.C. 103 as being unpatentable over Shengdong in view of Rathbun, David, et al. “An evolution based path planning algorithm for autonomous motion of a UAV through uncertain environments.” Proceedings. The 21st digital avionics systems conference. Vol. 2. IEEE, 2002, hereinafter “Rathbun”.
Claim 6. Shengdong teaches the method of claim 1; however, Shengdong is silent on the term density. Yet, Rathbun teaches wherein the costs are calculated based on environmental measures that include a transform distance measure, an object density measure, and a zone permeability measure (pg. 8.D.2-5, col. 2 teaches on probability density as it relates to objects).
Therefore, it would have been obvious to one of ordinary skills in the art before the effective filing date of the claimed invention to combine the teaching of Rathbun with the invention of Shengdong because such combination would provide safe route through a field of obstacles at uncertain locations (see Abstract, Rathbun).
Allowable Subject Matter
Claims 5, 7, 10, 11, 17 and 18 objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ANA D THOMAS whose telephone number is (571)272-8549. The examiner can normally be reached Monday - Friday 8 - 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.
/A.D.T/Examiner, Art Unit 3661
/RUSSELL FREJD/Primary Examiner, Art Unit 3661
Prosecution Insights