KR101157496B1 - Method for mobile device's movement using utility function and apparatus for the same - Google Patents

Abstract

Provided are a method of moving a moving object using a utility function. The method detects another moving object on the moving path of the moving object, exchanges first information, which is information of the moving object, and second information, which is information of the other moving object, with the other moving object, and the first information and the second information. The first utility function, which is a reference for determining whether to move the moving object, is determined, and the first utility function is larger by comparing the first utility function with the second utility function of the other moving object. It includes moving along.

Description

METHOD FOR MOBILE DEVICE'S MOVEMENT USING UTILITY FUNCTION AND APPARATUS FOR THE SAME}

The present invention relates to a method for moving a moving object, and more particularly, to a method for determining and moving a moving object through a negotiation with another moving object using a utility function indicating a moving priority of the moving object, and an apparatus for supporting the moving object. will be.

Recently, the wireless network technology between objects has been used to predict collisions and prevent collisions as the possibility of collision between objects having mobility on the objects (hereinafter referred to as 'mobile device') increases. . Conventionally, in preventing collision between moving objects, a sensor network technology for detecting a moving object around a sensor and preventing a collision with an object has been applied thereto. In addition, in collision avoidance between vehicles, a method of utilizing current communication with satellite communication-based current position information such as a global positioning system (GPS) and a current speed using wireless communication. For example, the above method is used to predict the collision distance and time by transmitting location and speed information of each vehicle to another vehicle at an intersection. However, a method of detecting another moving object using a sensor and preventing a collision causes a problem in that a small moving cost occurs because the detection range of the sensor is narrow.

In the past, the basis for determining whether to move a moving object was a priority assigned to each moving object. This may cause a problem in that when a moving object that has already moved a certain distance detects another moving object having a higher priority, it must retreat regardless of the existing moving distance. Therefore, it is necessary to determine whether to move using the new criteria of moving decision, including priority, existing distance of travel and possibility of collision risk.

The present invention provides a method for determining whether to move a moving object and preventing collision between moving objects using a utility function and an apparatus supporting the same.

In one aspect, a method of moving a moving object using a utility function is provided. The method detects another moving object on the moving path of the moving object, exchanges first information, which is information of the moving object, and second information, which is information of the other moving object, with the other moving object, and the first information and the second information. The first utility function, which is a reference for determining whether to move the moving object, is determined, and the first utility function is larger by comparing the first utility function with the second utility function of the other moving object. It includes moving along.

The first information may include an existing utility function including a priority of the moving object, a speed according to the time of the moving object, a position according to the time of the moving object, and a moving cost of the moving object and a collision cost of the moving object.

The second information may include an existing utility function including a priority of the other moving object, a speed according to the time of the other moving object, a position according to the time of the other moving object, a moving cost of the other moving object, and a collision cost of the other moving object. It may include.

The first utility function may be the following equation.

Where u _i (t) is the first utility function, w _i (t) is the priority of the moving object, x _i (t) is the position according to the time of the moving object, and v _i (t) is the moving object The velocity over time, c _i (t) is the cost that the mobile consumes over time, c _{i, mobility} (t) is the travel cost over time of the mobile, c _{i, collision} (t) is the The collision cost according to the time of the moving object, C _mobility is the moving unit cost constant of the moving object, C _collision is the collision cost constant of the moving object, d _{i, j} (t) is the distance between the moving object and the other moving object, x _j ( t) is the position according to the time of the other movable body.

Detecting the other moving object periodically transmits a radio signal; and

The method may include receiving an acknowledgment signal in response to the wireless signal.

The first information and the second information may be exchanged through packet transmission and reception.

In another aspect, a moving object is provided that determines whether to move using a utility function. The moving body includes a signal transmitting and receiving unit for transmitting and receiving a signal, a processor functionally connected to the signal transmitting and receiving unit, and a driving unit for moving the moving object according to the instruction of the processor. The signal transceiving unit transmits first information, which is information of the mobile body, to another mobile body and receives second information, which is information of the other mobile body, and the processor moves the mobile body based on the first information and the second information. A first utility function as a reference for determining whether to determine whether to determine, and comparing the first utility function and the second utility function of the other moving object is characterized in that the moving object is moved if the first utility function is larger.

The first information may include an existing utility function including a priority of the moving object, a speed according to the time of the moving object, a position according to the time of the moving object, and a moving cost of the moving object and a collision cost of the moving object.

