Movement of an autonomous entity through an environment

• US 20050261886A1
• Filed: 09/09/2003
• Published: 11/24/2005
• 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,389,210 B2
• Time in Patent Office: Days
• US Class Current: 703/22
• 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 determining a path 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, die 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, wherein determining said preferred step comprises determining a first dissatisfaction function for expressing a cost of taking a step comprising a sum of an inconvenience function for expressing a cost of deviating from a given direction and a frustration function for expressing a cost of deviating from a given speed;

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 step parameters for determining said region in dependence upon at least one locally perceivable condition.

5. A method according to claim 1, wherein determining said region includes adapting step parameters for determining 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, comprising determining the inconvenience function for expressing a cost of deviating from a given direction.

10. A method according to claim 9, 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.

11. A method according to claim 9, 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.

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

13. A method according to claim 1, comprising determining the frustration function.

14. A method according to claim 13, 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.

15. A method according to claim 1, 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.

16. A method according to claim 1, wherein the determining whether said preferred step is feasible comprises determining a discomfort function for expressing a cost arising from the entity having to keep a distance which is less than a preferred distance from an obstruction.

17. 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.

18. A method according to claim 17, 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.

19. A method according to claim 17, comprising:

providing information relating to velocity of said entity; and

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

20. 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.

21. A method according to claim 20, 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.

22. 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.

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

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

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

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

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

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

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

27. A method according to claim 1, wherein providing said profile for said autonomous entity comprises:

basing said profile on a set of measured attributes.

28. A method according to claim 1, wherein providing said profile for said autonomous entity comprises:

statistically assigning said profile.

29. A method according to claim 1, wherein providing said profile for said autonomous entity comprises:

providing said profile in dependence upon at least one aspect of said environment.

30. A method according to claim 1, wherein providing said provisional path through said model of the environment from said current location to said intended destination comprises:

determining a beating from said current location to said intended destination.

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

providing a preferred clearance tolerance for said entity; and

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

32. A method according to claim 31, 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.

33. A method according to claim 31, comprising:

providing information relating to velocity of said entity; and

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

34. 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, according to claim 1;

and

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

35. A method according to claim 1, comprising:

determining said step towards said intended destination while minimising deviation from a preferred speed.

36. A method according to claim 1, comprising:

selecting said step towards said intended destination while maintaining at least a minimum distance from obstacles.

37. A method according to claim 1, comprising:

defining a neighbourhood;

scanning said neighbourhood for obstacles;

determining at least one condition relating to said obstacles and

defining an area in which to seek a step towards said destination in dependence upon said at least one condition.

39. A method according to claim 37, wherein determining said at least one condition relating to said obstacles comprises:

determining a density of one type of obstacle.

40. A method according to any one of claims 37, wherein defining said area in which to seek a step towards said destination comprises:

establishing an angular range for a search.

41. A method according to claim 37, wherein defining said area in which to seek a step towards said destination comprises:

determining to which side of a preferred direction to search.

42. A computer program for performing the method according to claim 1.

43. A computer-readable medium storing the computer program of claim 42.

44. Apparatus configured to perform the method according to claim 1.

38. A method of simulating movement of an autonomous entity through an environment from a current location to an intended destination, 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 and,

if said preferred step is not feasible determining a compromise step, wherein determining a compromise step includes;

defining a neighbourhood;

scanning said neighbourhood for obstacles;

determining at least one condition relating to said obstacles and

defining an area in which to seek a step towards said destination in dependence upon said at least one condition.

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

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

means for providing a profile for said autonomous entity;

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

said determining means configured to determine a first dissatisfaction function for expressing a cost of taking a step comprising a sum of an inconvenience function for expressing a cost of deviating from a given direction and a frustration function for expressing a cost of deviating from a given speed;

means for determining a personal space around said autonomous entity;

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

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

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

means for providing a profile for said autonomous entity;

means for determining a preferred step cowards said intended destination based upon said profile and said provisional path;

means for determining a personal space around said autonomous entity;

means for determining whether said preferred step is feasible by considering whether obstructions infringe said personal space and, if said preferred step is not feasible, for determining a compromise step,

wherein said means for determining a compromise step includes;

means for defining a neighbourhood;

means for scanning said neighbourhood for obstacles;

means for determining at least one condition relating to said obstacles; and

means for defining an area in which to seek a step towards said destination in dependence upon said at least one condition.

47. 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;

an 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, wherein said processor is configured to determine a first dissatisfaction function for expressing a cost of taking a step comprising a sum of an inconvenience function for expressing a cost of deviating from a given direction and a frustration function for expressing a cost of deviating from a given speed;

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.

48. 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;

an 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 and, if said preferred step is not feasible, for determining a compromise step,

wherein said processor is configured define a neighbourhood, scan said neighbourhood for obstacles, determine at least one condition relating to said obstacles; and

define an area in which to seek a step towards said destination in dependence upon said at least one condition.