ユニファ開発者ブログ

ユニファ株式会社システム開発部メンバーによるブログです。

シフトスケジューリング問題

研究開発部の浅野です。普段は画像やヘルスケアデータを扱うことが多いのですが、最近シフトスケジューリング問題に興味をもって学び始めたので、その内容を少しご紹介したいと思います。シフトスケジューリング問題とは、人員の配置基準や働く人の希望、能力、相性、業務負荷などを加味しながらある一定期間(1ヶ月など)の勤務シフト表を作成する問題です。看護師のナーススケジューリングが有名ですが、保育士のシフト作成も多くの園長先生が頭を悩ませていることの一つです。今回はこの問題を最適化問題としてモデル化・定式化して実際に解いてみたいと思います。

最適化問題は、制約条件を満たす解の中で、目的関数を最小(最大)にする解を求めるもので、次のように定義されます。

\begin{align} minimize \quad &f(x): &目的関数\\ subject \; to \\ &g(x)>= 0: &不等式制約条件\\ &h(x) = 0: &等式制約条件\\ &a <= x <= b: &変数\\ \end{align}

我が家のシフトスケジューリング問題

共働きで3人の子どもを育てており、朝の支度と夜のお迎えから寝かしつけまでを夫婦どちらが担当するのか、仕事などの都合を考慮して決めています。週の終わりにお互いの来週の予定を共有し、それをもとに1週間分のシフトを作成します。それぞれの都合を尊重しつつ公平性を保った配分を手作業で決めるのは結構面倒です。

それではこの問題を徐々にモデル化および定式化していきましょう。メンバー mが曜日 dにアクション aを担当するときに 1、そうでないときに 0となる変数 x_{mda}を使います。夫婦がどちらも都合が悪い場合に奥様の母上がヘルプに入ってくれてとても助かっているのですが、それに甘えすぎると大切な子どもとの時間を仕事などに割り振ってしまう傾向が強まります。そこで目的関数として母上のヘルプ回数を設定し、それを最小化するという問題設定にします。

 \displaystyle
minimize  \sum_{d \in D, \, a \in A} x_{母da} \qquad D=\{Mon, Tue, Wed, Thu, Fri\}, \, A=\{朝, お迎え\}

これは我が家ではこうするのがよい、ということであり、各家庭の状況によって問題設定は変わります。このように、どんな目的関数を設定してどのような制約条件を設けるかというモデリングはかなりドメインの知識を必要とする作業です。

それではここまでの部分をコードに落としてみましょう。PythonのPuLPという最適化問題のモデリングを簡単にコーディングできるライブラリを用います。PuLPには汎用ソルバーもバンドルされているため、そのまま解を求めることも可能です。

import pulp

Member = ["夫", "妻", "母"] 
Day = ["Mon", "Tue", "Wed", "Thu", "Fri"] 
Action = ["朝", "お迎え"] 

#問題の宣言
ShiftScheduling = pulp.LpProblem("ShiftScheduling", pulp.LpMinimize)

#変数宣言
x = {}
for m in Member:
    for d in Day:
        for a in Action:
            x[m, d, a] = pulp.LpVariable("x({:},{:},{:})".format(m,d,a), 0, 1, pulp.LpInteger)

#目的関数:母からのヘルプを最小限に抑える
ShiftScheduling += pulp.lpSum(x['母', d, a] for d in Day for a in Action), "Target"

制約条件

制約条件として、まず下記を考えます。

 \displaystyle  \sum_{m \in M} x_{mda}=1 \qquad M=\{夫、妻、母\}, \, d \in D, \, a \in A

これは毎日朝とお迎えには誰か1人が必ずアサインされる、という意味です。そうしないと子ども達が路頭に迷ってしまいます。次に、この日は朝早く出社したい、あるいは遅くなるからお迎えに行けない、といった条件を加えます。

 \displaystyle   x_{mda}=0 \qquad (m,d,a) \in NG, \quad NG=\{(m, d, a) | メンバーmは曜日dにアクションaが不可能\}

これらをコードにすると下記のようになります。夫は火曜朝と木曜夜、妻は水曜夜、(宿泊出張で)木曜夜と金曜の朝が都合が悪い(実際よくあるパターン)、としています。

# それぞれの日の朝やお迎えに必ず誰か1人が割り当てられる
for d in Day:
    for a in Action:
        ShiftScheduling += pulp.lpSum(x[m, d, a] for m in Member) == 1, "Constraint_{:}_{:}".format(d,a)

# 対応不可能日
NG = [['夫','Tue','朝'],['妻','Wed','お迎え'],['夫','Thu','お迎え'],['妻','Thu','お迎え'],['妻','Fri','朝']]
for m, d, a in NG:
    ShiftScheduling += x[m, d, a] == 0, "Constraint_NG_{:}_{:}_{:}".format(m,d,a)

解いてみる

では一旦この状態で最適化問題を解いてみましょう。 solve()関数を呼ぶだけです。その結果作成されたシフトも示します。

results = ShiftScheduling.solve()
print("optimality = {:}, target value = {:}".format(pulp.LpStatus[results], pulp.value(ShiftScheduling.objective)))

 optimality = Optimal, \quad target \, value = 1.0

f:id:unifa_tech:20190616233256j:plain:w300
自動で計算されたシフト

