Method and apparatus of simulating movement of an autonomous entity through an environment

• US 7,188,056 B2
• Filed: 09/09/2002
• Issued: 03/06/2007
• Est. Priority Date: 09/09/2002
• Status: Active Grant

• Current Assignee: Bentley Systems (UK) Limited (Bentley Systems Incorporated)
• Original Assignee: The Maia Institute
• Inventors: Kagarlis, Marios
• Primary Examiner(s): Rodriguez; Paul
• Assistant Examiner(s): GUILL, RUSSELL L
• Application Number:
  US10/237,178
• Publication Number:
  US 20040059548A1
• Time in Patent Office: 1,639 Days
• Field of Search: 703/6
• US Class Current: 703/6
• CPC Class Codes: G06F 2111/08 Probabilistic or stochastic CAD
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30
• CPC Class Codes: G06N 3/004 Artificial life, i.e. computing arrangements simulating life

Abstract

A method of simulating movement of an autonomous entity through an environment, the method comprising providing a provisional path through a model of the environment from a current location to an intended destination, providing a profile for said autonomous entity, determining a preferred step towards said intended destination based upon said profile and said provisional path, determining a personal space around said autonomous entity and determining whether said preferred step is feasible by considering whether obstructions infringe said personal space.

Claims

1. A method of simulating movement of an autonomous entity through an environment, the method comprising:

providing a provisional path through a model of the environment from a current location to an intended destination;

providing a profile for said autonomous entity;

determining a preferred step towards said intended destination based upon cost of a step, said profile and said provisional path;

determining a personal space around said autonomous entity;

determining whether said preferred step is feasible by considering whether obstructions infringe said personal space; and

recording a feasible preferred step so as to allow movement of said autonomous entity to be determined.

2. A method according to claim 1, wherein if said preferred step is not feasible, then the method further comprises:

determining a region in which to seek a compromise step and

determining whether at least one compromise step is feasible.

3. A method according to claim 2, comprising choosing one of a plurality of compromise steps.

4. A method according to claim 2, wherein determining said region includes adapting step parameters to determine said region in dependence upon at least one locally perceivable condition.

5. A method according to claim 2, wherein determining said region includes adapting step parameters to determine said region in dependence upon memory of past conditions.

6. A method according to claim 1, wherein the determining of said personal space comprises defining a region in which absence of obstructions is sought.

7. A method according to claim 1, wherein said obstructions include other autonomous entities.

8. A method according to claim 1, wherein said obstructions include fixed obstructions.

9. A method according to claim 1, wherein the determining of said preferred step comprises determining a first dissatisfaction function comprising a sum of an inconvenience function and a frustration function.

10. A method according to claim 9, further comprising determining said inconvenience function to express a cost of deviating from a given direction.

11. A method according to claim 10, wherein said provisional path includes an optimal direction from said current location to said intended destination and said profile includes a preferred step length, and wherein the determining of said inconvenience function includes:

determining a first amount of work required to take a step of given step length;

determining a second amount of work which is a proportion of said first amount of work corresponding to a component which is not directed in said optimal direction.

12. A method according to claim 11, wherein the determining of said inconvenience function includes:

determining an acceleration associated with a change in velocity between said step and a previous step and

determining a third amount of work required to produce said acceleration.

13. A method according to claim 12, wherein the determining of said inconvenience function includes summing said second and third amounts of work.

14. A method according to claim 11, further comprising determining a discomfort function to express a cost arising from said autonomous entity having to keep a distance which is different from a preferred distance from an obstruction.

15. A method according to claim 9, further comprising determining said frustration function.

16. A method according to claim 15, wherein said profile includes a preferred walking speed and the determining of said frustration function comprises:

determining a preferred instantaneous walking speed by adding said preferred walking speed to walking speed noise; and

determining amount of work dependent upon a walking speed and said preferred instantaneous walking speed.

17. A method according to claim 9, wherein the determining of said preferred step comprises:

minimizing said first dissatisfaction function in respect of step length; and

minimizing said first dissatisfaction function in respect of step orientation;

thereby to obtain a preferred step length and a preferred step orientation.

18. A method according to claim 1, wherein the determining of whether said preferred step is feasible comprises determining a discomfort function to express a cost arising from the autonomous entity having to keep a distance which is different from a preferred distance from an obstruction.

19. A method according to claim 1 further comprising:

providing a preferred clearance tolerance for said autonomous entity; and

determining said personal space around said autonomous entity in dependence upon said preferred clearance tolerance.

20. A method according to claim 19, further comprising:

determining a density of neighbouring entities and

determining said personal space around said autonomous entity in dependence upon said preferred clearance tolerance and said density of neighbouring entities.

21. A method according to claim 19, further comprising:

providing information relating to velocity of said autonomous entity; and

determining an angular dependency for said personal space in dependence upon said velocity.

22. A method according to claim 1, wherein the considering of whether obstructions infringe said personal space comprises:

determining whether said personal space is infringed at a first position along said preferred step and

determining whether said personal space is infringed at a second position along said preferred step.

