# US 12,008,720 B1 · Scene graph assisted navigation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,008,720 B1 - Document ID: US12008720B1 - Status: Granted - Kind: B1 - Application number: 17/746,218 - Filed: 2022-05-17 - Granted: 2024-06-11 - Earliest claimed: 2021-06-28 - Assignees: Apple Inc. - Applicants: Apple Inc. - Inventors: Bo Morgan; Payal Jotwani; Angela Blechschmidt; Mark E. Drummond; Daniel Ulbricht - Web page: https://patentgrep.com/patent/US12008720B1 ## CPC - G06T 19/003: {Navigation within 3D models or images} - G06T 2200/24: involving graphical user interfaces [GUIs] - G06T 2210/61: Scene description - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract In one implementation, a method of achieving an objective using a scene graph includes identifying a set of transition couples of a plurality of transition couples between sets of spatial relationships of the scene graph, wherein each spatial relationship of a respective first set of spatial relationships indicated by each transition couple of the set of transition couples is included in an initial set of spatial relationships or an respective second set of spatial relationships indicated by a previous transition couple and wherein a particular spatial relationship is included in a respective second set of spatial relationships of a last transition couple of the set of transition couples. ## Claims ### Claim 1 A method performed at a device that includes a display, one or more processors, and non-transitory memory, the method comprising: obtaining a scene graph as a data structure representing a plurality of objects and an initial set of spatial relationships between respective pairs of the plurality of objects, wherein the plurality of objects includes an objective-effectuator object; obtaining from the scene graph a plurality of transition couples, wherein each transition couple indicates a transition from respective first set of spatial relationships in the scene graph between respective pairs of the plurality of objects to a respective second set of spatial relationships in the scene graph between respective pairs of the plurality of objects; displaying, on the display, a representation of the objective-effectuator object in association with other objects of the plurality of objects in an environment having the initial set of spatial relationships in the scene graph; obtaining an objective indicative of a particular spatial relationship in the scene graph between a first object of the plurality of objects and a second object of the plurality of objects; identifying a set of transition couples of the plurality of transition couples in the scene graph, wherein each spatial relationship of the respective first set of spatial relationships indicated by each transition couple of the set of transition couples in the scene graph is included in the initial set of spatial relationships or the respective second set of spatial relationships indicated by a previous transition couple in the scene graph and wherein the particular spatial relationship in the scene graph is included in the respective second set of spatial relationships of a last transition couple of the set of transition couples in the scene graph; displaying a representation of the objective-effectuator object in association with other objects of the plurality of objects in the environment having the respective second set of spatial relationships of each transition couple of the set of transition couples in the scene graph; failing to identify a set of transition couples of a first portion of the plurality of transition couples in the scene graph, wherein each spatial relationship of the respective first set of spatial relationships indicated by each transition couple of the set of transition couples in the scene graph is included in the initial set of spatial relationships or the respective second set of spatial relationships indicated by a previous transition couple in the scene graph and wherein the particular spatial relationship in the scene graph is included in the respective second set of spatial relationships of a last transition couple of the set of transition couples in the scene graph; and in response to failing to identify the set of transition couples of the first portion of the plurality of transition couples in the scene graph, obtaining a second portion of the plurality of transition couples in the scene graph. ### Claim 2 (depends on 1) The method of claim 1, wherein the plurality of objects includes at least one physical object. ### Claim 3 (depends on 1) The method of claim 1, wherein the first object of the plurality of objects is the objective-effectuator object. ### Claim 4 (depends on 1) The method of claim 1, further comprising storing data identifying the set of transition couples in association with the initial set of spatial relationships and the particular spatial relationship. ### Claim 5 (depends on 1) The method of claim 1, wherein each of the plurality of transition couples is certified. ### Claim 6 (depends on 5) The method of claim 5, wherein each of the plurality of transition couples is certified based on a capability of the transition. ### Claim 7 (depends on 5) The method of claim 5, wherein each of the plurality of transition couples is certified based on a permission for the transition. ### Claim 8 (depends on 1) The method of claim 1, wherein obtaining the second portion of the plurality of transition couples includes: displaying, on the display, an indication of failing to identify a set of transition couples of the first portion of the plurality of transition couples; and receiving user input indicative of a transition couple of the second portion of the plurality of transition couples. ### Claim 9 A device comprising: a display; a non-transitory memory; and one or more processors to: obtain a scene graph as a data structure representing a plurality of objects and an initial set of spatial relationships between respective pairs of the plurality of objects, wherein the plurality of objects includes an objective-effectuator object; obtain from the scene graph a plurality of transition couples, wherein each transition couple indicates a transition from respective first set of spatial relationships in the scene graph between respective pairs of the plurality of objects to a respective second set of spatial relationships in the scene graph between respective pairs of the plurality of objects; display, on the display, a representation of the objective-effectuator object in association with other objects of the plurality of objects in an environment having the initial set of spatial relationships in the scene graph; obtain an objective indicative of a particular spatial relationship in the scene graph between a first object of the plurality of objects and a second object of the plurality of objects; identify a set of transition couples of the plurality of transition couples in the scene graph, wherein each spatial relationship of the respective first set of spatial relationships indicated by each transition couple of the set of transition couples in the scene graph is included in the initial set of spatial relationships or the respective second set of spatial relationships indicated by a previous transition couple in the scene graph and wherein the particular spatial relationship in the scene graph is included in the respective second set of spatial relationships of a last transition couple of the set of transition couples in the scene graph; display a representation of the objective-effectuator object in association with other objects of the plurality of objects in the environment having the respective second set of spatial relationships of each transition couple of the set of transition couples in the scene graph; fail to identify a set of transition couples of a first portion of the plurality of transition couples in the scene graph, wherein each spatial relationship of the respective first set of spatial relationships indicated by each transition couple of the set of transition couples in the scene graph is included in the initial set of spatial relationships or the respective second set of spatial relationships indicated by a previous transition couple in the scene graph and wherein the particular spatial relationship in the scene graph is included in the respective second set of spatial relationships of a last transition couple of the set of transition couples in the scene graph; and in response to failing to identify the set of transition couples of the first portion of the plurality of transition couples in the scene graph, obtain a second portion of the plurality of transition couples in the scene graph. ### Claim 10 (depends on 9) The device of claim 9, wherein the plurality of objects includes at least one physical object. ### Claim 11 (depends on 9) The device of claim 9, wherein the first object of the plurality of objects is the objective-effectuator object. ### Claim 12 (depends on 9) The device of claim 9, wherein the one or more processors are further to store data identifying the set of transition couples in association with the initial set of spatial relationships and the particular spatial relationship. ### Claim 13 (depends on 9) The device of claim 9, wherein each of the plurality of transition couples is certified. ### Claim 14 (depends on 13) The device of claim 13, wherein each of the plurality of transition couples is certified based on a capability of the transition. ### Claim 15 (depends on 13) The device of claim 13, wherein each of the plurality of transition couples is certified based on a permission for the transition. ### Claim 16 (depends on 9) The device of claim 9, wherein the one or more processors are to obtain the second portion of the plurality of transition couples by: displaying, on the display, an indication of failing to identify a set of transition couples of the first portion of the plurality of transition couples; and receiving user input indicative of a transition couple of the second portion of the plurality of transition couples. ### Claim 17 A non-transitory memory storing one or more programs, which, when executed by one or more processors of a device including a display, cause the device to: obtain a scene graph as a data structure representing a plurality of objects and an initial set of spatial relationships between respective pairs of the plurality of objects, wherein the plurality of objects includes an objective-effectuator object; obtain from the scene graph a plurality of transition couples, wherein each transition couple indicates a transition from respective first set of spatial relationships in the scene graph between respective pairs of the plurality of objects to a respective second set of spatial relationships in the scene graph between respective pairs of the plurality of objects; display, on the display, a representation of the objective-effectuator object in association with other objects of the plurality of objects in an environment having the initial set of spatial relationships in the scene graph; obtain an objective indicative of a particular spatial relationship in the scene graph between a first object of the plurality of objects and a second object of the plurality of objects; identify a set of transition couples of the plurality of transition couples in the scene graph, wherein each spatial relationship of the respective first set of spatial relationships indicated by each transition couple of the set of transition couples in the scene graph is included in the initial set of spatial relationships or the respective second set of spatial relationships indicated by a previous transition couple in the scene graph and wherein the particular spatial relationship in the scene graph is included in the respective second set of spatial relationships of a last transition couple of the set of transition couples in the scene graph; display a representation of the objective-effectuator object in association with other objects of the plurality of objects in the environment having the respective second set of spatial relationships of each transition couple of the set of transition couples in the scene graph; fail to identify a set of transition couples of a first portion of the plurality of transition couples in the scene graph, wherein each spatial relationship of the respective first set of spatial relationships indicated by each transition couple of the set of transition couples in the scene graph is included in the initial set of spatial relationships or the respective second set of spatial relationships indicated by a previous transition couple in the scene graph and wherein the particular spatial relationship in the scene graph is included in the respective second set of spatial relationships of a last transition couple of the set of transition couples in the scene graph; and in response to failing to identify the set of transition couples of the first portion of the plurality of transition couples in the scene graph, obtain a second portion of the plurality of transition couples in the scene graph. ### Claim 18 (depends on 17) The non-transitory computer-readable medium of claim 17, wherein the device is further to store data identifying the set of transition couples in association with the initial set of spatial relationships and the particular spatial relationship.