Patent ID: 12223447

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

The following description of the present invention based on the accompanying drawings is not limited to specific embodiments and may be variously modified, and the present invention may have a variety of embodiments. Also, it should be understood that the following description includes all alterations, equivalents, and substitutions within the spirit and technical scope of the present invention.

In the following description, terms including first, second, etc. are used for describing various components. These components are not limited by the terms, and the terms are used only for the purpose of distinguishing one component from another.

Throughout the specification, like reference numerals refer to like elements.

As used herein, the singular forms include the plural forms unless context clearly indicates otherwise. Also, the terms “comprise,” “include,” “have,” etc. used herein should be interpreted as indicating the presence of features, numerals, steps, operations, components, parts, or combinations thereof stated in the specification and should not be understood as excluding the presence or addition of one or more other features, numerals, steps, operations, components, parts, or combinations thereof.

As used herein, the terms including “unit,” “part,” “module,” etc. mean units that process at least one function or operation. The units may be implemented as hardware, software, or a combination of hardware and software.

Hereinafter, a drone taxi system based on multi-agent reinforcement learning and a drone taxi operation method using the drone taxi system according to exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings.

FIG.1is a diagram illustrating a drone taxi system based on multi-agent reinforcement learning according to an exemplary embodiment of the present invention.FIG.2is a block diagram illustrating a control server of a drone taxi system based on multi-agent reinforcement learning according to an exemplary embodiment of the present invention.FIG.3is a diagram illustrating a structure of a route optimizer ofFIG.2.FIG.4is an example diagram illustrating a state matrix mapped to nodes (drone taxies) of a graph structure generated by the route optimizer ofFIG.2.

The drone taxi system based on multi-agent reinforcement learning (hereinafter “drone taxi system”) according to the exemplary embodiment of the present invention optimizes routes of a plurality of drone taxies and causes the drone taxies to take cooperative actions through a graph neural network (a game abstraction mechanism based on two-stage attention network (G2ANet)), thereby maximizing profits of drone taxies.

In other words, routes are optimized in a cooperative manner, and thus it is possible to solve traffic jam in a future smart city. Also, efficient operation and application of carpooling and the like are possible, and thus profits of drone taxies can be maximized.

Referring toFIG.1, a drone taxi system may include passenger terminals (not shown), drone taxies1, and a control server2.

The passenger terminals may be mobile terminals possessed by people who want to use the drone taxies1, that is, passengers. The passenger terminals include an application for using the drone taxi system. Accordingly, the passenger terminals receive call information from the passengers and thus may be detected by the drone taxies1. The detected passenger terminals may transmit the call information to the drone taxies1.

The call information may include departure point information, destination information, and whether carpooling is possible. However, the call information is not limited thereto and may additionally include various pieces of information such as a passenger number and the like.

The application enables passengers to use the drone taxi system of the present invention. The application is a general application based on Android or iOS but may be provided as a webservice-based application depending on terminal or wired or wireless service type. According to provision methods, a passenger may access a server through a terminal and download the application or download the application through an online application market (e.g., Google Play, Apple Store, an online market of a communication service provider, etc.), and install the application.

The passenger terminals may receive assignment information from the drone taxies1. The assignment information may include a number, current location information, departure point arrival time information, etc. of an assigned drone taxi. However, the assignment information is not limited thereto and may include stopover information and the like when a carpool is made up.

The drone taxies1refer to drones that may carry passengers. Personal aerial vehicles (PAVs) or electric vertical takeoff and landing (eVTOL) may be used, but the drone taxies1are not limited thereto.

Each of the drone taxies1may detect passenger terminals present within a certain range through a communicator, receive call information from the detected passenger terminals, and transmit the call information to the control server2.

The drone taxi1includes a global positioning system (GPS) and thus may transmit current location information to the control server2in real time.

The drone taxi1may receive travel route information from the control server2and travel according to the travel route information under the control of a controller.

When travel route information is received from the control server2, the drone taxi1may transmit assignment information to a terminal of a passenger selected as a candidate passenger.

When the passenger boards, the drone taxi1may transmit boarding information (an onboard time, a boarding location, etc.) to the control server2.

Upon arriving at a destination, the drone taxi1may transmit destination arrival information to the control server2, and payment of the fare may be processed. To process the payment, the drone taxi1may include a payment terminal.

The control server2may select a passenger who will board each drone taxi1and design an optimal route to control travel of the drone taxi1.

In other words, the control server2may receive call information of passengers from each drone taxi1to select a candidate passenger depending on whether an onboard passenger is present and may generate travel route information of each drone taxi1from drone state information of the plurality of drone taxies1through multi-agent reinforcement learning to control the drone taxies1.

