第一部分在线视频

同学们好

今天我开始讲这个电梯控制的应用问题

在开始讲之前呢我得感谢两个人

一个是清华大学的胡晓强

以及他为首的几个助教

还有我以前的同事现在他自主创业 严雄亮

他们两位在周末的时候帮我画了图

所以我今天才能有这些ppt跟大家讲这个课

电梯控制我们先看这物理对象是什么

有一个大楼有m层楼 有n部电梯

我们现在需要做的是什么呢

设计一个统一的控制系统

来统一控制这个n部电梯

使它来完成这个服务

大家都知道所谓电梯服务

无非就是通过按钮来向电梯提出服务请求

那么按钮呢一共有三种

一种就是楼层上的上升按钮

还有楼层上的下降按钮

还有就是电梯里面的按钮

我们用Fu表示楼层上的按钮

那么Fu(1)就是楼层上上升的这一层的按钮

同样那个Fu(2)Fu(3)等等

楼层的下降我们用Fd表示

那么Fd（i）呢就是在i层楼下降的请求

这个楼层上的

那么电梯呢

因为它一共有n部电梯

所以我们用两个符号

这个方框里面的i是第i层楼

外面的j是表示第j部电梯

那么这几个按钮代表的服务请求是什么呢

楼层上的两个上升要求

有一部电梯

n部电梯里面随便哪一部电梯

到了这个i层然后停下来开门

在上升方向

这个方向一定要对

至于有人上有人下没有

那不是我们能管得了的

然后楼层上的下降按钮是一样的

就是有某一部电梯

到i层来停下来然后把门打开

那么电梯内部的那个按钮呢

就不管升降还是下降了

只要到了那一层把门打开这就算完成服务了

这就是按钮所代表的用户的需求

那么我们这个要设计一个软件来控制它

所以除了用户的需求以外

我们主要考虑的是这个第二种需求

软件需求

我们要设计一个软件

保证电梯的运行

能够提供这些按钮所要求的服务

要做到有求必应

就是说有人按一下去了你就一定要来服务

当然这个所谓的有求必应也不是说限时的

你必须十分钟到

但是也不能太长时间

我今天按了你 你说我明天才来

这都不行

那么在一个合理的时间能够得到服务

这就可以了

那么现在这个控制策略是什么呢

现在我们能够看到

在许多大楼里面都有两部三部几部电梯统一控制的

那么现在的控制策略是什么呢

现在的控制策略是全局控制

这是做软件设计的人统一的一个惯性的思维

就是全局状态 全局时间

所以这个电梯控制呢也没有离开这个老套

还是全局控制

我自己也坐过

你们大家也可能都坐过

就是发现有很多问题

主要那个问题是什么

让这个乘客不高兴的是什么呢

就是眼睁睁的看着一部电梯

从我这过而且方向也对

它就是不停

所以这个是让乘客最不满意的地方

另外我复旦大学的一个朋友

他曾经看了我写的这个

用Petri网来给出的解以后呢

他曾经找电梯公司的人去联系

说你们这个控制是不是考虑考虑这个方案呢

结果电梯公司的人告诉他说

我们只管安电梯

我们不管设计电梯

但是他得到一个信息就是

那样的全局控制最多能够控制六部电梯

多了以后这个全局状态太大了它就控制不了了

为什么全局状态会有这么多的问题

原因就是什么

全局状态的性质

我们不知道什么因素会影响全局状态

影响电梯的运行

这个电梯运行起来没有问题

说从一层到下一层或者到上一层多长时间

这个你心里有数

但是电梯到了某一层开了门以后

要滞留多长时间这就没数了

到底什么因素使它滞留

因素很多尤其是人为的因素

所以无法控制

所以呢下一个状态就很难预测

因此当你在现在已知的这个全局状态下

你认为最好的调度

是让哪一部电梯去提供服务的时候

等下一个状态就变了

你认为最早能够到达那一层的那个电梯

人为的原因或者别的原因没有到

而其他的电梯到了

但是你没有调度

没有让它去提供服务

所以它就过去了

这就是为什么眼睁睁的看着它过去而不停