23. A method according to claim 22, wherein the considering of whether obstructions infringe said personal space further comprises:

determining whether said personal space is infringed at a third position along said preferred step.

24. A method according to claim 1, wherein if said preferred step is not feasible, then the method further comprises:

determining a region in which to seek a compromise step.

25. A method according to claim 24, wherein the determining of said region comprises defining an arc.

26. A method according to claim 24, wherein determining said region in which to seek a compromise step comprises:

establishing an angular range for a search.

27. A method according to claim 24, wherein determining said region in which to seek a compromise step comprises:

determining to which side of a preferred direction to search.

28. A method according to claim 1, further comprising:

determining a set of attributes for said autonomous entity in dependence upon said profile.

29. A method according to claim 28, wherein the determining of said set of attributes comprises:

determining at least one attribute at a time of generating said autonomous entity.

30. A method according to claim 28, further comprising:

modifying at least one attribute of said set of attributes for said autonomous entity.

31. A computer-readable medium storing a computer program for performing a method of simulating movement of an autonomous entity through an environment, the method comprising:

providing a provisional path through a model of the environment from a current location to an intended destination;

providing a profile for said autonomous entity;

determining a preferred step towards said intended destination based upon cost of a step, said profile and said provisional path;

determining a personal space around said autonomous entity;

determining whether said preferred step is feasible by considering whether obstructions infringe said personal space; and

recording a feasible preferred step so as to allow movement of said autonomous entity to be determined.

32. Apparatus for simulating movement of an autonomous entity through an environment, the apparatus comprising:

an interface that provides a provisional path through a model of the environment from a current location to an intended destination and that provides profile for said autonomous entity; and

one or more processors that determines a preferred step towards said intended destination based upon cost of a step, said profile and said provisional path,

that determines a personal space around said autonomous entity,

and that determines whether said preferred step is feasible by considering whether obstructions infringe said personal space; and

a memory that records a feasible preferred step so as to allow movement of said autonomous entity to be determined.

33. A method of simulating movement of an autonomous entity through an environment, the method comprising:

providing a preferred clearance tolerance for said autonomous entity;

determining a density of neighbouring entities;

determining a personal space around said autonomous entity in dependence upon said preferred clearance tolerance and said density of neighbouring entities; and

recording said personal space so as to allow movement of said autonomous entity to be determined.

34. A method of simulating movement of an autonomous entity through an environment, the method comprising:

providing a preferred clearance tolerance for said autonomous entity;

providing information relating to velocity of said entity;

determining a personal space around said autonomous entity in dependence upon said preferred clearance tolerance;

determining an angular dependency for said personal space in dependence upon said velocity; and

recording said personal space so as to allow movement of said autonomous entity to be determined.

35. A method of designing a building structure, the method comprising:

providing a model of said building structure;

simulating movement of at least one autonomous entity through said building structure, the simulating of said movement of said at least one autonomous entity comprising providing a provisional path through a model of the environment from a current location to an intended destination, providing a profile for said at least one autonomous entity, determining a preferred step towards said intended destination based upon cost of a step, said profile and said provisional path, determining a personal space around said at least one autonomous entity and determining whether said preferred step is feasible by considering whether obstructions infringe said personal space; and

revising said model of said building structure in dependence upon movement of said at least one autonomous entity.

36. A method of controlling movement of an autonomous entity through an environment, the method comprising:

providing a provisional path through a model of the environment from a current location to an intended destination;

providing a profile for said autonomous entity;

determining a preferred step towards said intended destination based upon cost of a step, said profile and said provisional path;

determining a personal space around said autonomous entity;

determining whether said preferred step is feasible by considering whether obstructions infringe said personal space; and

controlling movement of said autonomous entity based on the feasibility of said preferred step.

37. A computer-readable medium encoded with computer-executable instructions to perform a computer-implemented method of simulating movement of an autonomous entity through an environment, the method comprising:

providing a preferred clearance tolerance for said autonomous entity;

determining a density of neighbouring entities;

determining a personal space around said autonomous entity in dependence upon said preferred clearance tolerance and said density of neighbouring entities; and

recording said personal space so as to allow movement of said autonomous entity to be determined.

38. A computer-readable medium encoded with computer-executable instructions to perform a method of controlling movement of an autonomous entity through an environment, the method comprising:

providing a provisional path through a model of the environment from a current location to an intended destination;

providing a profile for said autonomous entity;

determining a preferred step towards said intended destination based upon cost of a step, said profile and said provisional path;

determining a personal space around said autonomous entity;

determining whether said preferred step is feasible by considering whether obstructions infringe said personal space; and

controlling movement of said autonomous entity based on the feasibility of said preferred step.

39. A computer-readable medium encoded with computer-executable instructions to perform a computer-implemented method of simulating movement of an autonomous entity through an environment, the method comprising:

providing a preferred clearance tolerance for said autonomous entity;

providing information relating to velocity of said entity;

determining a personal space around said autonomous entity in dependence upon said preferred clearance tolerance;

determining an angular dependency for said personal space in dependence upon said velocity; and

recording said personal space so as to allow movement of said autonomous entity to be determined.