Method and apparatus for identifying or controlling travel to a rendezvous

• US 6,324,476 B1
• Filed: 12/20/1994
• Issued: 11/27/2001
• Est. Priority Date: 11/20/1987
• Status: Expired due to Fees

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: Philips Electronicsnorth America Corporation (Koninklijke Philips N.V.)
• Inventors: Trovato, Karen I.
• Primary Examiner(s): Elmore, Reba I.
• Application Number:
  US08/360,186
• Time in Patent Office: 2,534 Days
• Field of Search: 364/148, 364/424.02, 364/47.2, 364/444, 364/461, 364/167.01, 364/436, 364/437, 364/438, 395/919, 395/905, 395/920, 395/80, 395/85, 395/88, 395/90, 395/89, 701/23-28, 701/201, 701/202, 700/28, 700/18, 700/177, 700/178, 700/245, 700/250, 700/253, 700/255, 700/254, 700/87, 700/56-66, 702/201, 702/202, 702/117, 702/118, 702/119, 706/919, 706/905, 706/920
• US Class Current: 701/301
• CPC Class Codes: B25J 9/1666 Avoiding collision or forbidden zones
• CPC Class Codes: B63B 49/00 Arrangements of nautical instruments or navigational aids nautical measuring instruments G01C; radio navigation, analogous arrangements using other waves G01S
• CPC Class Codes: B63G 8/14 Control of attitude or depth of torpedoes F42B19/00
• CPC Class Codes: B63H 25/04 automatic, e.g. reacting to compass
• CPC Class Codes: G05B 19/4061 Avoiding collision or forbidden zones
• CPC Class Codes: G05B 2219/35415 3-D three dimension, space input, spaceball
• CPC Class Codes: G05B 2219/40443 Conditional and iterative planning
• CPC Class Codes: G05B 2219/40448 Preprocess nodes with arm configurations, c-space and planning by connecting nodes
• CPC Class Codes: G05B 2219/40465 Criteria is lowest cost function, minimum work path
• CPC Class Codes: G05B 2219/40471 Using gradient method
• CPC Class Codes: G05B 2219/40476 Collision, planning for collision free path
• CPC Class Codes: G05B 2219/45131 Turret punch press
• CPC Class Codes: G05B 2219/49143 Obstacle, collision avoiding control, move so that no collision occurs
• CPC Class Codes: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria
• CPC Class Codes: G05D 1/0225 involving docking at a fixed facility, e.g. base station or loading bay parking aids B62D15/027
• CPC Class Codes: G05D 1/0242 using non-visible light signals, e.g. IR or UV signals
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0255 using acoustic signals, e.g. ultra-sonic singals sonar systems designed for anti-collision purposes G01S15/93
• CPC Class Codes: G05D 1/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00
• CPC Class Codes: G05D 1/028 using a RF signal
• CPC Class Codes: G06F 30/18 : Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G06Q 10/047 : Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G08G 1/161 : Decentralised systems, e.g. inter-vehicle communication
• CPC Class Codes: G08G 9/00 : Traffic control systems for craft where the kind of craft is irrelevant or unspecified

Abstract

Paths are planned for one or more actors, through at least two dimensions of time or space, to identify rendezvous locations meeting a global criterion. At least two scenarios are defined, including at least one for each actor, and a configuration space is created for each of these scenarios. A scenario includes identification of the actor, a source direction for planning, a set of states identifying the source or obstacle locations, and the respective cost metrics for each possible transition between a configuration state in the corresponding configuration space, and its neighbors. Cost waves are propagated in each configuration space, to generate a cost-to-source for each state. A Boolean evaluation is then made of configuration states, according to a global criterion, to identify all possible rendezvous states. Finally, the actors are controlled to travel to that rendezvous chosen according to optimization criteria, or the candidate rendezvous states are displayed for further evaluation or use.

Claims

1. A computer method of identifying at least one rendezvous state that satisfies criteria for at least one actor, the method comprising executing the following operations in a data processing device:

defining a first scenario for travel to achieve a rendezvous condition;

embodying said first scenario in at least one computer readable medium;

defining at least one second scenario different from said first scenario for travel to achieve said rendezvous condition,

embodying said at least one second scenario in at least one computer medium,

forming at least respective first and second configuration space data structures based on said scenarios, said respective configuration space data structures being referred to herein as “

configuration spaces” and

having at least one task state in common,

embodying said respective configuration spaces in at least one computer readable medium,

propagating cost waves from a respective source for each configuration space, to determine costs for each configuration state corresponding to a said task state in common,

embodying said costs in at least one computer readable medium,

forming at least one Boolean expression defining at least one global criterion,

embodying said Boolean expression in at least one computer readable median,

for each said task state in common, evaluating costs of the corresponding configurations, according to said Boolean expression, to identify candidate rendezvous states,

outputting from the data processing device an identification of said candidate rendezvous states.

2. The method as claimed in claim 1, wherein the respective source for one of said configuration spaces is a starting state for said actor, and the respective source for another of said configuration spaces is a goal state.

3. The method as claimed in claim 1, including stopping the propagation of waves when the global criterion cannot be true.

4. The method of claim 1 further comprising the step of controlling an object to move in accordance with the candidate rendezvous states.

5. The method as claimed in claim 1, wherein said at least one actor includes a first actor and a different actor, said first scenario is defined for said first actor, said second scenario is defined for said different actor, and said rendezvous condition is simultaneous presence of said first and different actors at a same task state.

