Method of controlling the position of at least part of an autonomously moveable device

This invention relates to a method of controlling the position of at least part of an autonomously moveable device, and to an autonomously moveable device. Many interesting developments are being made in the field of home dialogue devices and systems, so that, in the near future, it is expected that many households will be equipped with one or more such systems. A home dialogue system, equipped with camera, microphone and loudspeaker, allows speech-based interaction with a user and can interpret visual data. Such a device can be used for many practical applications such as downloading desired programs from an external source, managing emails, voice mails and the recording of television programs or music, monitoring and checking supplies, controlling domestic applications such as heating and lighting, etc. The dialog system might be realised as a dedicated device as described, for example, in DE 102 49 060 Al, constructed in such a way that a moveable 'head' can turn to face the user, giving the impression that the device is listening to the user. Equipped with such a head having a face with eyes, mouth and ears, the home dialogue system may even be capable to a certain extent of facial expression. Such a system, when fitted with suitable motors and joints, can be capable of moving from one location to another. A home dialogue system can be realised as a robot with the appearance of, for example, a household pet or a human. To make the interaction between the user and the home dialogue system appear as natural as possible, the device or robot should be able to make certain decisions on its own, in an autonomous manner, for example to return to its docking station to recharge batteries if these are running low, or to position itself in a region in which the quality of a wireless signal is sufficiently high to allow transmission or reception of data.

Major problem sources in a household environment are dramatically varying conditions and environments. For example, robots understanding speech perform

worse in a noisy environment or when too far away from the user, recognition of objects or faces requires stable light conditions, and a wireless signal required for communication with the robot may have different strengths in different places in the household. Furthermore, the signal load is considerably higher when streaming video than when transporting text data such as email, while a Bluetooth connection may require a certain proximity to a compatible device. In spite of all these difficulties, the robot must be able to fulfill any task set to it by the user.

Therefore, it is an object of the invention to provide a way of controlling the motion of an autonomous device while taking into consideration any factors that might influence the motion.

To this end, the present invention describes a method of controlling the position of at least part of an autonomously moveable device, which method comprises computing an influence function for each position-related influence of a plurality of position-related influences, combining the influence functions to obtain an influence function sum, and calculating a path of motion for a part of the autonomously moveable device from an initial position to a target position on the basis of the influence function sum.

A position-related influence can be any influence that has a direct or indirect effect on the position or motion of the autonomously moveable device, such as obstacles between the autonomously moveable device and a destination, or the strength of a WLAN signal at various locations, or the noise levels in different locations. Other position-related influences might be a predefined minimum or maximum distance from a docking station, light levels in various parts of a room, the position of an object that the autonomously moveable device is to fetch or the position to which it is to move, etc. Information about these position-related influences can be obtained by the autonomously moveable device by means of appropriate input channels. For example, information regarding noise levels can be obtained over an input channel associated with one or more microphones of the autonomously moveable device, and information about obstacles in the path of the autonomously moveable device could be stored in a memory, or could be deduced from analysis of images of the environment captured using one or more cameras

of the autonomously moveable device. Information pertaining to a target position for the device can be obtained, for example, by analysis of a spoken user command such as "Go into the kitchen".

An obvious advantage of the method according to the invention is that all position-related influences are taken into consideration when controlling the motion of the autonomously moveable device, so that an optimum path of motion can be computed. At any stage of the motion of the autonomously moveable device from its initial position to its target position, the device can always be optimally placed with respect to all of the influence functions. For example, the autonomously moveable device can circumnavigate all obstacles whilst maintaining 'eye contact' with the user and remaining at all times within a satisfactory WLAN range. None of the influence functions need be favoured at the expense of another.

A suitable autonomously moveable device comprises a number of input channels - such as a camera, microphone, database, etc. - for obtaining position-related influence data for a plurality of position-related influences, an influence function computation unit for computing an influence function for each position-related influence, and a combination unit for combining the influence functions to obtain an influence function sum. The autonomously moveable device also comprises a path calculation unit for calculating a path of motion for a part of the autonomously moveable device from an initial position to a target position on the basis of the influence function sum.