print文の出力は、最適解が見つかったことと、母上の出動が1回あることを示しています。確かに木曜のお迎えは夫婦どちらも対応できないのでやむを得ません。他の都合が悪い日についてもちゃんと考慮されたシフトになっています。ただしこれをこのまま奥様に見せたら不公平だとお怒りになりますね。

制約条件の追加

そこで1週間の出動回数の差が大きくならないように制約条件を追加します。数式は割愛してコードと結果を示します。

# 週全体で出動回数の差を抑える
n_act_wife = pulp.lpSum(x['妻', d, a] for d in Day for a in Action)
n_act_husband = pulp.lpSum(x['夫',d, a] for d in Day for a in Action)
ShiftScheduling += n_act_wife - n_act_husband <= 1, "Constraint_fairness_wife"
ShiftScheduling += n_act_husband - n_act_wife <= 1, "Constraint_fairness_husband"

f:id:unifa_tech:20190616234538j:plain:w300
出動回数を調整したシフト

これで奥様の怒りも収まりますね。しかしよく見ると水曜日は朝もお迎えも自分が担当になっていて、できなくはないのですがちと辛い。そこでもう一つ制約条件を加えて朝とお迎えが重ならないようにします。ここも数式は割愛。

# 1日で朝かお迎えどちらかだけ
for m in Member:
    for d in Day:
        ShiftScheduling += pulp.lpSum(x[m, d, a] for a in Action) <= 1, "Constraint_Either_{:}_{:}".format(m,d)

f:id:unifa_tech:20190616235159j:plain:w300
朝とお迎えが重ならないようにしたシフト

いいシフトができました。今後は都合の悪い日をインプットするだけで自動的に公平な分担表を作成できて楽になります。

まとめ

シフトスケジューリング問題に対して、最適化問題としてのモデル化、定式化、コードへの実装を一通り行うことができました。今回扱ったのは登場メンバーが3人で1週間分の朝とお迎えシフトを決めるという比較的小さな問題で、変数の数が30しかないため解は一瞬で得られます。実際の保育士のシフト作成は、数十人の保育士さんの1ヶ月分の勤務(早番、中番、遅番など)を、園児の人数あたりの保育士配置基準、ベテランと若手のミックス、研修や休暇などの予定、シフトに入れる時間帯の制約、体調などを考慮に入れて作成します。変数の数や制約条件が桁違いに多くなるため複雑な作業になりますが、ドメイン知識を使ってモデル化し、目的関数や制約条件をうまく定式化し、ソルバーを使って解くという流れは同じです。こうした技術を使って保育園での作業負担をどんどん減らしていきたいですね。

AI Stock Price Prediction Methods.

By Matthew Millar R&D Scientist at ユニファ

Summary:

            This blog is looking at finding the best method for future price prediction for stocks in general.  This blog will look at methods for calculating production that is in current research and uses in the industry.  Also, it will cover; statistical methods, machine learning, artificial neural networks, and hybrid models.  From the current research, hybrid models were found to give the best results over pure statistical methods and pure machine learning and artificial neural network methodologies.

Introduction:

            Stock market prediction is a method to discover possible future values of a stock.  With successful predictions of prices, higher profits can be gained, but on the other hand with bad predictions can produce losses.  There is a standard thought that the market does not follow a standard flow, so predictions using statistics or models would be an impossible task due to the idea that technical factors cannot show all of the variables that help shape the movement of the stock market.  On the contrary, the efficient market hypothesis would otherwise suggest, a stock price already reflects all the information that could affect any price changes except for unknown information which is always a level of unpredictability.

            Fundamental analysis looks at the company rather than just the numbers or charts.  This involves looking at the past performance and credibility of its accounts.  This approach is mainly used by fund managers as this is one of the traditional methods that use publicly available information on the company.  Technical analysis does not care about the company's fundamentals but mainly look at the trends of the stocks past performance in a time series analysis.  These are the two more common ways of stock price prediction.  Current trends in price forecasting are the use of Data mining technologies.  The use of Artificial Neural Networks (ANN), Machine Learning (ML) algorithms, and statistical models are now being used to help in prediction.       

            Due to the increasing amount of data from trades, data mining and data analysis on this amount of data can be very difficult using standard methods.  With the amount of data that is produced daily, this could be considered on the level of Big Data analytics.  Due to the ever-changing values of the data throughout the day, it is difficult to monitor every stock that is available, let alone to perform prediction on price movements.  This is where the use of algorithms and models come into play.  With these algorithmic models, predictions can be made with relative accuracy and can give investors better insight into the actual data's value without all of the excessive amounts of data review.

Goal:

            The goal of this blog is to look at possible methods for prediction using ML, ANN, and statistical models.  Statistical methods are the most commonly used method for price prediction currently, but will the use of ML, ANN, or hybrid systems can give a more accurate prediction. It will continue to look at statistical methods, pure ML, pure ANN, and hybrid models, a more comprehensive list can be made, and a better idea of which approach could be better for forecasting purposes.   

Methodology Review:

            There are a few emerging methods that are gaining popularity and applications over the traditional financial approaches.  These methods are based on ML, statistical models, ANN, or a hybrid model.  Some of the proposed models use a purely statistical method, some use pure ML or ANN, and others use a hybrid approach combining both statistical and ML or ANN together.  Each model has its pros and cons for use and a problem that solves best.