Referring toFIG.2, the control server2may include a passenger selector20, a route optimizer21, an administrator22, and a compensator23.

The passenger selector20may receive call information of passengers from the drone taxi1and select a candidate passenger depending on whether a passenger is present. Here, the passengers may be candidate passengers or onboard passengers.

The onboard passengers may be passengers who are aboard the drone taxi1, and a determination on onboard passengers may be made using drone state information of the drone taxi1. In this case, only call information of passenger terminals to which the drone taxies1are not assigned may be used.

The drone state information of the drone taxi1may include at least one of current location information, onboard passenger information, candidate passenger information, and vacant seat information.

In other words, the passenger selector20may select a candidate passenger in consideration of three cases, that is, a case in which there is no passenger in the drone taxi1, a case in which there is a passenger and a vacant seat, and a case in which there is no vacant seat.

First, when there is no passenger in the drone taxi1, the passenger selector20may compare distances through the current location information of the drone taxi1and the call information received from the drone taxi1and determine call information, which indicates a shortest distance from the current location of the drone taxi1and allows a long-distance travel, to select a candidate passenger.

More specifically, the passenger selector20may determine call information having a maximum value through Equation 1 below and select the call information as a candidate passenger.

argmaxpm(❘"\[LeftBracketingBar]"Pmdep⁢Pmdes❘"\[RightBracketingBar]"-❘"\[LeftBracketingBar]"On⁢Pmdep❘"\[RightBracketingBar]")[Equation⁢1]

Here, |OnPmdep| denotes a distance value from a current location of an nthdrone taxi to a departure point of an mthpassenger, |PmdepPmdep| and denotes a distance value from the departure point to a destination of the mthpassenger.

In this process, a first passenger of the drone taxi1may be selected.

Meanwhile, the number of seats in the drone taxi1is fixed, and thus the number of passengers who may board the drone taxi1may be limited.

Accordingly, when there are passengers but there is still a vacant seat, the passenger selector20may additionally select a candidate passenger. When there is no vacant seat, the passenger selector20may stop selecting a candidate passenger.

When calling the drone taxi1, a passenger may select whether carpooling is possible. When the first selected passenger allows a carpool, the passenger selector20may additionally select a candidate passenger. When the first selected passenger allows no carpool, the passenger selector20may stop selecting a candidate passenger regardless of a vacant seat.

When there is a passenger (a candidate passenger or an onboard passenger) in the drone taxi1, there may be a vacant seat, and the passenger may allow a carpool. In this case, the passenger selector20may analyze a cosine similarity between a travel direction based on travel route information of the drone taxi1and a travel direction based on a departure point and a destination of received call information and select call information which has the highest cosine similarity as a candidate passenger.

In other words, a passenger heading in a direction similar to a direction in which the drone taxi1currently travels may be selected as a candidate passenger such that a carpool may be made up more efficiently.

The travel direction based on the travel route information may be a direction in which the drone taxi1currently moves after the travel route information is set by the route optimizer21because a passenger is present.

The passenger selector20may repeat the above process until there is no vacant seat in the drone taxi1.

The route optimizer21may generate travel route information of each drone taxi1from drone state information of a plurality of drone taxies1through G2ANet, which is a graph-based neural network, during multi-agent reinforcement learning and transmit the travel route information to each drone taxi1.

Referring toFIG.3, the route optimizer21may include a graph definer210, an attention part211, and a route generator212.

The graph definer210may define relationships between the plurality of drone taxies1as a graph structure using drone state information of the drone taxies1.

For example, assuming that there are four drone taxies1(h1, h2, h3, and h4), the drone taxies1may be represented as nodes in a graph structure as shown inFIG.3, and the relationships between the drone taxies1may be represented as edges. In other words, the graph structure may include a set of the nodes, which are the drone taxies1, and edges that represent relationships between the drone taxies1.

Also, the graph definer210may generate a state matrix for each drone taxi1on the basis of drone state information. Such a state matrix may be mapped to each drone taxi (node) in the graph structure.

In the state matrix, action values including a variable which is set according to the drone state information of the drone taxies1are arranged. This will be described in further detail with reference toFIG.4.

The variable of action values may include at least one of a direction vector [POSx, POSy], a distance [d], and a penalty [p]. The variable may include all of the direction vector [POSx, POSy], the distance [d], and the penalty [p], but is not limited thereto.

Referring toFIG.4, assuming that the number of seats of the drone taxi1is four, that is, the maximum number of passengers aboard is four, and the drone taxi1has one onboard passenger and two candidate passengers, four action values C1, C2, C3, and C4may be set to be taken by the drone taxi1.

