Movement of an autonomous entity through an environment

• US 7,389,210 B2
• Filed: 09/09/2003
• Issued: 06/17/2008
• Est. Priority Date: 09/09/2002
• Status: Expired due to Term

• Current Assignee: Bentley Systems (UK) Limited (Bentley Systems Incorporated)
• Original Assignee: The Maia Institute
• Inventors: Kagarlis, Marios
• Primary Examiner(s): JONES, HUGH M
• Application Number:
  US10/526,878
• Publication Number:
  US 20050261886A1
• Time in Patent Office: 1,743 Days
• Field of Search: 703/2
• 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 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, 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, 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; 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;

determining whether at least one compromise step is feasible;

choosing one of a plurality of compromise steps; and

recording said one of the plurality of compromise steps so as to allow movement of said autonomous entity to be determined.

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

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

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

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

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

8. A method according to claim 1, further comprising determining said inconvenience function for expressing a cost of deviating from a given direction.

9. A method according to claim 8, wherein said provisional path includes a 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.

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

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

12. A method according to claim 1, further comprising determining said frustration function.

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

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

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

minimising said first dissatisfaction function in respect of step length;

minimising said first dissatisfaction function in respect of step orientation;

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

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

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

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

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

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

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

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

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

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

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

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

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

25. A method according to claim 23, further comprising:

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

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

basing said profile on a set of measured attributes.

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

statistically assigning said profile.

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

29. 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 bearing from said current location to said intended destination.

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

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

32. A method according to claim 30, comprising:

providing information relating to velocity of said autonomous entity; and

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

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

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

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

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

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

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

determining a density of one type of obstacle.

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

establishing an angular range for a search.

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

determining to which side of a preferred direction to search.

39. 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; and

revising said model of said building structure in dependence upon movement of said at least one autonomous entity, wherein the simulating of the movement comprises;

providing a provisional path through said model of the building structure 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; and

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

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

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

if said preferred step is not feasible, determining a compromise step and recording the compromise step so as to allow movement of said autonomous entity to be determined, 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.

41. A computer program tangibly embodied on a computer-readable medium, the computer program comprising computer executable instructions for 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, 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; and

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

42. A computer-readable medium storing a computer program comprising computer executable instructions for 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, 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; and

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

43. Apparatus configured to perform 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, 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; and

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

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

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;

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.

46. 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 and 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;

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

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

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 and 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, for determining a personal space around said autonomous entity, and 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.