Statistical Methods:

            By using data analysis, one can predict the closing price of a certain stock.  Currently, there are six common methods or data analysis to make a predictive model.  Some of these models are common Stock price models that are used currently in the stock market and by fund managers.  These five models are must be in agreement of the movement direction in order for the price movement to be predicted most accurately.  These models are; Typical Price (TP), Chaikin Money Flow Indicator (CMI), Stochastic Momentum Index (SMI),

Relative Strength Index (RSI), Bollinger Bands (BB), Moving Average(MA), and Bollinger Signal.  By combining these algorithms, a more accurate prediction can be made by looking at upper and lower bands, if the price goes above the upper band then that indicates a positive selling point and if it goes below the lower band it indicates a positive buy point.  This method of combining the results of other models does give a better chance of price change than just one of the single statistical models (Kannan, Sekar, Sathik, & Arumugam, 2010).

Machine Learning Artificial Neural Network Methods:            

            Text mining has also been used in stock prices trends, especially for inter day prices trends.  By using text mining techniques, a 46% chance of knowing if a stock will increase or decrease by 0.5% or remain in the positive and negative range, which was more significant than a random predictor which only gave around 33% accuracy for stock price fluctuation prediction.  By using a process of text mining, by gathering press releases and preprocess them into usable data and categorizing them into different news types.  Trading rules can then be derived from this data for particular stocks (Mittermayer, 2004).

            Pure ANN is used currently for stock prediction as well as analysis.  The users have given very reliable results as ANN are good at working with errors, can use large and complex data, and can produce useful prediction results.  For forecasting just one stock, there is a lot of interacting input series that is needed.  Each neuron can represent a decision process.  This will allow for ANN to represent the interaction between the decisions of everyone in the market.  This will allow for the ANN to completely model a market.  ANN is very effective at predicting stock prices (Kimoto, Asakawa, Yoda, & Takeoka, 1990; Li, & Ma, 2010),

            ANN is gaining acceptance in the financial sector.  There are many techniques and application that look into using AI in creating prediction models.  One common method is to use a genetic algorithm (GA) to aid in the training or the ANN for the prediction of stock prices.  The GA, in most cases, are used for training the network, selecting the feature subset, and aiding in topology optimization.  A GA can be used to help in the feature discretionary and determination of connection weights for an ANN (Kim and Ham, 2000).

Hybrid Models:

            ML combined with an AI is a very good combination of two very powerful methodologies.  An ML model can be used for data mining to define and predict the relationships between both financial and economic variables.  The examination of the level estimation and classification can be used for a prediction of future values.  Multiple studies show that by using a classification model, a trading strategy can generate higher risk-adjusted profits than the traditional buy and hold strategy as well as the level estimation prediction capability of an ANN or linear regression (Enke and Thawornwong, 2005).  ML is mainly based on supervised learning which is not appropriate for long term goals.  But, by using reinforcement learning ML, is more suitable for modeling real-world situations much like stock price prediction.  By looking at stock price prediction as a Markov process, ML with the TD(0) reinforcement learning algorithm that focuses on learning from experiences which are combined with an ANN is taught the states of each stock price trend at given times.  There is an issue with this in that if the prediction period is either very short or very long, the accuracy decays drastically.  So this would only be useful for mid-range prediction for prices (Lee, 2001).  Another Hybrid model that has given great accuracy (around 77%) is combining a decision tree and an ANN together.  By using the decision tree to create the rules for the forecasting decision and the ANN to generate the prediction.  This combination is more accurate than either an ANN or a decision tree separately (Tsai and Wang, 2009).

Other Useful Models:

            Support Vector Machines have also been used for stock market prediction.  SVM does perform better than random guessing but are out shown by hybrid models.  A combination of a genetic algorithm and an SVM can produce a better result than even an SVM alone.  By using some technical analysis fields used as input features.  This method was used to not only produce a forecast for the stock that is being looked at as well as any other stock that has a correlation between each other and the target stock.  This hybrid significantly can outperform a standalone SVM (Choudhry and Garg, 2008). 

Discussion:

            There are many ways to produce a future value prediction, though some are slightly better and more accurate than others.  Statistical analysis is the most common approach to prediction.  Linear regression, logistic regression, time series models, etc... are some of the more common ways of predicting future values.  But, these methods may not be the best for more complex and dynamic data sets.  If the data is not the same type, linear regression may have poor results.  This is where an ANN or ML model comes in.  These can produce a better result which a higher accuracy than a purely statistical approach as they can work with the complex systems of a market.  In the pure form, an ANN or ML can produce better accuracy over many statistical methods for most stock price predictions.  But, by using hybrid ANN, an even more accurate and useful model can be done.  By combining a DT or a GA with an ANN, a greater accuracy over the two pure methods can be gained.   

 

 

 

 

Reference:

Choudhry, R., & Garg, K. (2008). A Hybrid Machine Learning System for Stock Market Forecasting. World Academy of Science, Engineering and Technology International Journal of Computer and Information Engineering, 2(3).

 

Enke, D., & Thawornwong, S. (2005). The use of data mining and neural networks for forecasting stock market returns. Expert Systems with Applications, 29(4), 927-940.

 

