Method of simulating movement of an autonomous entity through an environment

• US 20040059548A1
• Filed: 09/09/2002
• Published: 03/25/2004
• 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
• Granted Patent: US 7,188,056 B2
• Time in Patent Office: Days
• US Class Current: 703/2
• 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 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.

2. A method according to claim 1, wherein if the 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 1, comprising choosing one of a plurality of compromise steps.

4. A method according to claim 1, wherein determining said region includes adapting within said region in dependence upon at least one locally perceivable condition.

5. A method according to claim 1, wherein determining said region includes adapting within 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 obstructions include other autonomous entities.

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

9. A method according to claim 1, wherein the determining of the 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, comprising determining the inconvenicnce function.

11. A method according to claim 10, wherein the provisional path includes a direction from said current location to said intended destination and the profile includes a preferred step length, and wherein the determining of the 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 the 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 the inconvenience function includes summing said second and third amounts of work.

14. A method according to claim 9, comprising determining the frustration function.

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

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

determining a fourth amount of work dependent upon a difference between the walking speed and the preferred instantaneous walking speed.

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

minimising said first dissatisfaction in respect of step length;

minimising said first dissatisfaction in respect of step orientation;

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

17. A method according to claim 1, wherein the determining whether said preferred step is feasible comprises determining whether there is any discomfort arising from the entity having to keep a distance which is different from a preferred distance from an obstruction.

18. A method according to claim 11, further comprising if there is discomfort arising from the entity having to keep a distance which is different from a preferred distance from an obstruction.

19. A method according to claim 1, comprising:

providing a preferred clearance tolerance for said entity; and

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

20. A method according to claim 19, comprising:

determining a density of neighbouring entities and

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

21. A method according to claim 19, comprising:

providing information relating to velocity of said entity; and

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

22. A method according to claim 1, wherein said considering 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 said considering 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 the 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 1, further comprising:

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

27. A method according to claim 26, wherein the determining of said set of attributes at least attributes comprises:

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

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

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

29. A computer program for performing the method of claim 1.

30. A computer-readable medium storing the computer program of claim 29.

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

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

all interface for providing a profile for said autonomous entity;

a processor for determining a preferred step towards said intended destination based upon said profile and said provisional path;

a processor for determining a personal space around said autonomous entity;

a processor for determining whether said preferred step is feasible by considering whether obstructions infringe said personal space.

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

providing a preferred clearance tolerance for said entity; and

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

33. A method according to claim 32, comprising:

determining a density of neighbouring entities and

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

34. A method according to claim 32, comprising:

providing information relating to velocity of said entity; and

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

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

providing a model of said building structure;

simulating movement of at least one entity through said building structure, the simulating of said movement of said at least one entity comprises 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; and

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

36. A method of controlling movement of an 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;

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