所以全局状态控制引起的这些矛盾

这些不好的现象

我们怎么判断一个控制是好还是不好呢

不是说实践是检验真理的标准吗

这个咱们实践上看刚才我已经说了不太好

那么应该怎么来判断它好还是不好呢

电梯的用户有两种

一种就是这个电梯的拥有者

他希望这个电梯什么呀

最好是不要空驶

那样耗电而且磨损机器

另外一个呢最好能够满载

就是电梯装满了再走这样效率最高

另一个用户就是乘电梯的人 乘客

这个乘客呢他就相反了

他愿意这里面大概最好就我一个人坐

另外他希望少等待

就是他不希望不管你空驶不空驶

少等待是最好的

那么我们来折中一下这两个

我们为什么要有电梯

电梯就是为乘客服务的

所以那个电梯拥有者提出的要求

什么少空驶 满载

这个是不太合理的要求

优先考虑的是乘客的要求

就是有求必应和少等待

所以少等待比这个少空驶要求是要高的

它有高的优先级

那么当前的策略

我们的全局控制策略不符合这个标准

乘客等待经常看到

有没有空驶这个不知道了

那么我们放弃全局调度

放弃全局调度最直接的就是我们不调度了

最直接的一个方案就是

我就像公共汽车一样的来运行

从一层到二层到三层到四层到m层

掉过头来在一层一层的下

这样保证层层都停你不会等待

不会有从我这过不停的

另外呢你不会看到过而不停的

让你不满意的这种状态

第二种不控制的方法呢

就是出租汽车似的

我把按钮按下去的时间按照时间顺序排成队

排成队以后我就按出租车一样调度

一部电梯去按一次给这个排成队的按钮服务

结果这样怎么样

显然是过而不停是正常的

另外出租汽车不能合乘

但是电梯可以合乘

电梯你有多少人上多少人只要不超载就行

而出租汽车那只能是一伙人自己坐一辆

所以这个出租汽车式的调度

直接从出发地到达目的地中间不停

这显然也是不合适的

所以都不符合刚才我们分析的

有求必应或少等待这个标准

所以这种方法呢就是这样的不调度是不合理的

我们再准确的理解一下少等待和这个空驶

少等待就是指的没有过而不驶不停

我看着它过去它不停

那显然我就等待的时间就长了

少空驶呢

不等于说电梯里面没有人它在运行

电梯里没有人它运行那个不叫空驶

而是空驶什么意思

是指的你这次运行是有目标的

有一个按下去的按钮需要你服务

你去那儿提供服务

比方说电梯在一层你在五层

你想要下来你按了

如果电梯不空驶到五层怎么接你呀

所以从一层到五层

即便里面没有人坐

那也不能叫空驶

因为它运行是有目标的

是到第五层去为下楼的乘客服务

所以空驶是应该这样理解

有目的的 有目标的运行就不叫空驶

那么咱们放弃全局控制

又不能像刚才那样的

出租汽车式的 公共汽车式的控制

那怎么办呢

咱们Petri网有个基本的原理就是局部确定

放弃全局

用Petri网的特点就是没有全局控制

那么局部确定是Petri网的核心思想之一

我们就用局部确定这个方法

来设计我们的电梯控制

第一条局部控制 局部

对于这个电梯来说

n部电梯是全部

而一部电梯是局部

所以我们呢

可以让一部电梯独立运行根本不考虑其他的

就是一部电梯它自己像自治区一样的自治

然后自治它的这个运行方案是什么呢

就是我写的这四句话

先内后外 楼层顺带

是无活找活

然后主动不怠

什么意思

如果我这个电梯里面有电梯内部的按钮按下了

我就不管楼层上有没有按钮

我就为我电梯内部的按钮提供服务

这样也不是说楼层上的你就不管了

楼层顺带

如果我从你这一层过

你这有正好方向合适的按钮按下了

那么我就捎带着把你带上去

我停但是我不是直接来为你服务的

这叫楼层顺带

我们不是有句话叫搂草打兔子吗

我们现在搂的是草

但是你这个兔子在这我看见了

我也把你给打了

这叫楼层顺带