Kannan, K., Sekar, P., Sathik, M., & Arumugam, P. (2010). Financial Stock Market Forecast using Data Mining Techniques. Proceedings of the International MultiConferences of Engineers and Computer Scientists, 1.

 

Kim, K., & Han, I. (2000). Genetic algorithms approach to feature discretization in artificial neural networks for the prediction of stock price index. Expert Systems with Applications, 19(2), 125-132.

 

Kimoto, T., Asakawa, K., Yoda, M., & Takeoka, M. (1990). Stock market prediction system with modular neural networks. 1990 IJCNN International Joint Conference on Neural Networks.

 

Lee, J. W. (2001). Stock price prediction using reinforcement learning. ISIE 2001. 2001 IEEE International Symposium on Industrial Electronics Proceedings (Cat. No.01TH8570). 

 

Lin, Tom C. W., The New Investor. 60 UCLA Law Review 678 (2013); 60 UCLA Law Review 678 (2013); Temple University Legal Studies Research Paper No. 2013-45. Available at SSRN: https://ssrn.com/abstract=2227498

 

Li, Y., & Ma, W. (2010)Applications of Artificial Neural Networks in Financial Economics: A Survey. 2010 International Symposium on Computational Intelligence and Design, Computational Intelligence and Design (ISCID), 2010 International Symposium on, 211. 

 

Mittermayer, M. (2004). Forecasting Intraday Stock Price Trends with Text Mining Techniques. E Proceedings of the Hawai'i International Conference on System Sciences, January 5 – 8, 2004, Big Island, Hawaii.

 

Tsai, C. Wang, S. (2009). Stock Price Forecasting by Hybrid Machine Learning Techniques. Proceedings of the International MultiConference of Engineers and Computer Scientist 2009 Vol1 IMECS 2009. Vol 1

Reinforcement Learning the Hello World Version

By Matthew Millar R&D Scientist at ユニファ

What is Reinforcement Learning?

Reinforcement learning (RI) is a subset of Artificial Intelligence (AI) that is an agent-based approach in the field of AI. Agent-based AI learns from interacting with their environment rather than a dataset. The environment is controlled or altered by the actions of the agent. The environment changes should have goals linked to them so that the agent knows the results of each action. From this goal, appropriate actions can be learned for many different types of tasks. RI is one of the three learning techniques in machine learning. The other two are supervised and unsupervised learning. RI does not require labeled data as in supervised or semi-supervised learning.

In general, RI is a Markov Decision Process (MDP) which takes both the environment and agent states denoted a  S. It then lists out a set of all possible actions available to an agent denoted as A. There is a probability equation that shows the likely hood of transitions between states   (s1 -> s2) when a certain action  (a) is performed. The requirement of a reward is also needed to drive the system forward to learn. The normal use is an immediate reward after the transition between states denoted as  Ra(s, sl). There also must be a set of rules that control what the agent receives as feedback, or what it can observe.

f:id:unifa_tech:20190617091506g:plain
Probability

The interaction between an agent and its environment happens in discrete time steps. Each time t step will have an observation (ot ) and a reward (rt), The agent will then chose an action from its predefined set of actions (at). This action is then sent into the environment which will move the environment to its next state (st+1). As the environment moves to its next state, a new reward is then generated (rt+1). This state change can then create a transition (st, at, st+1) which allows for the agent to learn from its actions.

The agent will have to learn what is optimal behavior which leads to teaching it to regret its actions. Regret compares the performance of the current agent to that of an “optimal” agent and looks at the differences between both the actions and the awarded rewards. This is where instant rewards can hinder the performance of a model. The Agent will have to consider the long-term outcomes of its actions. This means even if the instant rewards for a certain action may be negative, the total long-term rewards could be higher. This is all to maximize future outcomes and rewards. This allows for RI to be applied to both short term goals as well as long term solutions, but not at the same time normally.

For an agent to increase the total rewards for a task, a balance between exploration and exploitation needs to be considered. Exploitation is basically using what works. This means that the agent will continue to perform actions that give it the best rewards but may not be optimal or can max out the rewards for a given set of actions. This is where exploration comes in to manage this and to hopefully optimize the result by trying different actions at any given time step. In general, simple exploration models are preferred as there are very few exploration algorithms that can scale up with a very complex environment and action sets. One way is to choose the best long-term action and then randomly choose an action at different times to see if these actions can improve on the already defined “optimal” long-term option.

There are many options to control the learning process for RI agents. The idea of how to define what actions a beneficial is still difficult to deal with correctly. The simplest method if the action set is finite is to use a policy. A policy maps the probability of action to a certain change in the state of the environment. These policies are the base of all other learning algorithms. The state-value function uses the policies by looking at the expected return of each action from the initial state and successfully follow the policy. This method evaluates the benefit of being in certain states over others. Monte Cario (MC) method can be used to mimic a policy evaluation and improvement. MC evaluation step looks at every state and action pair and averages all the returns from each state and action pair. This can compute a very accurate Q-table which can fully evaluate the policy. The improvement step uses a greedy policy and looks at each state-action pair and then computes an action that will maximize the return for each state. These are just two methods to control the learning of an RI agent.

Simple Example:

This was a very quick overview of the main principles of RI. Now let’s get to our first project.
So, let’s start with the hello world of OpenAI Gym. Note that this is just a first step on our way to the final project that I have planned.
The first step is to get all the dependencies.

