# US 11,906,971 B2 · Spatiotemporal robotic navigation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,906,971 B2 - Document ID: US11906971B2 - Status: Granted - Kind: B2 - Application number: 17/409,480 - Filed: 2021-08-23 - Published: 2021-12-09 - Granted: 2024-02-20 - Earliest claimed: 2018-07-24 - Assignees: inVia Robotics, Inc. - Applicants: inVia Robotics, Inc. - Inventors: William Shane Simpson Grant; Randolph Charles Voorhies; Lior Elazary; Daniel Frank Parks, II - Web page: https://patentgrep.com/patent/US11906971B2 ## CPC - G05D 1/69: Coordinated control of the position or course of two or more vehicles - G05D 1/00: Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots (drive control systems specially adapted for autonomous road vehicles B60W60/00) - G05D 1/0217: {in accordance with energy consumption, time reduction or distance reduction criteria} - G05D 1/0219: {ensuring the processing of the whole working surface} - G05D 1/0291: {Fleet control (monitoring fleets in traffic control systems for road vehicles G08G1/127, G08G1/127)} - G05D 1/22: Command input arrangements - G05D 1/644: Optimisation of travel parameters, e.g. of energy consumption, journey time or distance - G05D 1/648: Performing a task within a working area or space, e.g. cleaning - G05D 1/695: for maintaining a fixed relative position of the vehicles, e.g. for convoy travelling or formation flight - G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES ## Abstract Spatiotemporal robotic navigation may include providing a set of robots non-conflicting access to the same shared resources at different times so that the robots may operate without continually accounting for the locations of the other robots and workers operating in the particular site, without continually planning or updating paths after determining an initial path, and without continuously adjusting movements as the robots near one another. The spatiotemporal robotic navigation involves generating spatiotemporal plans. Each plan has a set of objectives that a robot is to execute by different time intervals. Each plan is generated so as to not conflict with the resources being accessed by other robots at time intervals set in the plans of other robots. ## Claims ### Claim 1 A method comprising: mapping a plurality of resources in a site, wherein the plurality of resources are used by a plurality of workers during completion of different tasks; receiving a first task for completion by a first worker of the plurality of workers; detecting a first set of the plurality of resources with which to complete the first task in a least amount of time; reserving, as part of a first plan, each resource of the first set of resources with a different temporal element; controlling operation of the first worker in completing the first task by the different temporal element specified for each resource of the first set of resources in the first plan; receiving a second task for completion by a second worker of the plurality of workers; detecting a second set of the plurality of resources with which to complete the second task in a least amount of time without temporal conflict with the first set of resources reserved for the first plan; reserving, as part of a second plan, each resource of the second set of resources with a different temporal element that is not conflicting with the temporal element of a common resource also specified as part of the first plan; and controlling operation of the second worker in completing the second task by the different temporal element specified for each resource of the second set of resources in the second plan. ### Claim 2 (depends on 1) The method of claim 1, wherein reserving each resource of the second set of resources comprises reserving a particular resource with a first temporal element corresponding to a first time, and wherein the particular resource is reserved as part of the first set of resources with a second temporal element corresponding to a second time that is different than the first time. ### Claim 3 (depends on 1) The method of claim 1 further comprising: receiving a third task for completion by a third worker of the plurality of workers; detecting a third set of the plurality of resources with which to complete the third task in a least amount of time without temporal conflict with the first set of resources reserved for the first plan and the second set of resources reserved for the second plan; reserving, as part of a third plan, each resource of the third set of resources with a different temporal element that is not conflicting with the temporal element of a common resource also specified as part of the first plan or the second plan; and controlling operation of the third worker in completing the third task by the different temporal element specified for each resource of the third set of resources in the third plan. ### Claim 4 (depends on 1) The method of claim 1, wherein controlling operation of the first worker comprises: monitoring that the first worker accesses each particular resource of the first set of resource by or within the temporal element specified for that particular resource. ### Claim 5 (depends on 1) The method of claim 1, wherein each particular resource of the first set of resources corresponds to a different waypoint in the site, and wherein the temporal element specified for each particular resource corresponds to a future time the particular resource is reserved for exclusive access by the first worker. ### Claim 6 (depends on 1) The method of claim 1, wherein the first worker is an autonomous robot, and wherein controlling operation of the first worker comprises adjusting actuators of the autonomous robot to cause the autonomous robot to access each resource of the first set of resources by the temporal element specified for each resource. ### Claim 7 (depends on 1) The method of claim 1 further comprising: determining that the second worker is to access a particular resource of the first set of resources and the second set of resources before the first worker; and marking the particular resource in the first plan and in the second plan with a precedence ordering indicating that the second worker is to access the particular resource before the first worker. ### Claim 8 (depends on 7) The method of claim 7, wherein controlling operation of the first worker comprises: halting the operation of the first worker in response to the first worker reaching the particular resource before the second worker; receiving a message indicating that the second worker has accessed the particular resource; and continuing the operation of the first worker in response to receiving the message. ### Claim 9 (depends on 1) The method of claim 1 further comprising: tracking different sets of the plurality of resources that have been reserved for other plans pending execution, and temporal elements specified for each resource of the different sets of resources; determining available resources at different temporal elements that do not conflict with the different sets of resources at the temporal elements specified for the different sets of resources; selecting at least a first group of available resources and a second group of available resources with which to complete the first task; simulating performance of completing the first task using the first group of available resources and using the second group of available resources; and wherein detecting the first set of resources comprises defining the second group of available resources for the first plan based on the second group of available resources providing resulting in quicker completion of the first task than the second group of available resources. ### Claim 10 (depends on 1) The method of claim 1 further comprising: receiving a set of messages from the first worker, each message of the set of messages comprising an identifier for a resource of the first set of resources and a timestamp; and monitoring operation of the first worker in completing the first task based on the timestamp and identifier of each message of the set of messages being within the temporal element for a resource that is identified by the identifier of each message. ### Claim 11 (depends on 1) The method of claim 1, wherein the first set of resources comprises a shortest path from a current position of the first worker to a first destination of the first task, and wherein the second set of resources comprises a shortest path from a current position of the second worker to a second destination of the second task that does not conflict with the first set of resources at common points in time. ### Claim 12 (depends on 1) The method of claim 1 further comprising: receiving a third task for completion by the first worker after completion of the first task; detecting a third set of the plurality of resources with which to complete the third task in a least amount of time from a starting position corresponding to a position of a last resource of the first set of resources; reserving, as part of a third plan, each resource of the third set of resources with a different temporal element; and controlling operation of the first worker in completing the third task after successfully completing the first task and accessing the first set of resources by the different temporal element specified for each resource of the first set of resources. ### Claim 13 (depends on 1) The method of claim 1 further comprising: determining unsuccessful execution of the first plan based on the first worker not accessing a particular resource of the first set of resources by the temporal element that is specified for the particular resource in the first plan; determining that the unsuccessful execution of the first plan creates a conflict that prevents the second worker from accessing the particular resource of the second set of resources according to the temporal element that is specified for the particular resource in the second plan; and adjusting the operation of the second worker to workaround the conflict. ### Claim 14 (depends on 13) The method of claim 13, wherein adjusting the operation comprises: selecting an available resource adjacent to the particular resource; and accessing the available resource instead of the particular resource during the temporal element that is specified for the particular resource in the second plan. ### Claim 15 (depends on 14) The method of claim 14, wherein selecting the available resource comprises: scanning other plans to determine resources neighboring the particular resource that are reserved during the temporal element that is specified for the particular resource in the second plan; and identifying the available resource in response to determining that the available resource is not reserved by the other plans during the temporal element that is specified for the particular resource in the second plan. ### Claim 16 (depends on 13) The method of claim 13, wherein adjusting the operation comprises: adjusting one or more of the temporal elements for resources of the second set of resources that are before the particular resource in the second plan or that are after the particular resource in the second plan. ### Claim 17 (depends on 13) The method of claim 13, wherein adjusting the operation comprises: discarding a first subset of the second set of resources that come after the particular resource in the second plan; and detecting a second subset of resources with which to complete the second task in a least amount of time while avoiding the conflict at the particular resource. ### Claim 18 A device comprising: one or more processors configured to: map a plurality of resources in a site, wherein the plurality of resources are used by a plurality of workers during completion of different tasks; receive a first task for completion by a first worker of the plurality of workers; detect a first set of the plurality of resources with which to complete the first task in a least amount of time; reserve, as part of a first plan, each resource of the first set of resources with a different temporal element; control operation of the first worker in completing the first task by the different temporal element specified for each resource of the first set of resources in the first plan; receive a second task for completion by a second worker of the plurality of workers; detect a second set of the plurality of resources with which to complete the second task in a least amount of time without temporal conflict with the first set of resources reserved for the first plan; reserve, as part of a second plan, each resource of the second set of resources with a different temporal element that is not conflicting with the temporal element of a common resource also specified as part of the first plan; and control operation of the second worker in completing the second task by the different temporal element specified for each resource of the second set of resources in the second plan. ### Claim 19 A non-transitory computer-readable medium, storing a plurality of processor-executable instructions to: map a plurality of resources in a site, wherein the plurality of resources are used by a plurality of workers during completion of different tasks; receive a first task for completion by a first worker of the plurality of workers; detect a first set of the plurality of resources with which to complete the first task in a least amount of time; reserve, as part of a first plan, each resource of the first set of resources with a different temporal element; control operation of the first worker in completing the first task by the different temporal element specified for each resource of the first set of resources in the first plan; receive a second task for completion by a second worker of the plurality of workers; detect a second set of the plurality of resources with which to complete the second task in a least amount of time without temporal conflict with the first set of resources reserved for the first plan; reserve, as part of a second plan, each resource of the second set of resources with a different temporal element that is not conflicting with the temporal element of a common resource also specified as part of the first plan; and control operation of the second worker in completing the second task by the different temporal element specified for each resource of the second set of resources in the second plan.