The dependent claims and the subsequent description disclose particularly advantageous embodiments and features of the invention.

Naturally, the autonomously moveable device can recompute the influence function sum, or total influence function, at any stage in its motion to the target position. For example, a new obstacle may appear in its path of motion, or the user may move about so that the autonomously moveable device must recalculate the relevant influence functions and therefore also the overall influence function, in order to take such factors into account. The 'initial position', therefore, is the current position at which the total influence function is calculated. The user might not give absolutely precise instructions regarding the

target position of the autonomously moveable device, rather, such commands might be phrased in a vague manner, such as "Follow me", when he moves into a different room. Therefore, in a particularly preferred embodiment of the invention, the autonomously moveable device can analyse the influence function sum to determine an optimal target position. In the example given, the autonomously moveable device might analyse the new conditions, once it arrives in the room into which the user has moved, to position itself in a region of satisfactory WLAN reception while, for example, remaining close enough to the user to be able to hear spoken commands. Similarly, if the robot is located next to a sound source (e.g. a TV or running water) and speech recognition capabilities are required because a dialogue with a user is ongoing, or because the user has requested to be informed about an incoming email, the robot can detect a gradient in the noise level, determine a position at which the conditions are better, and move to this position. In this way, the robot can position itself in a location that is optimal for its estimated performance requirements. An autonomously moveable device in the form of a robot can, as described above, comprise different 'body parts' such as head, trunk, legs, arms, etc. Particularly if the robot is to appear lifelike, these body parts can to some extent be movable independently of each other. For example, the robot itself may remain in one position while, for example, the head rotates as required. In a preferred embodiment of the invention, a target position and/or a path of motion is calculated for each part of a number of independently moveable parts of the autonomously moveable device. In this way, a path of motion can be calculated for the body of the autonomously moveable device, while a separate path of motion is calculated for the head. For example, while the entire robot follows one path of motion to arrive at a target position, the head of the robot might swivel or turn to maintain eye contact with the user, thereby following a different path of motion.

The different influence functions which are considered by the autonomously moveable device in moving from an initial position to a target position might have different levels of importance. For example, any obstacles in the path of the autonomously moveable device have of necessity a high level of importance, since it is

generally undesirable that the device bump into an object or fall down a step. If there is no ongoing spoken interaction between the user and the autonomously moveable device, the noise level or proximity to the user is less important than during a spoken interaction. Functions of comparatively high importance or comparatively low importance can be weighted accordingly, so that the more important function is accorded more influence than the function of less importance. Therefore, in a preferred embodiment of the invention, combining the influence functions comprises weighting the influence functions according to a set of weighting factors to give a weighted influence function sum. The value of the weighting factor for an influence function can be chosen according to the importance of that function. The contribution of a particularly important influence function can be doubled by assigning it a weighting factor of '2', for example, while the weighting factor for a fairly unimportant function can be set to '0.5'. Naturally, the weighting factors can all be set to T if all functions are deemed to be of equal importance. The relative importance of the various influence functions can vary according to the current situation. For example, if the user commands the autonomously moveable device to go ahead into another room, while the user himself remains where he is, the autonomously moveable device can conclude that maintaining eye contact is not important for the duration of the motion. In a preferred embodiment of the invention, the set of weighting factors used to weight the influence function sum is compiled according to a current situation. For example, a corresponding influence function can be essentially factored out of the influence function sum by assigning it an appropriately low weighting factor. On the other hand, an influence function might be accorded more importance and therefore needs a higher weighting factor. For example, if the autonomously moveable device is to move from an initial position to a target position while also downloading information from an external source, for example the internet, and this download operation should under no circumstances be interrupted, the weighting factor for the corresponding influence function might be increased accordingly for this situation.

It may also be that some position-related influences are more relevant at the target position, while others play a role in determining the path of motion to that