Tensorflow: pip install --upgrade tensorflow
Keras: pip install Keras
Numpy: pip install numpy
OpenAI Gym: pip install gym.

Now that we have all the requirements lets get down to the nuts and bolts.
Let’s define our rewards method

Calculate Rewards (reward, gamma value)
		The new reward is reward + (previous reward * gamma value) 

This method lets us calculate the reward for every action.
Now let use a custom log loss function as well

Custom Loss (True Value, Predicted Value)
		Log(True * (true – Predicted) + (1 – ture) * (true + predicted)
		Take the mean of the results of this

Now a scoring function to see how accurate out AI is for testing.

Evaluate Model (Model, number of tests)
		Model score = 0
		Total reward = [] # Holds all rewards for each iteration
		For each iteration or run though the environment
			Sum of rewards
			Have the agent run though the environment collecting rewards
			Add the collected rewards to the Sum of rewards
			After the iteration add the final rewards 
		After each run through to add the final rewards to the total reward list
		Then you can find the mean, median, or the mode score or any other method you want

Now the keras model part

# Set up Keras model
action_count = env.action_space.n
input_shape = layers.Input(shape=env.reset().shape)
adv = layers.Input(shape=[1])

x = layers.Dense(8,activation="relu",
                 kernel_initializer=glorot_uniform(seed=42))(input_shape)
out = layers.Dense(action_count,activation="softmax",
                   kernel_initializer=glorot_uniform(seed=42))(x)

# Crate the training model and prediction model
train_model = Model(inputs=[input_shape, adv], outputs=out)
train_model.compile(loss=my_ri_loss, optimizer=Adam(lr))
test_model = Model(inputs=[input_shape], outputs=out)

This will allow us to then try out the test environment that is in OpenAI gym.
Let us start with

env = gym.make("CartPole-v0")

Putting it all together should give you this.

f:id:unifa_tech:20190614170044p:plain
CartRI
With the output of

Average reward for training episode 100: 19.30 Test Score: 13.60 Loss: 0.030333 
Average reward for training episode 200: 22.45 Test Score: 10.50 Loss: 0.022194 
…..
The average reward for training episode 8200: 25.68 Test Score: 191.40 Loss: -0.003017 
Solved in 8199 episodes!

Conclusion:

This is the end of this necessary explanation of RI. We learned the basics of reinforcement learning and how to code this up using a simple example in python. Now we can start to get into more complex models and even latter teach something to run!

Part two so soon!?!?

Well yes as this was a simple version and easy to follow. Let’s look at using a retro game and start playing stuff like Space Invaders and Mario!
The first thing we need to do is install Game-Retro using
pip3 install gym-retro
And that’s it, so to test this out we will use the built in rom from Airstriker-Genesis, but other roms can be downloaded and used here as well.

import retro
def main():
    env = retro.make(game='Airstriker-Genesis')
    obs = env.reset()
    while True:
        obs, rew, done, info = env.step(env.action_space.sample())
        env.render()
        if done:
            obs = env.reset()
    env.close()
if __name__ == "__main__":
    main()

And that will give you the below screen output.

f:id:unifa_tech:20190614170236p:plain
ShooterRI

Now that we know that it is working, we need to import other games into the environment. The simplest way is to import all the ROMS that came with Gym-Retro by going into the terminal and typing this

python3 -m retro.import /path/to/your/ROMs/directory/

But you will need to find ROMs that work with gym-retro.

So our next steps that we will go after is to start with Unity3D and see how to implement RI in a 3D environment over these simpler 2D games. Soon we will look at teaching an AI to walk in the future.

自動計画器がねこを動かす

 こんにちは、サーバーサイドエンジニアのいいだです。

 もうすぐ夏ですね。私は夏になると決まって、ある問題に直面します。毎年試行錯誤を繰り返してはいますが、いまいちしっくりくる答えにたどり着くことができません。つまり、そうめんに合うおかずとは何であろうかということです。

 ちなみに実家では目玉焼きが定番でした。いいえ、悪くはありません。今日は自動計画の話をします。

そうめんと自動計画とねこ

 自動計画とは、そうめんに合うおかずを決定することです。いわゆるAIの一分野で、周囲の環境や自身のとれる行動などから既知ないし未知の問題を解決する具体的な手順を作り出すのがその役目です。

f:id:unifa_tech:20190611175724p:plain:w300
そうめんのおかずを獲得する計画

 自動計画はロボットや産業機器などの真面目な分野でももちろん使われていますが、個人的な好みの問題からここではゲームにおける自動操作キャラクターの挙動とその計画を扱う仕組みとして紹介します。プレイヤーの体力が減った場合に攻撃を中断して回復アイテムを使ってくれる味方キャラクターという簡単なものから、アイテムを総取りしつつ崖際へ走ってプレイヤーの復帰を阻止する極悪非道のロゼッタ&チコまで、自動計画はゲームの様々なところで活用されています。

 今回は、与えられた環境で可能な限り長時間生存することを目標とするねこを作りました。(簡単な)ゴール指向の自動計画器を(それらしい)遺伝的ネットワーク計算によって学習し、横からレーザーを撃たれない限り死なないねこを目指します。

ねこについて

f:id:unifa_tech:20190611180037p:plain:w300
これはねこです

 ねこです。72頂点あります。関節は全て固定されていて動きませんが、時速40km程度で移動することができます。

 今回の設定では、ねこは最大で100の満腹度を持ちます。ねこが環境に存在する時、ねこは1秒ごとに2の満腹度を失います。これが50を下回った時、ねこは「はらへり」を認識します。その状態のまま何もせずにいると、やがて満腹度が0になり、体力を失い、死にます。

 ねこも死にたくはありませんので、何かを食べたいかと思います。もちろん、この環境には食べるものも用意されています。

f:id:unifa_tech:20190611180115p:plain:w300
これはすしです

 すしです。ねこは実際のところすしをあまり食べないそうですが、刺身にすると8頂点になりますので、ハイポリゴンなモデルを用いたリッチな体験を目指してすしにしました。16頂点あります。

 ねこはすしを「食べる」ことにより、満腹度を30回復することができます。これによって満腹度が80を上回った時、「はらへり」は解消されます。また、満腹度が50以上のとき、体力は徐々に回復します。

 つまり、すしを食べることでねこは永遠に生き続けるでしょう。大変喜ばしいことです。そのために、ねこには正しい食事を計画してもらいます。

ねこによる計画

 ゴール指向の自動計画器は、ゴールを最初に決め、それを解決する行動を求めることによって計画を作成します。たとえば冒頭のそうめんのおかずを獲得する計画においては、「食卓に並べる」がそれにあたります。おかずを食卓へ並べるには、食べる準備の整ったおかずが必要です。然るに、私はその下位のゴールとして「薬味オンリーで行く」を選択するでしょう。計画が短く、調理や洗い物等のコストも少なく、とても効率的であるからです。このように、効率的な計画器は食後の満足度をも左右します。

 海苔や小ねぎ、しょうがにも飽きましたか? いいえ、わさびがあります。茹でた小麦粉をめんつゆで食べましょう。

 ねこは行動を計画するための計画器として、有向グラフを一つ持ちます。これを計画グラフと呼びます。このグラフには「状態」「行動」の二種類の頂点が存在し、それらの接続(辺)を作成ないし変更することによって、計画器は「状態」の解消を目指します。

f:id:unifa_tech:20190611180327p:plain:w300
計画器によって作られた計画(理想)

 もし、ねことすしが十分に近ければ、ねこはすしをそのまま食べることができます。今回の設定では、ねこは2m以内のすしを0.17msで食べることができます。ちなみに、このねこは全長がおよそ1mあります。

f:id:unifa_tech:20190611180425p:plain:w300
ねことすしの間には距離があることを示す図

 しかしながら、往々にして、我々と食べ物との間には距離があります。ねこの口はねこと独立して移動できるようにはなっていないので、ねこがすしを食べるにはねこ自身がすしに近づく必要があります。つまり、すしが「食べる」の範囲内にあるかどうかを判断し、そうでない場合には「近づく」ことが求められます。

 このため、計画では「状態」が自身のとれる「行動」によって解消できるか、またそもそもその「行動」ができるかを自身で判断しなければなりません。この場合では、「はらへり」を解消するためには「食べる」必要があり、「食べる」には「近づく」必要があります。

f:id:unifa_tech:20190611180507p:plain:w300
実際の計画グラフ

 計画グラフはこのような「状態」と「行動」の接続を保持しておき、最終的に「現在すぐに実行できる行動」から「将来解消されるべき状態(課題)」までの道筋をねこに示すことができます。これによって、ねこはすしが近くにない時でも、自分ですしに近づき、それを食べることができるようになります。

ねこの提案グラフ

 計画においては、ねこは自分がどのような行動をとれば課題を解決できるかをよくよくわかっている必要があります。「はらへり」状態から「(何かを)食べる」へ至るには、「(何かを)食べる」ことが「はらへり」を解消する行動であると知っていなければいけません。

 このため、ねこは「現時点で解消できない状態」または「現時点で実行できない行動」に直面したとき、それを解消する新たな行動を探します。これにより、ねこはあらゆる問題に対して、最低限「直ちに実行できること」を見つけることができます。

 しかしながら、直ちに実行できれば何でもよいわけではありません。「はらへり」になった時、「食べる」ではなく「近づく」を選択してしまったねこは、すしに近づくことはしますがそれ以上は何もせず、いずれ死んでしまうでしょう。

 今回は、「すしは食べ物である」というのはねこにもわかっているものとして、「はらへり」→「食べる」や「食べる」→「近づく」の接続をねこ自身に発見してもらうべく、遺伝的ネットワーク計算による簡易的な学習の仕組みを用意します。これを提案グラフと呼びます。

f:id:unifa_tech:20190611180600p:plain:w300
提案グラフの例

 提案グラフは、「状態」「行動」「条件」「選択」の四つの頂点を持った有向グラフです。提案グラフはねこが持つ全ての「状態」及び「行動」と同じ数が用意され、始点となるそれによって使い分けられます。提案グラフは計画グラフが「直ちに解消できない状態ないし直ちに実行できない行動」に直面したとき、それを解決するために使われます。

 計画グラフは計画において、グラフの末端にある「状態」ないし「行動」が解決不可である場合、その時点の「状態」ないし「行動」を提案グラフに渡します。提案グラフはそれと同じ種類の「状態」ないし「行動」を始点として、別の「行動」へ辿り着くまで各頂点を辿って探索し、たどり着いた結果である「行動」を返します。もし探索中の頂点が次への接続を持っていなかった場合は、ランダムに別の頂点へ接続して探索を続けます。

頂点の種類 やること
状態 なにもしない(始点以外には選ばれない)
行動 始点でない場合、探索を終了する
条件 環境を指定の条件で検査し、trueかfalseによってそれぞれ別の頂点へ移動する
選択 その目標にターゲット(モノ、場所、時間)を設定する

 この結果得られた「行動」が実行可能であればそれを実行し、そうでなければまた提案グラフを呼ぶことによって、最終的には実行可能な「行動」にたどり着く、というのが基本的な仕組みになります。これによって、計画グラフは自分ができる全ての行動が実行不可である場合を除き、あらゆる「状態」ないし「行動」からさしあたって実行可能な行動を導くことができます。

 もちろん、それが価値ある行動かどうかは、今のところは考えません。ねこは精一杯に生きています。

ねこの天国

 提案グラフを作ることによって、ねこは実行可能な「行動」を確実に得ることができるようになりました。しかしながら、現時点では新たな問題へ直面する度にランダムで行動を選ぶおもしろ計画器であり、それが正しく機能するかは疑問です。

f:id:unifa_tech:20190611181403p:plain:w300
執拗にレーザーを出すねこ

 死にそうだからといってみだりにレーザーを撃つべきではありません。空腹ならばなおさらです。ねこは正しくない行動をした時にそれを知り、正す必要があります。少なくとも来世では。

f:id:unifa_tech:20190611181431p:plain:w300
空腹に打ち震えているねこ

 環境はねこの天国を持ちます。ねこの天国はまたたびの香りのフォグに包まれ、すしと比べて頂点数に優れる缶詰の山と、リアルタイム流体シミュレーションで流れるおやつの川、そして物理演算の宿った荒ぶるおもちゃの大地があります。さておき、全てのねこは死んだとき、その生存時間と自身が持っている提案グラフを天国に送ります。

f:id:unifa_tech:20190611181524p:plain:w300
天国が管理する情報

 天国は直近100件のねこの平均生存時間と、最大で100件の提案グラフを持っています。新しいねこが環境に生まれるとき、天国はねこに自身が持つ提案グラフをランダムで一つ与えます。ねこは天啓を受け、生まれた瞬間から比較的賢いかもしれない状態になります。

f:id:unifa_tech:20190611181548p:plain:w300
天国が持っている中で最もマシな提案グラフ

 これにより、ねこは賢かったり、そうでなかったりする状態で人生を送ります。生きるうちに新たな発見をし、提案グラフに変更が加わるかもしれません。そうして大往生を迎えると、提案グラフと生存時間がまた天国に蓄積されていきます。

 この繰り返しによって提案グラフが100件集まると、天国は「進化」を行います。世代を一つ送り、100件集まった提案グラフを長生きした順に並べ、以下の処理を行います。

範囲 やること
上位10件 そのまま残す
次の20件 ランダムな2件ずつでペアを作る
双方にある辺を残す
片方にしかない辺は30%の確率で残す
次の5件 全ての辺を10%の確率で消す
そのほか 削除する

 この結果、残った提案グラフが次世代のねこたちに与えられます。これらは概ね前世代のご長寿ランキング上位勢ということになりますので、次世代のねこは比較的賢いことが期待できそうな状態から人生をスタートします。そしてそのねこがより長く生き、優秀な提案グラフを次世代に残し続けることによって、提案グラフが改善され、計画器がより適切な計画を立てられるようになります。

 全てのねこが永遠に生きるようになったとき、天国はその役目を終えるでしょう。

f:id:unifa_tech:20190611181846p:plain:w300
まだ天国を必要とするねこ

おわりに

 簡単なものではありますが、ゴール指向の自動計画器と遺伝的ネットワーク計算の学習装置を作ることができました。AIについては全くの門外漢なので調べていてもなるほどわからん状態でしたが、さしあたってねこが動いているので私は満足しています。

 計画器やその学習には様々な手法がありますので、それらを参考に今後も改善を重ねつつ、より賢いねこになってもらえればと思っています。

時間帯被るかどうかから長方形の衝突検知

こんにちは、午睡チェックサーバーエンドエンジニアのちょうです。最近開発で見つかったちょっと難しい問題について話したいです。それは時間帯が被ってるかどうかのチェックです。

時間帯

例えば

  • 午後3時から午後4時
  • 午後5時から午後6時

という2つの時間帯は被らないとし、

  • 午前10時から午後4時
  • 午後3時から午後5時

が被るとしたら、どうやって時間帯が被るかをチェックしますか。

時間帯を表記しやすいために、[15:00, 16:00] は午後3時から午後4時の意味をします。なお、[15:00, 16:00][16:00, 17:00] は被らないとします。

個別のケースを考えるより、すべて可能なケースをここにリストアップしました。

f:id:unifa_tech:20190603190445p:plain

2つの時間帯の関係は全部6ケースあります。以下金色の時間帯1は[S1, E1]、水色の時間帯2は[S2, E2]とします。

  1. 被らない、E1 <= S2
  2. 被る、S1 < S2 < E1
  3. 被る、S2 <= S1 < E1 <= E2
  4. 被る、S1 <= S2 < E2 <= E1
  5. 被る、S1 < E2 < E1
  6. 被らない、E2 <= S1

被るケースが4個あるので、4ケースの一つに当てはまれば被ります。とはいえ、4つのケースに共通点あまりないし、そのままコードにするのは分かりにくいです。

ここで一つのテクニックは被るケース以外のケース、つまり被らないケース、の逆にすれば簡単にできます。

  ALL CASES - <CASE 1> - <CASE 6>
=!<CASE 1>   && !<CASE 6>
=!(E1 <= S2) && !(E2 <= S1)
= (E1 > S2)  &&  (E2 > S1)

実際、↑の条件で被る4つのケース一つ一つチェックしてみれば、すべて合ってることが分かります。もし数学が強い人がちゃんと4つの被るケースの共通点を見つければ、たぶん同じ結果になるでしょう。我々一般人にとって、同じ結果に辿り着けるには、逆思考がキーになります。

長方形の衝突検知

もうひとつ自分が興味を持っていた問題を紹介します。長方形の衝突検知。

f:id:unifa_tech:20190604113432p:plain

長方形の衝突検知はよくゲームで使われるらしいです。例えば、2つのオブジェクトがぶつかるかによってダメージを受けるかなどを決めます。

方法1

時間帯と同じ方法を使えます。金色長方形を長方形1とし、水色長方形は長方形2とする。X軸に長方形1と長方形2が被るかつY軸に長方形1と長方形2が被れば長方形1と長方形2が被る。つまり

長方形1: (x1, y1), (x2, y2)
長方形2: (x3, y3), (x4, y4)
[x1, x2] と [x3, x4] 被る -> (x2 > x3) && (x4 > x1)
[y1, y2] と [y3, y4] 被る -> (y2 > y3) && (y4 > y1)
よって衝突の条件は
(x2 > x3) && (x4 > x1) && (y2 > y3) && (y4 > y1)
方法2

↑以外に、もう一つ方法があります。2つの円が被るかどうかの条件を考えてみましょう。円でしたら中心と中心の距離が2つの円の半径の和より大きいでしたら被らない、小さいでしたら被るということになります。同じように、長方形の中心と中心のX軸の距離が2つの長方形の高さの半分より小さいかつY軸の距離も2つの長方形の幅の半分より小さいでしたら2つの長方形が被る。つまり

f:id:unifa_tech:20190604140657p:plain

長方形1: (x1, y1), (x2, y2)
長方形2: (x3, y3), (x4, y4)
w1 = (x2 - x1), h1 = (y2 - y1)
w2 = (x4 - x3), h2 = (y4 - y3)
中心1 ((x2 + x1) / 2, (y2 + y1) / 2)
中心2 ((x4 + x3) / 2, (y4 + y3) / 2)
ABSは絶対値関数
中心の距離: (
    ABS((x4 + x3) / 2 - (x2 + x1) / 2), 
    ABS((y4 + y3) / 2 - (y2 + y1) / 2)
)
衝突の条件
ABS((x4 + x3) / 2 - (x2 + x1) / 2) < (w1 + w2) / 2 && 
    ABS((y4 + y3) / 2 - (y2 + y1) / 2)) < (h1 + h2) / 2