The second information may include an existing utility function including a priority of the other moving object, a speed according to the time of the other moving object, a position according to the time of the other moving object, a moving cost of the other moving object, and a collision cost of the other moving object. It may include.

The first utility function may be the following equation.

Where ui (t) is the first utility function, wi (t) is the priority of the moving object, x _i (t) is the position of the moving object over time, and v _i (t) is the moving object's position. Velocity over time, c _i (t) is the cost that the vehicle consumes over time, c _{i, mobility} (t) is the movement cost over time of the vehicle, c _{i, collision} (t) is the The collision cost according to time, C _mobility is the moving unit cost constant of the moving object, C _collision is the collision cost constant of the moving object, d _{i, j} (t) is the distance between the moving object and the other moving object, x _j (t) Is the position according to the time of the other moving object.

The present invention anticipates a collision through the transfer of information using a wireless network of the utility function between moving bodies, prevents collision of each vehicle by minimizing movement, and minimizes the movement cost. In addition, the bottleneck of each moving body can be eliminated, and the congestion cost of the whole system can be reduced.

1 illustrates an example of a moving object to which an embodiment of the present invention can be applied.
2 is a view showing an example of narrow path entry of the moving object shown in the embodiment of the present invention.
3 is a diagram illustrating an example of collision between moving bodies that may occur in an embodiment of the present invention.
4 is a view showing an example of a path movement mechanism of the moving body according to an embodiment of the present invention.
5 is a view showing another example of the path movement mechanism of the moving body according to an embodiment of the present invention.
6 is a flowchart illustrating the operation of a moving object according to an embodiment of the present invention.
7 is a block diagram showing the format of a packet used by a mobile according to an embodiment of the present invention.
8 is a view showing a collision avoidance system between moving bodies according to another embodiment of the present invention.
9 is a view showing a moving body according to an embodiment of the present invention.

The moving object referred to below refers to an object that an object can freely carry, and refers to all objects in the human body, including a vehicle, aviation, marine and human. The moving object includes a device capable of wireless communication as well as an object detection sensor for preventing collision, and through this, the moving object can perform a function of exchanging information with other moving objects by wire or wirelessly.

The type of wireless communication is not limited to a specific type and includes all wireless communication, a direct link, and an ad hoc network via a base station or an access point (AP).

1 illustrates an example of a moving object to which an embodiment of the present invention can be applied.

Referring to FIG. 1, there is a narrow path between intersections I _a and I _b , and a wide path between intersections I _c and I _d . The moving object i (11) existing at the intersection I _a has the intersection I _b , and the moving object j 12 existing at the intersection I _b has the intersection I _a as its destination. The moving body i 11 and the moving body j 12 can return to a wide path via I _c , I _d . However, it is assumed that a narrow path that is fast and relatively low in cost is selected as the moving path. In this situation, when all the moving objects enter a narrow path, one of the two must yield the moving path.

2 is a view showing an example of narrow path entry of the moving object shown in the embodiment of the present invention.

Referring to FIG. 2, the mobile bodies i, i-1, and j all have a wireless communication function, and a communication radius capable of wireless communication is R. FIG. Therefore, each moving object can detect the presence of other moving objects entering the communication radius R, and can perform wireless communication when necessary.

The moving body i 11 and i-1 13 are moving from the intersection I _a , and the moving body i-1 13 follows the moving body i 11. The moving object j 12 is moving from the intersection I _b to I _a . A collision that may occur when entering a path as shown in FIG. 2 is shown in FIG. 3.

In the case of the sub-view (a) of FIG. 3, the collision between the moving bodies moving in the same direction is illustrated. This case corresponds to a case in which the moving object i-1 13, which is following after the rapid deceleration of the moving object i 11 that has entered the narrow path, may occur unexpectedly. In the case of the sub-drawing (b), it is a figure which shows the collision between moving bodies moving to a different direction. This case corresponds to a case where a collision occurs because the moving object i (11) and the moving object j (12) entering from the opposite side do not anticipate a collision with each other.

 In order to prevent a collision that may occur as described above, the mobile object provided in the embodiment of the present invention includes a detection system using a wireless network, which will be described in more detail below.

4 is a view showing an example of a path movement mechanism of the moving body according to an embodiment of the present invention. In the figure, the horizontal axis indicates time t and the vertical axis indicates the position of each moving object. The lowermost end of the vertical axis indicates the starting point of the moving object i, and the uppermost end of the vertical axis indicates the starting point of the moving object j. Mobile object i has a higher priority than mobile object j having a priority of 1 and a priority of 2. The sum of the y-axis components of the graph corresponding to each moving object is the total distance traveled by the moving object through the path.