target position. For example, the autonomously moveable device may choose a target position on the basis of WLAN signal strength and distance from a docking station. While moving to the target position, however, the autonomously moveable device may be in a spoken dialogue with the user, so that noise levels and, of course, obstacles must be taken into consideration when calculating the path of motion, but actual eye-contact may be of less relevance, particularly if the user is walking ahead of the autonomously moveable device. Therefore, in a preferred embodiment of the invention, the target position and the path of motion are calculated using different influence function sums, or weighted in different ways, using only the influence functions that are in each case relevant. In this way, the target position can quickly be determined, and the path leading to this target position can be calculated with less effort.

An influence function can be visualised as a three-dimensional graph or grid with 'peaks' and 'troughs' corresponding to positive and negative situations. For example, an influence function for the obstacles in a room can be visualised as a three- dimensional grid with a number of troughs associated with a corresponding number of obstacles, and peaks corresponding to obstacle-free regions in the room. The influence function for WLAN reception can have a number of peaks associated with regions in the room in which reception is good, and troughs associated with regions in the room where reception is poor. Naturally, a high weighting factor for an influence function will make the peaks of that function higher, and the troughs deeper. The influence function sum can therefore also be visualised as a three-dimensional grid with peaks and troughs obtained from summing the individual influence functions together.

To determine the target position and/or the path of motion, the autonomously moveable device can search for a global maximum of the influence function sum using well-known algorithms such as, for example, the technique of simulated annealing. The autonomously moveable device could then move into the direction of the global maximum. However, this may result in situations where the robot tries to go through regions of low value, so that this technique may be better suited to situations in which the troughs of an influence function do not pose an actual safety hazard for the robot or the user, for example troughs in an obstacle influence function.

Another way for the autonomously moveable device to determine an optimal path of motion to its target position is to compile the path of motion from incremental path segments following the contours of the influence function sum, where each path segment is chosen on the basis of steepest ascent, or gradient. In other words, the path follows the intermediate points of the gradient ascent algorithm towards the point of convergence, i.e. the target position. This process of always choosing the path segment of steepest gradient ultimately delivers an increasing path from the initial position to the target position, taking into account all of the influence functions. Although this technique is somewhat cost-intensive, advancing along the gradient direction ultimately yields an increasing path between the initial position and the target position, or steady improvement in the total value function, avoiding hazardous regions such as obstacles. This technique, known as the gradient ascent method, will be known to a person skilled in the art.

Since the gradient ascent method evaluates local maxima, it may not always yield satisfactory results, particularly in such a case where the current position of the autonomously moveable device is located on a local maximum, so that it may elect to remain where it is, failing to recognise the existence of a better target position (a global maximum). On the other hand, the technique of simulated annealing is suitable for determination of the best target position since it focuses on a global maximum (i.e. the target point), and may deliver a suitable path of motion to get there, for example by application of a path-planning module, which will be known to a person skilled in the art. An example is Dijkstra's algorithmen which finds the shortest path in a weighted graph which for this instance would be generated by sampling the influence function sum on a dense grid, connecting the neighbouring nodes and removing the hazardous areas. Naturally, the autonomously moveable device can combine different techniques in order to perform the calculations in a cost-efficient manner. In a particularly preferred embodiment of the invention, the target point can be quickly determined using a technique such as simulated annealing or gradient ascent, whereas the path of motion to that target position can be calculated using a known path planning technique. The autonomously moveable device might base its decision on the requirements of the

current situation.

The method according to the invention as described above can also be applied to determine if it is at all advantageous for the autonomously moveable device to move from its current position to a target position. In some situations, the total influence function may not exhibit any pronounced peaks. For example, if the autonomously moveable device is already close enough to its docking station and in a region of good reception, and can hear the user sufficiently well, the autonomously moveable device can decide to remain where it is, since its current position is essentially no worse than any other position. In a preferred embodiment of the invention, therefore, the path of motion is only followed by the autonomously moveable device if a predefined threshold value on an 'improvement' between the initial position and the target position is exceeded, otherwise the autonomously moveable device will remain in its current position. An improvement can be given, for example, by a satisfactory difference between the absolute function values of the initial and target positions. If this difference is less than a predefined threshold value, the autonomously moveable device can conclude that conditions at the target position are not significantly better than at its initial position. Evidently, this would apply only in a situation where the autonomously moveable device is given a directive without a specific target position, it being left to the autonomously moveable device to decide whether or not it should move. As mentioned above, the techniques for determining the target position and the path of motion can be carried out using known algorithms. These can run as software on one or more processors of the autonomously moveable device. The other processing steps, such as processing of data provided by the input channels and computation of the influence functions and the influence function sum can also be performed using software modules running on one or more processors of the autonomously moveable device. Results of the target position and/or path calculation can be converted into suitable commands by a drive unit of a device controller, for example, to drive motors of the autonomously moveable device in order to cause the autonomously moveable device to complete the desired movements. A suitable software package comprising one or more such modules and configurable for a number of