如果这个电梯里面没有按钮按下去了

也就是我电梯现在没有运行的目标了

那么这个时候我就来找活

这叫无活找活

找到活以后

就干那个活去

去提供你所找到的要提供的服务

主动不怠这是说电梯的一个特点

人可能会偷懒

你给他什么活

人看不见的时候

他去坐一会喝点水休息休息

电梯不会

这个电梯是主动的提供服务

它不会懈怠的

所以这个每部电梯自主独立

它的运行原则就是

先内后外 楼层顺带 无活找活

然后呢主动的不会放弃

因为我们只考虑一部电梯

所以那个电梯里面的按钮我们就用L（i）来表示

那个J就不需要了

因为我们只考虑一部电梯

这就是电梯自制

楼层上的button是大家共享的

谁从这儿过谁提供服务

不预先说好是我来还是你来

所以不需要调度但是呢提供了更好的服务

那么局部确定的第二个局部

我们在一个楼层上面有两个运行方向

一个是上 一个是下

那么上和下呢它是镜面对称的

往上上一层跟往下下一层

正好对应于楼层这个地板

正好是镜面对称

所以我们只需要考虑一个

上升的方向下降的方向

我们做一个对称的映射就行了

比方说把i+1上一层变成i-1

它就变成下一层了

那么局部确定的第三个就是楼层

我们一共有m层楼

但是这一层或上一层再上一层

每一层楼它那个变迁它的运行都是一样的

共享同样的动作

所以我们不需要考虑m层

只需要考虑一层就行

考虑电梯在这一层上面都有哪些动作

把这些动作描述好

在这一层我们分析清楚

然后通过共享的楼层的状态元素

就可以把这一层或上一层或下一层联系在一起了

因此呢我们这个m层楼呢也只需要考虑一层楼

所以这样一来我们(M,N,2)这样的一个复杂度呢

就变成(1，1，1)了

一部电梯 一个方向 一层

有了这个局部确定的思想以后

我们就来设计了

设计步骤是分四步

第一步我们先在第i层楼上升的方向

设计找出它所有的变迁来

然后把这些变迁的外延找出来

然后第三步通过这些共享的外延

把所有的变迁联系在一起变成一个系统

然后由于它们共享这个S元素 共享库所

因此呢就有可能有冲突

那么我们把冲突给消解掉

然后第四步

根据我们的正确性的标准就是少空驶有求必应

我们来证明它确实符合这两个要求

我们看第一步

设计上升方向的变迁

上升方向有几个动作

在一层楼它有可能上升到上一层

所以有一个升

另外有一个停

在这一层我到了 我要停下来

有停的需求那我停下来

开门让客人下去或者上来

所以停 开

然后呢当然就要把门关上

然后你才能进一步的上升或者下降

假定你在这一层没有需求

你不知道还有什么需求的时候

我们说过要找活

那么找活呢也是在这一层需要做的事情

先内就是我先看看

我这电梯里面有没有按下去的按钮

如果没有我再找楼层的

楼层的那我先找上升方向的

如果没有上升方向的

我再看看楼层上面有没有下降方向的

比如说在第二层

在第五层有下降的要求

我在第二层必须要上去接他对吧

所以虽然他的要求是下降

但是你还得先上去才能为他服务

所以这也算上升方向电梯的活

如果这些都没有

那你就要改变方向

把它改成下降的方向

看看下降的方向有没有服务请求

所以这一个楼层上面呢就有这么多的

几个呀

一共有这么六七个吧

或者是七八个变迁

好 我们现在给这个变迁命名

变迁的名字

上升方向的变迁

我都用个小写的u_作为这些变迁的前缀

那么下降的用小写的d_作为变迁的前缀

所以u_stop(i)或者d_stop(i)

就是上升方向停在i层下降方向停在i层

因为你停下来肯定要开门

我们没有必要关心这个细节

所以把这个开门呢

这个动作就合并到stop里面去了

所以u_stop(i)表示在上升方向

在i层停下来把门打开

然后u_close

d_close就是在i层把这个门关上

在上升方向或者是下降方向

然后u_d这就是从上升方向改到下降方向