The auxiliary view (a) is an example of a moving mechanism for preventing collision in the case of a moving object having an object detecting object detecting sensor. The moving body i first enters the path at time t _{0, i} and then the moving body j enters the path at time t _{0, j} . At t ₁ , the two moving bodies respectively enter the moving object sensing radius r with respect to the other moving bodies, thus detecting the other party and stopping entering. The interval t ₁ to t ₂ performs negotiation between each mobile to continuously enter the negotiation period. In this step, since the moving object i has a higher priority than the moving object j, the moving body i is determined to enter the traveling direction. At t ₃ , the moving object i exits the path and the moving object j enters the path again to move the path.

The sub-view (b) is an example showing a moving mechanism for collision prevention in the case of a mobile object using a wireless network. When using a wireless network, since the moving object sensing radius R is longer than the existing radius r (R = 3r in the drawing), the moving body i can detect the moving body j relatively quickly. Since the moving j is detected at T ₁ before entering the path, the moving j waits without entering the moving path. Therefore, it is possible to reduce the unnecessary travel distance caused by unnecessary entry and retraction as shown in the sub-view (a). In addition, since the other party can be quickly detected by using a wireless network, the time taken for both mobiles to pass through the path is relatively short and the risk of collision is reduced.

5 is a view showing an example of a path movement mechanism of the moving body according to an embodiment of the present invention. FIG. 5 illustrates the path moving mechanism through cooperation and competition between three moving objects by extending the moving path moving mechanism of FIG. 4. The solid line shown in FIG. 5 represents the actual movement path of each moving object over time, and the dotted line indicates the possible movement path when determining whether to move based only on the priority.

Referring to FIG. 5, the moving object i has the highest priority (1), and the moving object j entering in the direction opposite to the moving body i has the second priority (2). Moving body i-1 following in the same direction as moving body i has a third priority (3). The moving object i, which has the highest priority, first enters and moves the moving path, and the moving object i-1 moves while entering the moving path while maintaining a specific distance from the moving object i.

The moving body i passes through the path at t ₁ , and the moving body j and the moving body i-1 negotiate for moving the path. Referring to the dotted line in FIG. 5, when determining whether to move based on priority only, the moving object j enters the path and moves, and the moving object i-1 returns along the path. Thus, the moving object i-1 takes more time for all the moving objects to pass through the path, as well as the cost of the incoming path, the returning path and the moving path again. To solve the above problems, the moving object determines whether to move the path based on the utility function.

Referring to the solid line, the moving object i-1 has a lower priority than the moving object j at t ₁ , but may have a higher utility function than the moving object j by increasing the value according to the distance traveled until negotiation. Therefore, the moving object i-1 determines to move the path in preference to the moving object j and passes through the path at t ₂ . The moving object j moves and passes the path for t ₂ to t ₃ after the moving object i-1 passes through the path.

As described above, it can be seen that a more efficient and reasonable result occurs when the utility function is used as compared with simply determining the moving path of the moving object based on the priority. Hereinafter, the operation performed in moving the moving object will be described in more detail.

6 is a flowchart illustrating the operation of a moving object according to an embodiment of the present invention.

Referring to FIG. 6, the moving body i 610 entering the path senses other moving bodies (moving j 620 and moving body i-1 630) around (S611 and S612). The moving object i 610 exchanges information with other detected moving objects (S621 and S622). The mobile body 610 calculates a utility function (S630). The moving object i 610 determines whether to move based on the utility function (S640). The moving object may move / pass the path (S651), wait (S652), or move (S653) according to the movement decision.

The moving object i 610 enters a path and senses other moving objects 620 and 630 that are moving (S611 and S612). The moving object i 610 may detect other moving objects 620 and 630 through a sensor, or may use satellite communication. However, in the embodiment of the present invention, since the mobile uses a wireless network, each mobile periodically transmits a wireless signal, and the mobile receives the wireless signal and transmits an acknowledgment signal in response thereto. You can monitor the moving object through.

The mobile unit i 620 that detects another mobile unit exchanges its own information with each other (S621 and S622). The information exchanged with each other may include a priority of the moving object, a speed over time, a position over time, a moving cost constant, and a collision cost constant. The utility function may be included in the information if each moving object has a utility function value that is the basis for determining the priority of the movement path.