different types of autonomously moveable device might be loaded into the device, so that updates of the software can be easily be obtained.

Other objects and features of the present invention will become apparent from the following detailed descriptions considered in conjunction with the accompanying drawings. It is to be understood, however, that the drawings are designed solely for the purposes of illustration and not as a definition of the limits of the invention.

Fig. 1 shows an autonomously moveable device according to an embo diment o f the invention;

Fig. 2a shows a first influence function;

Fig. 2b shows a second influence function;

Fig. 2c shows a third influence function;

Fig. 2d shows a fourth influence function; Fig. 2e shows a combined influence function;

Fig. 3 shows a path of motion from an initial position to a target position, superimposed on the combined influence function;

Fig. 4a shows an autonomously moveable device according to an embodiment of the invention; Fig. 4b shows a block diagram of an autonomously moveable device according to an embodiment of the invention.

In the drawings, like numbers refer to like objects throughout. Fig. 1 shows a very simple example of an environment, in this case a room, in which an autonomously moveable device 1 can move about. Obviously, more complicated environments would be realistic, but a simple room 14 will be described for the sake of convenience. Here, the autonomously moveable device 1 has entered the room 14 at the request of the user and is currently positioned at an initial position P ₁ . Various objects are positioned in the room 14, such as a TV 10, a potted plant 11, and

an armchair 12. A docking station 13 is positioned in one corner of the room 14. Let us assume that a user, not shown in the diagram, has commanded the autonomously moveable device 1 to go to a target position P _t in the room 14.

Figs. 2a - 2d show, in the form of 'three-dimensional' graphs, a number of influence functions /i, /2, /?, /4 for the room shown in Fig. 1. In Fig. 2a, the influence function/i describing the distance from the autonomously moveable device to its docking station is plotted, showing a 'peak' at the point corresponding to the docking station, while all other points in the graph are lower. In other words, proximity to the docking station is interpreted to be positive, and a large separation is interpreted as negative.

Similarly, in Fig. 2b, the influence function/2 describing the target position of the autonomously moveable device is plotted, showing a 'peak' at the point corresponding to the desired position, while all other points in the graph are lower.

The regions corresponding to good and poor WLAN signal strength are shown in the influence function/3 in Fig. 2c. Here, troughs in the function correspond to areas of poor reception owing to external influences, while peaks indicate adequate signal strength.

Fig. 2d charts the positions of obstacles that the autonomously moveable device must circumnavigate. A trough in the obstacle influence function/i indicates an obstacle, while regions of higher elevation indicate areas through which the autonomously moveable device can navigate without impediment.

The influence functions /1, /2,/3,/i are combined to give an influence function sum F, as shown in Fig. 2e, with the initial position P ₁ and target position P _t as indicated. It now remains for the autonomously moveable device to determine how it should move from the initial position P ₁ to the target position P _t , as will be explained below.

If 5ϊ * is the k-dimensional vector space with k degrees of freedom for the motion of the autonomously moveable device or parts of the autonomously moveable device, and x is a vector in this space, the functions for each influence on the value of a position x e % ^k can be expressed thus:

where f _t (x) in equation (1) can be positive or negative, i.e. a noisy region would result in a negative value. The total influence function sumF(x) of a position x is a weighted sum over all influence functions, and can be expressed as F(x) = ∑w,f, (x) = ^y ff(x) (2) i where the weight vector w = (W ₁ ,..., W _n f in equation (2) is compiled according to the current requirements, such as the current task or operating mode of the robot. The gradient AF\x°) at the current position x° yields the direction of steepest ascent with respect to the value. The gradient at the current position is then given by the weighted sum of the individual gradients of the influence functions:

