美文网首页
使用ABT(The asynchronous backtrack

使用ABT(The asynchronous backtrack

作者: 学习编程王同学 | 来源:发表于2019-12-15 23:15 被阅读0次

    本文代码点击这里下载。

    将4个皇后放入4x4的棋盘中,修改4个皇后的位置,使他们不能“立即”攻击对方。这里我们假设4个皇后被放置在不同的行中,仅能修改4个皇后的列的位置。

    假设我们4个皇后的id依次是A1,A2,A3和A4,它们的优先级依次是1,2,3和4,它们的位置依次是(1,1),(2,1),(3,1)和(4,1)。算法仅能修改它们所在的列。最终使它们无法一步攻击彼此。

    四皇后问题:1-2循环
    • 循环1. A1发Ok?信号给A2,A3和A4,A2发Ok?信号给A3和A4,A3发Ok?信号给A4.
    • 循环2. A2收到A1的Ok?信号后,发现自己目前的位置与A1有冲突,于是进行重新选了一个位置——(2,3),并将新位置通过Ok?信号发送给A3和A4. A3收到A1和A2的Ok?信号后,发现自己目前的位置与A1和A2有冲突,于是进行重新选了一个位置——(3,4),并将新位置通过Ok?信号发送给A4. A4收到A1,A2和A3的Ok?信号后,发现自己目前的位置与A1,A2和A3有冲突,但是无法找到可行的位置,于是发送Nogood信号给自己的上级——A3,并将A3的位置从自己的agent_view表中抹去,更新了自己的位置——(4,2).
    四皇后问题:3-5循环
    • 循环3. A3收到了A2的Ok?信号,无法找到可行的位置,于是发送Nogood信号给自己的上级——A2,并将A2的位置从自己的agent_view表中抹去,为自己重新分配了位置(虽然与原先一样,因为A2被抹去后该位置不再非法)——(3,4). A3收到了A4的Nogood信号,但是由于A4发来的Nogood信号与自己的agent_view表中的数据不一致(A4在发送此Nogood信号时认为A1,A2和A3还都在第1列,因此对此Nogood信号不作理会。A4收到了Ok?信号,但其位置并不非法,因此不作理会。
    • 循环4. A2收到了A3的Nogood信号,为自己重新分配了位置——(2,4),并通过Ok?信号告知A3和A4.
    • 循环5. A3收到了A2的Ok?信号,为自己重新分配了位置——(3,2),并通过Ok?信号告知A4. A4收到了A2的Ok?信号,无法找到可行的位置,于是发送Nogood信号给A3,并将A3的位置从自己的agent_view表中抹去,为自己重新分配了位置——(3,4).

    如此这般循环,找到一个可行方案。

    主函数部分代码如下。

    while len(ok_set) != 0 or len(nogood_set) != 0:
        for agent in agents:
            agent.handle_ok()
            agent.handle_nogood()
    

    每次循环中,每个智能体都要处理自身收到的Ok?和Nogood信号,当没有信号在网络中传递时,程序结束。

    处理Ok?信号函数的部分代码如下。

    def handle_ok(self, it, ok_set, nogood_set):
        del_list = []
        i = 0
        for ok in ok_set:
            if ok.it == it - 1 and ok.receiver_id == self.id:
                print(self.id, '处理', ok)
                self.agent_view[ok.sender_id] = ok.pose
                del_list.append(i)
            i += 1
        for i in range(len(del_list)):
            # 由于i是被从小到大添加到del_list中的,因此可以这样做
            del ok_set[del_list[i]]
            for j in range(i + 1, len(del_list)):
                del_list[j] -= 1
        self.check_agent_view(it, ok_set, nogood_set, False)
    

    可以看到,程序的实现方法是:收集上一循环中自己作为接收方的Ok?信号,并且将其添加到自己的agent_view中,最后检查自己的值(check_agent_view)。

    处理Nogood信号函数的部分代码如下。

    def handle_nogood(self, it, ok_set, nogood_set):
        del_list = []
        i = 0
        ignore = False
        for nogood in nogood_set:
            if nogood.it == it - 1 and nogood.receiver_id == self.id:
                del_list.append(i)
                ignore = self.ignore_nogood(nogood)
                if not ignore:
                    print(self.id, '处理', nogood)
                    self.add_nogood(nogood.agent_view)
                else:
                    print(self.id, '忽略', nogood)
            i += 1
        for i in range(len(del_list)):
            # 由于i是被从小到大添加到del_list中的,因此可以这样做
            del nogood_set[del_list[i]]
            for j in range(i + 1, len(del_list)):
                del_list[j] -= 1
        # 没有检查是否是neighbor的步骤
        self.check_agent_view(it, ok_set, nogood_set, ignore)
    

    与处理Ok?信号的过程比较类似,不同在于,如果Nogood信号中的内容与自己agent_view表中内容不相符,该Nogood信号会被丢弃。

    check_agent_view函数的部分代码如下。

    def check_agent_view(self, it, ok_set, nogood_set, send_ok):
        old_pose = [self.pose.x, self.pose.y]
        cps = np.random.permutation(range(1, self.pars['map_width'] + 1)).tolist()
        k = 0
        is_consistent, inconsistent_id = self.check_consistent()
        while not is_consistent and k < len(cps):
            self.pose.y = cps[k]
            is_consistent, inconsistent_id = self.check_consistent()
            k += 1
        if not is_consistent:
            if self.priority == 1:
                print('无解')
                sys.exit()
            self.backtrack(it, ok_set, nogood_set)
        else:
            if old_pose != [self.pose.x, self.pose.y] or send_ok:
                receivers_id = self.get_ok_receivers(self.priority)
                for receiver in receivers_id:
                    ok_set.append(signals.Ok(it, self.id, receiver, copy.deepcopy(self.pose)))
    

    可以看出,如果自己的位置是非法的,那么智能体应寻找新的位置,并且将新的位置发送给下一级智能体。

    回溯(backtrack)函数部分代码如下。

    def backtrack(self, it, ok_set, nogood_set):
        # 怎样判断nogood已经全部出现是一个问题
        # !!! 此处的方法存疑
        if len(self.nogood_list) >= self.pars['map_width'] ** self.pose.x:
            print('无解')
            sys.exit()
        receiver_id = self.get_nogood_receiver(self.priority)
        nogood_set.append(signals.Nogood(it, self.id, receiver_id, copy.deepcopy(self.agent_view)))
        if receiver_id in self.agent_view.keys():
            del self.agent_view[receiver_id]
        self.check_agent_view(it, ok_set, nogood_set, True)
    

    回溯过程会判断整个算法是否已经无解。如果还无法判断是否无解,那么就将Nogood表中优先级最低的智能体的Nogood去掉,并发送Nogood信号给那个智能体,并重新检查自己的值(check_agent_view)。

    请注意下面的代码:

    def check_agent_view(self, it, ok_set, nogood_set, send_ok):
    

    check_agent_view函数中有一个send_ok参数,如果该参数为True,则该智能体的位置会被Ok?信号发送到下一级智能体中。如果智能体在check_agent_view过程中发现自己的值与进入该过程前的值不一致,那么它会发送Ok?信号。那么这个参数起什么作用呢?可以看到,在下面两句中,这个参数可能被赋值为True

    def handle_nogood(self, it, ok_set, nogood_set):
        self.check_agent_view(it, ok_set, nogood_set, ignore)
    def backtrack(self, it, ok_set, nogood_set):
        self.check_agent_view(it, ok_set, nogood_set, True)
    

    先来看看handle_nogood的情况,我们假设3个智能体A->B->C。在一次循环中,A发送Ok?信号给B和C,C发送Nogood信号给B。再次循环中,B发现自己目前的位置是合法的,而C的Nogood信号被忽略,也就是B没有改变的自己的位置,也没有任何信号发出;C收到Ok?信号后,发现自己目前的位置不合法,于是换了新的位置,但是与当前B位置冲突,但是由于上一次循环中,C在发送Nogood信号前把B的位置抹去了,因此C并不知情。因此,此时出现了一种奇怪的现象:B与C的位置是矛盾的,网络中却没有信号了。为了避免这种情况的发生,如果Nogood信号被忽略了(ignore==True),那么send_ok位被赋值位True,即B一定会发送Ok?信号给C。

    再来看看backtrack过程得情况,我们假设有一个智能体收到了Nogood信号,在check_agent_view过程中,它改变了自己的位置,但是仍然无法找到合法的位置,此时进入backtrack过程,此时它的位置与处理Nogood信号前位置不一样(即它已经更改了自己的位置)。接下来,它在backtrack过程中发送了Nogood信号,并且将某一上级智能体的位置抹去,便又进入check_agent_view过程。当它目前的位置是合法的时候(因为某一上级智能体的位置被抹去了),它不会发送Ok?信号给下一级智能体(因为在此次check_agent_view过程中位置没变)。但是,它目前的位置与最开始相比,已经改变了,因此此时需要把send_ok设置为True

    相关文章

      网友评论

          本文标题:使用ABT(The asynchronous backtrack

          本文链接:https://www.haomeiwen.com/subject/aizlnctx.html