ABS((x4 + x3) - (x2 + x1)) < (w1 + w2) && 
    ABS((y4 + y3) - (y2 + y1))) < (h1 + h2)
ABS((x4 + x3) - (x2 + x1)) < ((x2 - x1) + (x4 - x3)) && 
    ABS((y4 + y3) - (y2 + y1))) < ((y2 - y1) + (y4 - y3))

条件は2つに減りました。

方法1と方法2が同じなのかは私が答えられないですが、中心の距離で判断するのを理解すればいいと思います。

さいご

いかがでしょうか。たまにこういう数学っぽい問題を解いてみましょうか。普段の開発ではあまりこういう問題が出ないですが、気分転換としていい勉強になると思います。

Vue.jsで複数ページにまたがるフォームをVuexを使わずに実装してみる

滑り込みで東京オリンピックの抽選申し込みを済ませました、Webエンジニアの本間です。 どの日でもよいので抽選に当たって欲しいのですが、全部当たると困ってしまう、なかなか悩ましい気持ちになりました。

さて弊社では、現在開発中のプロジェクトのフロントエンドの実装において Vue.js を使っています。 今回、Vue.jsを使った実装をしている中で、複数ページにまたがるフォームの実装で調査した内容を紹介しようと思います。

続きを読む

sudo実行時のカレントディレクトリや環境変数などの挙動について

おはこんにちばんわ! ひさびさなユニファのインフラのすずきです。

最近八王子から、都心に引っ越してきました。
やはり通勤時間が短いと快適ですよね。
そして先日AWSのRe:Inventのチケット申込みが始まりましたね。
今年は行きたい…い゛ぎたい!!!!

と前置きはおいて今回は2度めのsudo関連のブログです。

前回のsudoの記事はこちら、

tech.unifa-e.com

なんかそこそこ見てもらえてるみたいで、関連記事かけという強いプレッシャーの元今回書くことにしました。

では本題

続きを読む