δF(x°) = ∑w Af _t (x ⁰ ) (3)

Using this approach, the path from the initial position P ₁ can be incrementally compiled by determining the gradient at the current position according to equation (3), determining the end point of the path segment by moving along the ascent direction by a predefined step size, using that end point as the updated current position, and repeating the process until no significant improvement is observed. The end of the last segment corresponds to the target position P _t . The resulting 'path' along the contours of the influence function sum can be mapped to a two-dimensional path in the room, and then used to provide motion coordinates or commands to enable the autonomously moveable device to physically follow the path. This can be done as the path is being calculated, i.e. the autonomously moveable device can begin to move more or less right away, even before the path has been calculated to its end point, or the autonomously moveable device can wait until the path has been calculated in its entirety before starting to move. As described above, the autonomously moveable device can combine the influence functions as required in order to determine the target position or path of motion. For instance, one influence function sum F can be obtained for the determination of the target point, while a different influence function sum is used when calculating the

path of motion to the target point. Alternatively, all influence functions might be combined to give an influence function sum F, and a weighted influence function sum can be obtained by weighting one or more of the influence functions according to the requirements of the current situation. Fig. 3 shows the combined influence function sum F with initial position

P ₁ and target position P _t , and the incrementally calculated path of motion M superimposed on the contour of the influence function sum F. This is the optimal path for the autonomously moveable device to follow in order to arrive at the target position P _t . In this example, the autonomously moveable device will move between the television on the wall and the other two obstacles in the middle of the room, in a path that ensures optimal WLAN signal reception during the motion. The influence functions were assumed to remain constant, but naturally this need not always be the case. For example, another person might move about in the room, thus presenting another 'obstacle'. In such a situation, the influence function sum is simply recalculated and the path of motion for the autonomously moveable device is adjusted accordingly.

Fig. 4a shows the autonomously moveable device 1 in more detail. Here, the autonomously moveable device 1 can move about by means of rollers 23 acting as 'feet', and has an independently moveable head 20 attached to a trunk 21. The autonomously moveable device 1 is furthermore equipped with cameras 24 and microphones 25 acting as 'eyes' and 'ears' respectively.

Fig. 4b is a block diagram illustrating the units and modules required for the method according to the invention. Image data are collected by the camera 24, and audio data are collected by the microphone 25. In the diagram, only one of each are shown, but it will be clear that an autonomously moveable device 1 can avail of any number of cameras or microphones. A wireless receiver and transmitter unit 26 delivers information about the signal strength of a WLAN signal. Using this information, the autonomously moveable device 1 can plot a 'map' of signal strength and can use this as an influence function. Similarly, a memory 27 provides information about the locations of obstacles in one or more rooms, or the autonomously moveable device 1 can learn about obstacles in its environment by analysing images generated by the camera 24.

Signals from the input channels 24, 25, 26, 27 are forwarded to an influence function computation unit 40, in which the corresponding influence functions are computed. These are forwarded as an appropriate signal 28 to a combination unit 41, where the influence functions are combined to give an overall influence function F, which may be weighted in a weighting unit 43 as necessary. The decision to weight one or more influence functions can be made with the aid of an information signal 45 pertaining to the current situation. This information signal 45 might be compiled on the basis of a spoken command of the user, or can be determined by the autonomously moveable device 1 itself. The influence function sum F is forwarded to a path calculation unit 42, which applies an appropriate algorithm to determine a target position P _t and/or the path of motion M from the initial position of the autonomously moveable device 1 to that target position P _t . Using spatial coordinates obtained from this information, a drive unit 44 can generate suitable device control commands to cause the autonomously moveable device 1 to move in the specified direction, or to move independent parts of the autonomously moveable device separately.

Although the present invention has been disclosed in the form of preferred embodiments and variations thereon, it will be understood that numerous additional modifications and variations could be made thereto without departing from the scope of the invention.