It is assumed that drone state information of the drone taxi1includes two pieces of onboard passenger information, one piece of candidate passenger information, and vacant seat information (vacant seat1).

Accordingly, when an action value is based on the candidate passenger information, the direction vector [POSx, POSy] and the distance [d] may be set according to departure point information in the candidate passenger information as indicated by [C1]. In this case, an onboard time may be set to “0” in the candidate passenger information. This is because the passenger has not boarded the drone taxi1yet.

For this reason, there is no change in the boarding time, and the penalty [p] does not apply. Therefore, the penalty [p] may be set to “1.”

When an action value is based on the onboard passenger information, the direction vector [POSx, POSy] and the distance [d] may be set according to destination information in the onboard passenger information as indicated by [C2] and [C3] In this case, an onboard time in the onboard passenger information may be set to a current time. Since time is passing with the passengers on board, the penalty [p] may vary depending on the current time until the onboard passengers get off and apply. A method of calculating the penalty will be described in detail below with reference to the compensator23.

Meanwhile, when the penalty [p] calculated according to the onboard time has a positive value, the penalty [p] may be set to “1” as indicated by [C4] and when the penalty calculated has a negative value, the penalty may be set to “0” as indicated by [C3].

When an action value is based on the vacant seat information, the direction vector [POSx, POSy] and the distance [d] may be set to “0” as indicated by [C4].

The reason is that a departure point where the candidate passengers are present is important because the candidate passengers have not boarded the drone taxi1yet and a destination where the onboard passenger wants to go is important because the passenger has boarded the drone taxi1already.

The attention part211may remove irrelevant edges by processing the graph structure defined by the graph definer210and give weights.

More specifically, the attention part211may include hard attention and soft attention.

Hard attention may remove interference between irrelevant drone taxies1by processing the graph structure defined by the graph definer210. Accordingly, the relationships between the drone taxies1may be simplified.

Soft attention may process the graph structure defined by the graph definer210and give weights Wsaccording to the degree of relationship between drone taxies1. The higher the degree of relationship, the higher weight Wsmay be given to the edge between the drone taxies1.

The route generator212may generate travel route information of each drone taxi on the basis of the graph structures processed by the attention part211.

In other words, the route generator212may acquire one graph structure by combining the graph structure, in which interference is processed, obtained from hard attention and the graph structure, to which weights are given, obtained from soft attention and design travel route information using action values of a state matrix of each drone taxi1on the basis of the graph structure.

The generated travel route information may be transmitted to each drone taxi1such that travel of the drone taxi1may be controlled according to the travel route information.

The route optimizer21may perform a process of generating travel route information every time the drone state information of the drone taxi1is updated, but the present invention is not limited thereto.

The administrator22may manage the drone state information of the drone taxi1by updating the drone state information in real time.

The drone state information of the drone taxi1may include at least one of current location information, onboard passenger information, candidate passenger information, and vacant seat information.

The onboard passenger information may include departure point information, destination information, and an onboard time, which may indicate a time that has passed since boarding.

Also, the candidate passenger information may include departure point information, destination information, and an onboard time, and the onboard time of the candidate passenger information may be set to “0” because the candidate passengers have not boarded yet.

When a candidate passenger is selected by the passenger selector20, current location information, boarding information, destination arrival information, etc. are received from the drone taxi1, and the administrator22may update the drone state information.

When the destination arrival information is received from the drone taxi1, the compensator23may process payment of the fare according to onboard time (a time that the passenger is actually aboard—a boarding start time and a boarding end time) in the passenger information.

This compensates the passenger for a time loss by giving a penalty to the passenger when the drone taxi1takes a longer time than an optimal travel time based on the travel route information.

More specifically, when the destination arrival information is received from the drone taxi1, the compensator23may compare the onboard time in the onboard passenger information with the optimal travel time and set a penalty according to the difference.

In this case, the compensator23may derive the penalty according to Equation 2 below.

p=topt-(tarr-tdep)topt[Equation⁢2]

Here, p denotes a penalty, toptis an optimal travel time, tarrdenotes an arrival time, and tdepdenotes a departure time. (tarr−tdep) denotes an onboard time which is a time that a passenger is actually aboard.

The time that the passenger is actually aboard versus the optimal travel time is observed as a ratio through Equation 2 above to give a penalty such that the passenger and the drone taxi1may be compensated.

For example, when a result of comparing the onboard time based on the onboard passenger information with the optimal travel time indicates that the onboard time is longer than the optimal travel time, the penalty p generated by the compensator23may have a negative value. The penalty may be applied to the fare such that the fare may be reduced.

In this way, the passenger may be compensated for the time loss.

