2Д планировщик дискретного движения


Я пишу 2Д дискретных планировщик движения для задачи с конкретными инструкциями. Инструкции для поискового алгоритма содержится исключительно в строкой документации для search функция.

Моими главными задачами кодекса являются следующие:

  • Я получаю сложности этот код правильный ( О(Н) )?
  • Документация в комплекте?

Пожалуйста, сделайте какие-либо рекомендации вам ознакомиться с соответствующим, при условии, что они придерживаются инструкций алгоритма поиска.

#!/usr/bin/env python

import numpy as np

class RandomPlanner(object):

    """Random 2D discrete motion planner.

    Args:
        max_step_number (int): Maximum number of steps in search path before
            search fails. Also memory length is determined by
            sqrt(max_step_number).

    Attributes:
        max_step_number (int): Maximum number of steps in search path before
            search fails. Also memory length is determined by
            sqrt(max_step_number).

    """

    def __init__(self, max_step_number):
        self.max_step_number = max_step_number

    def search(self, world_state, robot_pose, goal_pose):
        """Random based discrete motion planner.

        This search algorithm tries to fina a path to the goal by randomly
        moving in the environment (only orthogonal moves are legal). If the
        planner can not find an acceptable solution in less than
        max_step_number, the search fails.

        The random planner has a short memory, never attempting to visit a cell
        that was visited in the last sqrt(max_step_number) steps except if this
        is the only available option.

        Complexity of this algorithm is O(N) where N is the max_step_number.

        Args:
            world_state (2D array): Grid representation of the environment. The
                value 0 indicates a navigable space and the value 1 indicates
                an occupied/obstacle space.
            robot_pose (2-tuple): Indices (x, y) represent the
                current pose of the robot in the world_state coordinate system.
            goal_pose (2-tuple): Indices (x, y) represent the goal
                in the world_state coordinate system.

        Returns:
            List of tuple (x, y) representing a path from the robot_pose to the
            goal_pose in world_state if successful. None if no path has been
            found.

        Raises:
            AssertionError: if arguments are not of correct shape.

        """
        assert world_state.ndim == 2
        assert len(robot_pose) == 2
        assert len(goal_pose) == 2

        # Append column and row of 1's to enforce boundaries
        # Note this also enforces the left and top boundaries because an
        # index of -1 will also map to the appended row or column
        world_append = np.c_[world_state, np.ones(world_state.shape[0])]
        world_append = np.r_[world_append, np.ones((1,world_append.shape[1]))]

        # Init path list
        path = [robot_pose]

        while len(path) < self.max_step_number:

            # Start at last place in path
            current_pose = path[-1]
            current_pose_x = current_pose[0]
            current_pose_y = current_pose[1]

            # Establish memory
            mem = path[-int(np.sqrt(self.max_step_number)):]

            # Init list of available poses
            no_obst_poses = []
            if (not world_append[current_pose_x-1, current_pose_y]):
                no_obst_poses.append((current_pose_x-1, current_pose_y))
            if (not world_append[current_pose_x+1, current_pose_y]):
                no_obst_poses.append((current_pose_x+1, current_pose_y))
            if (not world_append[current_pose_x, current_pose_y-1]):
                no_obst_poses.append((current_pose_x, current_pose_y-1))
            if (not world_append[current_pose_x, current_pose_y+1]):
                no_obst_poses.append((current_pose_x, current_pose_y+1))

            # If we are immediately surrounded by walls/obstacles, search fails
            if len(no_obst_poses) == 0:
                return None
            # If only one choice, take it
            elif len(no_obst_poses) == 1:
                path.append(no_obst_poses[0])
            else:
                # Lets check if available_poses are in our memory
                # Init empty list of available poses
                available_poses = []

                # Step through all poses in no_obst_poses
                for pose in no_obst_poses:
                    # Check if pose is in our memory
                    if not pose in mem:
                        # If not in memory, append to available_poses
                        available_poses.append(pose)

                # Lets choose one of the available_poses
                if len(available_poses) > 0:
                    choice = np.random.choice(len(available_poses), 1)[0]
                    path.append(available_poses[choice])
                else:

                    choice = np.random.choice(len(no_obst_poses), 1)[0]
                    path.append(no_obst_poses[choice])

            # Check if we reached our goal_pose
            if path[-1] == goal_pose:
                return path

        return None