这个d_u就是从下降方向改向改到上升方向

所以这个变迁的命名的规律就是这样的

库所 也就是S元素怎么命名呢

上升方向的库所我们就用U_作为它的前缀

下降方向呢是用D_作为它的前缀

所以U_at(i)就是电梯呢在i层

这个在i层有两种可能性

一种是从下面一层上来了

是上升方向

或者是在这一层开了门以后又关了门停在i层

所以这个U_at(i)有可能是从这通过

也有可能是停在这

U_open就是停在这门开着的

可以上下

这就是库所的命名规律

另外还有两个呢是没有前缀的变迁

一个是up就是上升 上升一层

另外是dn就是down 是下降一层

这是两个没有前缀的

我们看一个例子

咱们来理解一下这个电梯怎么运行的

假定我们现在的电梯停在二层是上升方向

这个时候电梯里面的第五层的按钮按下了

L(5)有token

Fu(4)有token

就是第四层楼层上升的按钮按下了

第八层下降的按钮按下了

第十一层下降的按钮按下了

那么这个时候我们的电梯怎么运行呢

我们要先为L(5)提供服务

L(5)服务怎么办呢

从二层上升到三层所以up(2)

然后up(3)从三层上升到四层

然后up(4)从四层上升到五层

然后呢u_stop(5)停在五层了

然后我们要顺带

在通过第四层的时候

第四层上升的钮按下了

它是上升方向的这个服务需求

所以呢在第四层我们要停下来

给这个Fu(4)提供服务这叫顺带

所以当电梯到达第四层的时候

它会u_stop(4)就是停在四层

开了门 让人上或者让人下

然后呢在u_close(4)就是把门关上

这个时候电梯就在第四层

那个L(5)的服务还没有完成

所以它要继续完成这个服务

然后呢第四层上升一层到了第五层

因为第五层有服务需求是L(5)要求的

所以要stop L(5)

然后呢在第五层再关门u_close(5)

然后这个时候电梯呢

就已经停在五层了

停在五层以后

这个时候还有剩下的没有服务的是什么呢

Fu(8)和Fd(11)这两个还没有服务

这个时候我们就要找

因为从这个第五层上升到第八层

这个不具有原子性

它可能顺带服务

所以我们必须要找的是什么呢

一层一层的上升的这种服务

所以我们要找活

找呢先找上升的

找到了Fu(8)

这个怎么服务呢

从五层上升到六层 上升到七层 上升到八层

然后停在八层

然后开门这个停下来是包括开门的

然后关门

然后就完成了Fu(8)的这个服务

至于第八层上升这个按钮的人

还在不在 上不上来

上来以后按着什么钮这是咱们不知道

咱们先不管它就是假定没有人上来

那么这个时候呢我要继续找活

就只剩下一个Fd(11)了

为了提供在11层下降的服务

我还必须要继续上升

这个上升就是从八层上升到九层

九层上升到十层

十层上升到十一层

然后停下来

然后开门 关门到了11层

但是别忘了这个电梯的方向仍然是上升的方向

上升的方向并没有完成对Fd(11)的这个服务请求

因为Fd(11)要求你某一部电梯停在第11层

方向是下降的

所以我们这个电梯要继续上升方向的服务

假定这个时候13层有人

Fu(13)按下去了

那么我们要继续的提供Fu(13)的服务

到了这个十三层我就不重复了

它上升到13层停下来 上升方向

假定这个时候它提供了这个服务以后

它就要调转方向改变方向来服务

这个时候它必须要记住

我承诺了我要服务Fd(11)

所以我要到第十一层去

再把门打开

这就完成了Fd(11)的服务

那么整个电梯运行我们用这个例子呢

就可以来理解一下什么叫先内后外

什么叫楼层顺带

什么叫无活找活对吧

另外什么叫主动不怠

我一直在动 没有停的时候

没有说我停在某一层什么事也不干

没有

停下来没活了我就找活

那么在下降方向找活呢

为的是什么呀

要提供完成这个Fd(11)的服务

这个时候呢必须要考虑这个不能忘记它

这个我就不去多说了

就是一定要停在十一层下降方向