def _dijkstra(self):
    '\n        The dijkstra algorithm.\n        Was called beam search to be consistent with existing work.\n        But it actually finds the Exact K paths with smallest listener log_prob.\n        :return:\n        [{\n            "scan": XXX\n            "instr_id":XXX,\n            \'instr_encoding": XXX\n            \'dijk_path\': [v1, v2, ..., vn]      (The path used for find all the candidates)\n            "paths": {\n                    "trajectory": [viewpoint_id1, viewpoint_id2, ..., ],\n                    "action": [act_1, act_2, ..., ],\n                    "listener_scores": [log_prob_act1, log_prob_act2, ..., ],\n                    "visual_feature": [(f1_step1, f2_step2, ...), (f1_step2, f2_step2, ...)\n            }\n        }]\n        '

    def make_state_id(viewpoint, action):
        return ('%s_%s' % (viewpoint, str(action)))

    def decompose_state_id(state_id):
        (viewpoint, action) = state_id.split('_')
        action = int(action)
        return (viewpoint, action)
    obs = self.env._get_obs()
    batch_size = len(obs)
    results = [{'scan': ob['scan'], 'instr_id': ob['instr_id'], 'instr_encoding': ob['instr_encoding'], 'dijk_path': [ob['viewpoint']], 'paths': []} for ob in obs]
    (seq, seq_mask, seq_lengths, perm_idx) = self._sort_batch(obs)
    recover_idx = np.zeros_like(perm_idx)
    for (i, idx) in enumerate(perm_idx):
        recover_idx[idx] = i
    (ctx, h_t, c_t) = self.encoder(seq, seq_lengths)
    (ctx, h_t, c_t, ctx_mask) = (ctx[recover_idx], h_t[recover_idx], c_t[recover_idx], seq_mask[recover_idx])
    id2state = [{make_state_id(ob['viewpoint'], (- 95)): {'next_viewpoint': ob['viewpoint'], 'running_state': (h_t[i], h_t[i], c_t[i]), 'location': (ob['viewpoint'], ob['heading'], ob['elevation']), 'feature': None, 'from_state_id': None, 'score': 0, 'scores': [], 'actions': []}} for (i, ob) in enumerate(obs)]
    visited = [set() for _ in range(batch_size)]
    finished = [set() for _ in range(batch_size)]
    graphs = [utils.FloydGraph() for _ in range(batch_size)]
    ended = np.array(([False] * batch_size))
    for _ in range(300):
        smallest_idXstate = [(max(((state_id, state) for (state_id, state) in id2state[i].items() if (state_id not in visited[i])), key=(lambda item: item[1]['score'])) if (not ended[i]) else next(iter(id2state[i].items()))) for i in range(batch_size)]
        for (i, (state_id, state)) in enumerate(smallest_idXstate):
            assert (ended[i] or (state_id not in visited[i]))
            if (not ended[i]):
                (viewpoint, action) = decompose_state_id(state_id)
                visited[i].add(state_id)
                if (action == (- 1)):
                    finished[i].add(state_id)
                    if (len(finished[i]) >= args.candidates):
                        ended[i] = True
        (h_ts, h1s, c_ts) = zip(*(idXstate[1]['running_state'] for idXstate in smallest_idXstate))
        (h_t, h1, c_t) = (torch.stack(h_ts), torch.stack(h1s), torch.stack(c_ts))
        for (i, (state_id, state)) in enumerate(smallest_idXstate):
            next_viewpoint = state['next_viewpoint']
            scan = results[i]['scan']
            (from_viewpoint, heading, elevation) = state['location']
            self.env.env.sims[i].newEpisode(scan, next_viewpoint, heading, elevation)
        obs = self.env._get_obs()
        for (i, ob) in enumerate(obs):
            viewpoint = ob['viewpoint']
            if (not graphs[i].visited(viewpoint)):
                for c in ob['candidate']:
                    next_viewpoint = c['viewpointId']
                    dis = self.env.distances[ob['scan']][viewpoint][next_viewpoint]
                    graphs[i].add_edge(viewpoint, next_viewpoint, dis)
                graphs[i].update(viewpoint)
            results[i]['dijk_path'].extend(graphs[i].path(results[i]['dijk_path'][(- 1)], viewpoint))
        (input_a_t, f_t, candidate_feat, candidate_leng) = self.get_input_feat(obs)
        (h_t, c_t, alpha, logit, h1) = self.decoder(input_a_t, f_t, candidate_feat, h_t, h1, c_t, ctx, ctx_mask, False)
        candidate_mask = utils.length2mask(candidate_leng)
        logit.masked_fill_(candidate_mask, (- float('inf')))
        log_probs = F.log_softmax(logit, 1)
        (_, max_act) = log_probs.max(1)
        for (i, ob) in enumerate(obs):
            current_viewpoint = ob['viewpoint']
            candidate = ob['candidate']
            (current_state_id, current_state) = smallest_idXstate[i]
            (old_viewpoint, from_action) = decompose_state_id(current_state_id)
            assert (ob['viewpoint'] == current_state['next_viewpoint'])
            if ((from_action == (- 1)) or ended[i]):
                continue
            for j in range((len(ob['candidate']) + 1)):
                modified_log_prob = log_probs[i][j].detach().cpu().item()
                new_score = (current_state['score'] + modified_log_prob)
                if (j < len(candidate)):
                    next_id = make_state_id(current_viewpoint, j)
                    next_viewpoint = candidate[j]['viewpointId']
                    trg_point = candidate[j]['pointId']
                    heading = (((trg_point % 12) * math.pi) / 6)
                    elevation = ((((trg_point // 12) - 1) * math.pi) / 6)
                    location = (next_viewpoint, heading, elevation)
                else:
                    next_id = make_state_id(current_viewpoint, (- 1))
                    next_viewpoint = current_viewpoint
                    location = (current_viewpoint, ob['heading'], ob['elevation'])
                if ((next_id not in id2state[i]) or (new_score > id2state[i][next_id]['score'])):
                    id2state[i][next_id] = {'next_viewpoint': next_viewpoint, 'location': location, 'running_state': (h_t[i], h1[i], c_t[i]), 'from_state_id': current_state_id, 'feature': (f_t[i].detach().cpu(), candidate_feat[i][j].detach().cpu()), 'score': new_score, 'scores': (current_state['scores'] + [modified_log_prob]), 'actions': (current_state['actions'] + [(len(candidate) + 1)])}
        for i in range(batch_size):
            if (len(visited[i]) == len(id2state[i])):
                ended[i] = True
        if ended.all():
            break
    for i in range(batch_size):
        results[i]['dijk_path'].extend(graphs[i].path(results[i]['dijk_path'][(- 1)], results[i]['dijk_path'][0]))
    '\n            "paths": {\n                "trajectory": [viewpoint_id1, viewpoint_id2, ..., ],\n                "action": [act_1, act_2, ..., ],\n                "listener_scores": [log_prob_act1, log_prob_act2, ..., ],\n                "visual_feature": [(f1_step1, f2_step2, ...), (f1_step2, f2_step2, ...)\n            }\n        '
    for (i, result) in enumerate(results):
        assert (len(finished[i]) <= args.candidates)
        for state_id in finished[i]:
            path_info = {'trajectory': [], 'action': [], 'listener_scores': id2state[i][state_id]['scores'], 'listener_actions': id2state[i][state_id]['actions'], 'visual_feature': []}
            (viewpoint, action) = decompose_state_id(state_id)
            while (action != (- 95)):
                state = id2state[i][state_id]
                path_info['trajectory'].append(state['location'])
                path_info['action'].append(action)
                path_info['visual_feature'].append(state['feature'])
                state_id = id2state[i][state_id]['from_state_id']
                (viewpoint, action) = decompose_state_id(state_id)
            state = id2state[i][state_id]
            path_info['trajectory'].append(state['location'])
            for need_reverse_key in ['trajectory', 'action', 'visual_feature']:
                path_info[need_reverse_key] = path_info[need_reverse_key][::(- 1)]
            result['paths'].append(path_info)
    return results
The dijkstra algorithm.
Was called beam search to be consistent with existing work.
But it actually finds the Exact K paths with smallest listener log_prob.
:return:
[{
    "scan": XXX
    "instr_id":XXX,
    'instr_encoding": XXX
    'dijk_path': [v1, v2, ..., vn]      (The path used for find all the candidates)
    "paths": {
            "trajectory": [viewpoint_id1, viewpoint_id2, ..., ],
            "action": [act_1, act_2, ..., ],
            "listener_scores": [log_prob_act1, log_prob_act2, ..., ],
            "visual_feature": [(f1_step1, f2_step2, ...), (f1_step2, f2_step2, ...)
    }
}]
def _dijkstra(self):
    '\n        The dijkstra algorithm.\n        Was called beam search to be consistent with existing work.\n        But it actually finds the Exact K paths with smallest listener log_prob.\n        :return:\n        [{\n            "scan": XXX\n            "instr_id":XXX,\n            \'instr_encoding": XXX\n            \'dijk_path\': [v1, v2, ..., vn]      (The path used for find all the candidates)\n            "paths": {\n                    "trajectory": [viewpoint_id1, viewpoint_id2, ..., ],\n                    "action": [act_1, act_2, ..., ],\n                    "listener_scores": [log_prob_act1, log_prob_act2, ..., ],\n                    "visual_feature": [(f1_step1, f2_step2, ...), (f1_step2, f2_step2, ...)\n            }\n        }]\n        '

    def make_state_id(viewpoint, action):
        return ('%s_%s' % (viewpoint, str(action)))

    def decompose_state_id(state_id):
        (viewpoint, action) = state_id.split('_')
        action = int(action)
        return (viewpoint, action)
    obs = self.env._get_obs()
    batch_size = len(obs)
    results = [{'scan': ob['scan'], 'instr_id': ob['instr_id'], 'instr_encoding': ob['instr_encoding'], 'dijk_path': [ob['viewpoint']], 'paths': []} for ob in obs]
    (seq, seq_mask, seq_lengths, perm_idx) = self._sort_batch(obs)
    recover_idx = np.zeros_like(perm_idx)
    for (i, idx) in enumerate(perm_idx):
        recover_idx[idx] = i
    (ctx, h_t, c_t) = self.encoder(seq, seq_lengths)
    (ctx, h_t, c_t, ctx_mask) = (ctx[recover_idx], h_t[recover_idx], c_t[recover_idx], seq_mask[recover_idx])
    id2state = [{make_state_id(ob['viewpoint'], (- 95)): {'next_viewpoint': ob['viewpoint'], 'running_state': (h_t[i], h_t[i], c_t[i]), 'location': (ob['viewpoint'], ob['heading'], ob['elevation']), 'feature': None, 'from_state_id': None, 'score': 0, 'scores': [], 'actions': []}} for (i, ob) in enumerate(obs)]
    visited = [set() for _ in range(batch_size)]
    finished = [set() for _ in range(batch_size)]
    graphs = [utils.FloydGraph() for _ in range(batch_size)]
    ended = np.array(([False] * batch_size))
    for _ in range(300):
        smallest_idXstate = [(max(((state_id, state) for (state_id, state) in id2state[i].items() if (state_id not in visited[i])), key=(lambda item: item[1]['score'])) if (not ended[i]) else next(iter(id2state[i].items()))) for i in range(batch_size)]
        for (i, (state_id, state)) in enumerate(smallest_idXstate):
            assert (ended[i] or (state_id not in visited[i]))
            if (not ended[i]):
                (viewpoint, action) = decompose_state_id(state_id)
                visited[i].add(state_id)
                if (action == (- 1)):
                    finished[i].add(state_id)
                    if (len(finished[i]) >= args.candidates):
                        ended[i] = True
        (h_ts, h1s, c_ts) = zip(*(idXstate[1]['running_state'] for idXstate in smallest_idXstate))
        (h_t, h1, c_t) = (torch.stack(h_ts), torch.stack(h1s), torch.stack(c_ts))
        for (i, (state_id, state)) in enumerate(smallest_idXstate):
            next_viewpoint = state['next_viewpoint']
            scan = results[i]['scan']
            (from_viewpoint, heading, elevation) = state['location']
            self.env.env.sims[i].newEpisode(scan, next_viewpoint, heading, elevation)
        obs = self.env._get_obs()
        for (i, ob) in enumerate(obs):
            viewpoint = ob['viewpoint']
            if (not graphs[i].visited(viewpoint)):
                for c in ob['candidate']:
                    next_viewpoint = c['viewpointId']
                    dis = self.env.distances[ob['scan']][viewpoint][next_viewpoint]
                    graphs[i].add_edge(viewpoint, next_viewpoint, dis)
                graphs[i].update(viewpoint)
            results[i]['dijk_path'].extend(graphs[i].path(results[i]['dijk_path'][(- 1)], viewpoint))
        (input_a_t, f_t, candidate_feat, candidate_leng) = self.get_input_feat(obs)
        (h_t, c_t, alpha, logit, h1) = self.decoder(input_a_t, f_t, candidate_feat, h_t, h1, c_t, ctx, ctx_mask, False)
        candidate_mask = utils.length2mask(candidate_leng)
        logit.masked_fill_(candidate_mask, (- float('inf')))
        log_probs = F.log_softmax(logit, 1)
        (_, max_act) = log_probs.max(1)
        for (i, ob) in enumerate(obs):
            current_viewpoint = ob['viewpoint']
            candidate = ob['candidate']
            (current_state_id, current_state) = smallest_idXstate[i]
            (old_viewpoint, from_action) = decompose_state_id(current_state_id)
            assert (ob['viewpoint'] == current_state['next_viewpoint'])
            if ((from_action == (- 1)) or ended[i]):
                continue
            for j in range((len(ob['candidate']) + 1)):
                modified_log_prob = log_probs[i][j].detach().cpu().item()
                new_score = (current_state['score'] + modified_log_prob)
                if (j < len(candidate)):
                    next_id = make_state_id(current_viewpoint, j)
                    next_viewpoint = candidate[j]['viewpointId']
                    trg_point = candidate[j]['pointId']
                    heading = (((trg_point % 12) * math.pi) / 6)
                    elevation = ((((trg_point // 12) - 1) * math.pi) / 6)
                    location = (next_viewpoint, heading, elevation)
                else:
                    next_id = make_state_id(current_viewpoint, (- 1))
                    next_viewpoint = current_viewpoint
                    location = (current_viewpoint, ob['heading'], ob['elevation'])
                if ((next_id not in id2state[i]) or (new_score > id2state[i][next_id]['score'])):
                    id2state[i][next_id] = {'next_viewpoint': next_viewpoint, 'location': location, 'running_state': (h_t[i], h1[i], c_t[i]), 'from_state_id': current_state_id, 'feature': (f_t[i].detach().cpu(), candidate_feat[i][j].detach().cpu()), 'score': new_score, 'scores': (current_state['scores'] + [modified_log_prob]), 'actions': (current_state['actions'] + [(len(candidate) + 1)])}
        for i in range(batch_size):
            if (len(visited[i]) == len(id2state[i])):
                ended[i] = True
        if ended.all():
            break
    for i in range(batch_size):
        results[i]['dijk_path'].extend(graphs[i].path(results[i]['dijk_path'][(- 1)], results[i]['dijk_path'][0]))
    '\n            "paths": {\n                "trajectory": [viewpoint_id1, viewpoint_id2, ..., ],\n                "action": [act_1, act_2, ..., ],\n                "listener_scores": [log_prob_act1, log_prob_act2, ..., ],\n                "visual_feature": [(f1_step1, f2_step2, ...), (f1_step2, f2_step2, ...)\n            }\n        '
    for (i, result) in enumerate(results):
        assert (len(finished[i]) <= args.candidates)
        for state_id in finished[i]:
            path_info = {'trajectory': [], 'action': [], 'listener_scores': id2state[i][state_id]['scores'], 'listener_actions': id2state[i][state_id]['actions'], 'visual_feature': []}
            (viewpoint, action) = decompose_state_id(state_id)
            while (action != (- 95)):
                state = id2state[i][state_id]
                path_info['trajectory'].append(state['location'])
                path_info['action'].append(action)
                path_info['visual_feature'].append(state['feature'])
                state_id = id2state[i][state_id]['from_state_id']
                (viewpoint, action) = decompose_state_id(state_id)
            state = id2state[i][state_id]
            path_info['trajectory'].append(state['location'])
            for need_reverse_key in ['trajectory', 'action', 'visual_feature']:
                path_info[need_reverse_key] = path_info[need_reverse_key][::(- 1)]
            result['paths'].append(path_info)
    return results