Information exchanged between mobiles can be implemented through a mechanism for transmitting and receiving packets on a wireless network. The format of the packet transmitted and received by the mobile may be shown in FIG.

7 is a block diagram showing the format of a packet used by a mobile according to an embodiment of the present invention.

Referring to FIG. 7, a packet 700 used by a mobile object includes a sender ID field 710, a location field 720, a transmission time field 730, a moving speed field 740, a receiver ID field 750, and a packet discard. A time field 760, and a utility function field 770.

The sender ID field 710 indicates the identifier information of the mobile body that transmits the packet. The location field 720 indicates the location over time of the mobile body transmitting the packet. The transmission time field 730 indicates the time at which the packet was transmitted. The movement speed field 740 indicates a movement speed according to the time of the mobile body that transmitted the packet. The receiver ID field 750 indicates identifier information of another mobile unit that will receive the packet. The packet discard time field 760 indicates a time point at which another mobile device discards the packet.

The utility function field 770 indicates a utility function that is a utility function of the moving object. However, when the utility function of the moving object is not yet determined, the value of the utility function field may have a null value. The utility function field 770 may further include a priority subfield indicating the priority of the moving object, a moving cost constant subfield, and a collision cost constant subfield.

Referring to FIG. 6 again, the mobile unit i 620, which has received the information of the other mobile unit, determines the utility function based on this (S630). The determination of the utility function may be determined as in Equations 1 and 2 below.

Where u _i (t) is the first utility function, w _i (t) is the priority of the moving object, x _i (t) is the position according to the time of the moving object, and v _i (t) is the moving object The velocity over time, c _i (t) is the cost that the mobile consumes over time, c _{i, mobility} (t) is the travel cost over time of the mobile, c _{i, collision} (t) is the The collision cost according to the time of the moving object, C _mobility is the moving unit cost constant of the moving object, C _collision is the collision cost constant of the moving object, d _{i, j} (t) is the distance between the moving object and the other moving object, x _j ( t) is the position according to the time of the other movable body.

After determining the utility function, the moving object i 610 determines whether to move with another moving object (S640). In determining whether to move, the utility function of the moving object i 610 and the utility function of the other moving objects 620 and 630 are determined to determine that its own utility function moves the path.

The moving object i 610 having the path moving phase priority moves / passes the path (S651). The mobile body i-1 620 moves along the rear body i 620 (S653), and the mobile body j 630 waits without entering the path (S652).

8 is a view showing a collision avoidance system between moving bodies according to another embodiment of the present invention.

There is a possibility that a collision may occur when a result of a process for determining whether to move a path based on a utility function between mobile bodies is wrong or when the utility function of the other party is unknown due to a malfunction of a wireless network. Therefore, in order to minimize the collision, an automatic direction control technique may be used in which the moving body automatically corrects the moving direction.

Referring to FIG. 8, when the moving object approaches the other moving object within a certain distance, the moving body automatically changes the moving direction. At this time, in order to prevent collision with other moving objects, change the direction to cross each other. For example, when the preceding moving body turns to the right of the two moving bodies in the same direction, the following moving body turns to the left. On the contrary, when one of the two moving objects facing each other turns to the right, the other moving object also turns to the right.

This automatic direction control technique can be applied to the moving method of the above-described moving object. If the moving object is unable to determine whether to move the route due to a defect or a delay of the wireless network system, the above-described automatic steering technique may be applied to prevent a collision. However, the distance between moving bodies to which the automatic direction control technology is applied may be limited to be smaller than the sensing radius of the moving object sensing system such as a wireless network.

9 is a view showing a moving body according to an embodiment of the present invention.

The mobile unit 900 according to the embodiment of the present invention includes a signal transceiver 910, a processor 920, and a driver 930.

The signal transmitting / receiving unit 910 transmits a signal and / or information indicating a presence of a mobile body and receives a signal and / or information of another mobile body. The signal transceiving unit may be provided in a type that supports this, according to a network system provided by the moving object.

The processor 920 may include an application-specific integrated circuit (ASIC), another chipset, a logic circuit, and / or a data processing device.

The processor 920 performs various procedures to implement the above-described embodiment of the present invention. It processes the information of the other moving object received from the signal transmission and reception unit 910, and calculates the utility function based on this. The utility function is used to determine whether to move the moving object, and to instruct the operation of the driving unit 930.