6. The method of claim 5, wherein

propagating cost waves includes applying a respective criterion for each configuration space; and

said Boolean expression expresses a combination of all the respective criteria.

7. The method as claimed in claim 1, including the step of defining a third scenario for travel from said rendezvous condition to a goal, wherein the respective source for one of said configuration spaces is a starting state for said first actor, and the respective source for another of said configuration spaces is said goal.

8. The method as claimed in claim 7, wherein said goal is different from said starting state.

9. The method as claimed in claim 7, wherein said propagating step comprises:

a) propagating waves emanating from said starting state,

b) computing metrics by measuring transitions in reverse, and

c) leaving direction arrows pointing toward the start.

10. The method of claim 1 wherein the identification is user-discernable.

11. The method of claim 10 wherein the object is a displayed object.

12. The apparatus of claim 11 wherein the object is a displayed object.

13. Data processing apparatus for identifying at least one rendezvous state which satisfies criteria for at least one actor, comprising:

a. at least one processor arranged to perform the following operations

i. defining a first scenario, and at least one second scenario different from said first scenario, for travel to achieve a rendezvous condition,

ii. forming respective configuration space data structures based on said scenarios, said data structures being referred to herein as respective configuration spaces, the respective configuration spaces having at least one task state in common,

iii. propagating cost waves from a respective source for each respective configuration space, to determine costs of corresponding configuration states for each said task state in common,

iv. forming at least one Boolean expression defining at least one global criterion,

v. evaluating, for each said task state in common, said Boolean expression to identify candidate rendezvous states,

b. at least one medium readable by said processor and embodying said first and at least one second scenarios, said respective configuration spaces, said costs, and said expression; and

c. output means connected to the computer for providing an identification of said candidate rendezvous states.

14. The apparatus as claimed in claim 13, wherein the respective source for one of said configuration spaces is a starting state for said actor, and the respective source for another of said configuration spaces is a goal state.

15. The apparatus as claimed in claim 13, wherein the processor is further arranged for stopping the propagation of waves when the global criterion cannot be true.

16. The apparatus of claim 13 further wherein the processor is further arranged effect movement of an object in accordance with the candidate rendezvous states.

17. The apparatus as claimed in claim 13, wherein said at least one actor includes a first actor and a different actor, said first scenario is defined for said first actor, said second scenario is defined for said different actor, and said rendezvous condition is simultaneous presence of said first and different actors at a same configuration state.

18. The apparatus of claim 17, wherein

propagating cost waves includes applying a respective criterion for each configuration space; and

said Boolean expression expresses a combination of all the respective criteria.

19. The apparatus as claimed in claim 17, wherein said processor is further arranged for defining a third scenario for travel from said rendezvous condition to a goal, wherein the respective source for one of said configuration spaces is a starting state for said first actor, and the respective source for another of said configuration spaces is said goal.

20. The apparatus as claimed in claim 19, wherein said goal is different from said starting state.

21. The apparatus as claimed in claim 19, wherein propagating comprises:

a) propagating waves emanating from said starting state,

b) computing metrics by measuring transitions in reverse, and

c) leaving direction arrows pointing toward the start.

22. Data processing apparatus for controlling travel of at least first and second actors to a rendezvous, comprising:

a. at least one processor arranged to perform the following operations

i. defining a first scenario associated with a first one of the actors, and at least one second scenario associated with at least one other of the actors and different from said first scenario, for travel to achieve a rendezvous condition,

ii. forming respective configuration space data structures based on said scenarios, said respective data structures being referred to herein as respective configuration spaces, said respective configuration spaces having at least one task state in common,

iii. propagating cost waves from a respective source for each configuration space, to determine costs for configuration states corresponding to each said task state in common,

iv. forming at least one Boolean expression defining at least one global criterion,

v. evaluating said Boolean expression, for each configuration state corresponding to a rendezvous task state in common, to identify candidate rendezvous states,

vi. selecting one of said candidate rendezvous states,

vii. determining a respective optimum path for each of said actors to the selected rendezvous state, based on said costs, and

b. at least one medium readable by said processor and embodying said scenarios, said respective configuration spaces, said costs and said Boolean expression; and

c. output means connected to the processor for providing respective travel control signals to said actors to follow the respective optimum paths.

23. The apparatus as claimed in claim 22, wherein the respective source for one of said configuration spaces is a starting state, and the respective source for another of said configuration spaces is a goal state.

24. The apparatus of claim 22 wherein the one of said actors is a displayed actor.

25. The apparatus of claim 22, wherein

propagating cost waves includes applying a respective criterion for each configuration space; and

said Boolean expression expresses a combination of all the respective criteria.

26. The apparatus as claimed in claim 22, wherein said first scenario is defined for the first actor, said second scenario is defined for the second actor, and said rendezvous condition is simultaneous presence of said first and second actors at a same configuration state.

27. The apparatus as claimed in claim 26, wherein

the processor is further arranged for defining a third scenario for travel from said rendezvous condition to a goal,

the respective source for one of said configuration spaces is a starting state for said first actor, and

the respective source for another of said configuration spaces is said goal, and

said output means further provides travel control signals to one of said actors for travel from said rendezvous condition to said goal.

28. The apparatus of claim 22 wherein the output means comprises at least one controller for controlling movement of one of said actors.

29. The apparatus as claimed in claim 22, wherein one of said actors is a robot, and said controller controls movement of said robot.