if __name__ == "__main__":

    # If we run this file, run the provided example and print resultant path
    # to the terminal
    world_state = np.array([[0, 0, 1, 0, 0, 0],
                            [0, 0, 1, 0, 0, 0],
                            [0, 0, 0, 0, 1, 0],
                            [0, 0, 1, 1, 1, 0],
                            [0, 0, 0, 0, 1, 0],
                            [0, 0, 0, 0, 0, 0]])
    robot_pose = (2, 0)
    goal_pose = (5, 5) # Note: in provided example (6, 6) is not a valid pose

    # Set max_step_number
    max_step_number = 1000

    # Instantiate RandomPlanner class
    planner = RandomPlanner(max_step_number)

    # Perform path search
    path = planner.search(world_state, robot_pose, goal_pose)

    # Print result to screen
    print "\nRandom planner resultant path\n ", path


Комментарии
1 ответ


  1. Хорошая документация, мне нравится.

  2. Я не люблю использовать слово "поза". Как правило, слово "представлять" означает углы стыков робота. Но код здесь используется "поза", чтобы означать положение робота в мире. Я бы предпочел, чтобы сократить "положение" в "поз", поскольку отсутствует "е" в "позицию".

  3. В max_step_number аргумент должен быть задокументирован в строкой документации для __init__ метод, не в классе строкой документации.

  4. Я думаю, что это плохая идея скопировать из описания max_step_number аргумент. Когда у вас есть дубликаты документации такой, есть риск, что когда вы измените то, что вы будете редактировать одну копию и забудьте отредактировать остальные. Так почему бы не написать что-то вроде этого:

    The max_step_number attribute has the same meaning as the
    argument to the constructor, q.v.

    (Вы на самом деле не надо писать "сахара", но это звучит более сложные.)


  5. Это будет хорошая идея, чтобы кэшировать значения, как int(np.sqrt(self.max_step_number)) в локальных переменных, чтобы сохранить перерасчет их на каждом шагу:

    memory_size = int(np.sqrt(self.max_step_number))

  6. Есть много повторов в построении списка доступных позиций для переезда. Я бы предложил сделать список направлений, в которых робот может двигаться:

    DIRECTIONS = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    и обходишь тех направлениях, проверяя каждый, как вы идете:

    free_positions = []
    for dx, dy in DIRECTIONS:
    new_position = x + dx, y + dy
    if not world_append[new_position]:
    free_positions.append(new_position)

  7. Анализ сложности должен работать. Во-первых, строительство world_append занимает время, пропорциональное размеру в мире, и это, наверное, больше, чем \ФП\$. (Нанесение границ на мир-это хорошая идея для того, чтобы избежать проверка границ в петле, но при добавлении границы должно быть сделано только один раз, а не раз в поиск.) Во-вторых, линия

    mem = path[-int(np.sqrt(self.max_step_number)):]

    копии из памяти, принимает \$Θ(\корень Н)\ долл., и это сделано опять же для каждого шага на пути, принимая \$Θ(н^{3\over2})\ долл. В-третьих, тест

    if not pose in mem:

    возможно, придется искать через все элементы в памяти для того, чтобы сделать вывод, что pose нет, с \$О(\корень Н)\$, И опять же, это может быть сделано на каждом шагу, тем самым принимая на \$О(N^{3\over2})\ долл.

    Чтобы получить во время выполнения вплоть до \$О(П)\$ вам нужно использовать различные структуры данных для памяти робота. Простой подход будет представлять память как отображение от позиции числа последнего шага поиска, при котором эта позиция была посетить. Вам бы начать с пустой карты (без позиции все-таки побывал):

    memory = {} # mapping from position to step number

    и затем, после принятия Шаг position надо обновлять в памяти подобное:

    path.append(position)
    memory[position] = len(path)

    а затем, чтобы увидеть, если позиция находится в памяти, вы видите, если он был достаточно недавно посетили:

    if memory.get(position, float('-inf')) > len(path) - memory_size:
    # position is in memory

3
ответ дан 26 января 2018 в 12:01 Источник Поделиться