The driver 930 moves the moving body according to the instruction of the processor 920.

Although the system methods shown in the embodiments of the present invention described above are presented in a series of steps or blocks with reference to the drawings, the present invention is not limited to this order, and can achieve similar objects and effects as the present invention. It may be provided in a changed form within the scope. In addition, those skilled in the art of the present invention are not exclusive to the steps shown in the embodiments of the present invention, other steps are included or one or more steps are deleted without affecting the scope of the present invention. It can be understood.

The above-described embodiments include examples of various aspects. Although not all possible combinations may be described to represent the various aspects, one of ordinary skill in the art will recognize that other combinations are possible. It is therefore intended to include all other replacements, modifications and variations that fall within the claims of the present invention. The embodiments of the present invention described in detail above are merely illustrative of the technical idea of the present invention, and the technical idea of the present invention may not be limited by the above embodiments, and the protection scope of the present invention is It is specified by the claims of the present invention described below.

Claims (10)

In the moving method of the moving object using the utility function,
Detect other moving objects on the moving path of the moving object,
Exchanging first information, which is information of the mobile body, and second information, which is information of the other mobile body, with the other mobile body,
Based on the first information and the second information, determine a first utility function as a reference for determining whether to move the moving object, and
And comparing the first utility function with the second utility function of the other moving object and moving along the movement path when the first utility function is larger. The method of claim 1, wherein the first information is
Priority of the moving object;
Speed over time of the moving body;
Position of the moving object over time; And,
And an existing utility function of the moving object including the moving cost of the moving object and the collision cost of the moving object. The method of claim 2, wherein the second information,
Priority of the other moving objects;
Speed with time of the other moving object;
Position of the other moving object according to time; And,
And an existing utility function of the other vehicle including the movement cost of the other vehicle and the collision cost of the other vehicle. 4. The method of claim 3, wherein the first utility function is the following equation.

Where u _i (t) is the first utility function, w _i (t) is the priority of the moving object, x _i (t) is the position according to the time of the moving object, and v _i (t) is the moving object The velocity over time, c _i (t) is the cost that the mobile consumes over time, c _{i, mobility} (t) is the travel cost over time of the mobile, c _{i, collision} (t) is the The collision cost according to the time of the moving object, C _mobility is the moving unit cost constant of the moving object, C _collision is the collision cost constant of the moving object, d _{i, j} (t) is the distance between the moving object and the other moving object, x _j ( t) is the position according to the time of the other movable body. The method of claim 1, wherein the detecting of the other moving object comprises:
Periodically transmit wireless signals, and
Receiving an acknowledgment signal in response to the wireless signal. The method of claim 1, wherein the first information and the second information are exchanged through packet transmission and reception. In the mobile to determine whether to move using a utility function, the mobile,
Signal transmitting and receiving unit for transmitting and receiving a signal;
A processor functionally connected to the signal transceiver to determine whether the moving object is moved; And,
And a driving unit for moving the movable body according to the instruction of the processor.
The signal transceiver,
Transmitting first information that is information of the mobile body to another mobile body and receiving second information that is information of the other mobile body,
The processor determines a first utility function as a reference for determining whether to move the moving object based on the first information and the second information, and compares the first utility function with a second utility function of the other moving object. And the movable body moves if the first utility function is larger. The method of claim 7, wherein the first information is
Priority of the moving object;
Speed over time of the moving body;
Position of the moving object over time; And,
And an existing utility function of the moving object including the moving cost of the moving object and the collision cost of the moving object. The method of claim 8, wherein the second information,
Priority of the other moving objects;
Speed with time of the other moving object;
Position of the other moving object according to time; And,
And an existing utility function of the other moving object including the moving cost of the other moving object and the collision cost of the other moving object. The moving body according to claim 9, wherein the first utility function is represented by the following equation.

Where u _i (t) is the first utility function, w _i (t) is the priority of the moving object, x _i (t) is the position according to the time of the moving object, and v _i (t) is the moving object The velocity over time, c _i (t) is the cost that the mobile consumes over time, c _{i, mobility} (t) is the travel cost over time of the mobile, c _{i, collision} (t) is the The collision cost according to the time of the moving object, C _mobility is the moving unit cost constant of the moving object, C _collision is the collision cost constant of the moving object, d _{i, j} (t) is the distance between the moving object and the other moving object, x _j ( t) is the position according to the time of the other movable body.

Images