On the other hand, when the result of comparing the onboard time based on the onboard passenger information with the optimal travel time indicates that the onboard time is shorter than the optimal travel time, the penalty p generated by the compensator23may have a positive value. The penalty may be applied to the fare such that the fare may be increased.

Accordingly, the drone taxi1may obtain additional profit by providing temporal benefit to the passenger.

A drone taxi operation method using the drone taxi system based on multi-agent reinforcement learning will be described in detail below.

FIG.5is a flowchart schematically illustrating a drone taxi operation method using a drone taxi system based on multi-agent reinforcement learning according to an exemplary embodiment of the present invention, andFIG.6is a flowchart sequentially illustrating a route setting operation ofFIG.5.

Referring toFIG.5, the drone taxi operation method using a drone taxi system based on multi-agent reinforcement learning according to the exemplary embodiment of the present invention may include a passenger search operation S1, a passenger selection operation S2, a route setting operation S3, and a payment operation S4.

First, in the passenger search operation S1, the drone taxies1may search for passengers present within a certain range and receive call information including departure point information and destination information from passenger terminals present within the certain range.

Also, in the operation S1, the drone taxies1may transmit the received call information and current location information to the control server2.

In the passenger selection operation S2, the control server2may receive the call information from the drone taxies1and select a candidate passenger depending on whether a passenger is present.

In the operation S2, a candidate passenger may be selected in consideration of three cases, that is, a case in which there is no passenger in the drone taxies1, a case in which a passenger is present but there is still a vacant seat, and a case in which there is no vacant seat. This has been described above with reference to the system, and the detailed description will not be reiterated.

In the route setting operation S3, the control server2may generate travel route information of each drone taxi1from drone state information of the plurality of drone taxies1through multi-agent reinforcement learning and transmit the travel route information to each drone taxi1.

The operation S3may include a graph definition operation S30, a graph processing operation S31, and a route generation operation S32.

In the graph definition operation S30, the control server2may define relationships between the plurality of drone taxies1as a graph structure using the drone state information of the drone taxies1.

In the graph processing operation S31, the graph structure defined in the operation S30may be processed to remove irrelevant edges, and weights may be given.

In the route generation operation S32, travel route information of each drone taxi1may be generated on the basis of the graph structure processed in the operation S31.

This has been described in detail above with reference to the system, and the detailed description will not be reiterated.

In the payment operation S4, when destination arrival information is received from the drone taxies1, the control server2may process payment of fares according to onboard times in onboard passenger information. A detailed description thereof will be omitted.

As described above, the drone taxi system based on multi-agent reinforcement learning and the drone taxi operation method using the drone taxi system according to exemplary embodiments of the present invention can maximize profits of a plurality of drone taxies by optimizing routes of the drone taxies through multi-agent reinforcement learning.

Also, the drone taxi system and the drone taxi operation method can save time and money consumed in passenger transportation.

Further, when a drone taxi travels longer than the expected time, it is possible to reduce the fare, and thus the passenger can be compensated for a time loss.

The above-described present invention will be described in further detail below with reference to an experimental example and the exemplary embodiments. However, the present invention is not necessarily limited to the experimental example and the exemplary embodiments.

[Experimental Example 1] Comparison Between Drone Taxi Routes

To evaluate the drone taxi system according to the exemplary embodiment of the present invention, drone taxi routes of systems to which the exemplary embodiment and Comparative Example of the present invention are applied are analyzed.

In a 25 km×25 km two dimensional (2D) vector space, it is assumed that four drone taxies are used as agents and there are 20 passengers. To the Comparative Example, a random action algorithm is applied.

The results are shown inFIG.7.

FIGS.7A and7Bare graphs illustrating drone taxi routes according to the exemplary embodiment and Comparative Example of the present invention.

As shown inFIG.7, the exemplary embodiment of the present invention is run with a better route than Comparative Example, and thus it is possible to serve a larger number of passengers within a wider range.

The above-described drone taxi system based on multi-agent reinforcement learning and the drone taxi operation method using the drone taxi system according to the exemplary embodiments of the present invention can maximize profits of a plurality of drone taxies by optimizing routes of the drone taxies through multi-agent reinforcement learning.

Also, the drone taxi system and the drone taxi operation method can save time and money consumed in passenger transportation.

Further, when a drone taxi takes longer than the expected time, it is possible to reduce the fare, and thus the passenger can be compensated for a time loss.

Although exemplary embodiments of the present invention have been described with reference to the accompanying drawings, those of ordinary skill in the art should understand that the present invention can be implemented in other specific forms without changing the technical spirit or necessary features of the present invention. Therefore, the above-described embodiments are exemplary and are not limiting in all aspects.