О формуле Байеса и роботонавигации. Том I
Рассмотрим самого наипростейшего подвижного робота, который будет у нас жить на числовой прямой, причем даже не на непрерывной, а на дискретной, т.е. позиция робота будет описываться целым числом. Пусть в начальный момент времени робот находится в нулевой точке, а дальше ему можно подавать команды перемещения: сдвинуться на шаг вправо (в положительном направлении), либо сдвинуться на шаг влево, в отрицательном направлении.
(рандомная КДПВ с роботом из гугла, наш робот попроще будет)
Позиция такого робота в любой момент времени элементарно находится суммированием шагов вправо и влево (ваш К.О.). Однако, предположим, что исполнительный механизм робота не 100% надежен. В данный момент нас не интересует, проскальзывают ли обрезиненные колесики на кафеле или силовое реле искрит от близких термоядерных взрывов, мы просто постулируем, что с некоторой вероятностью
, робот, вместо того чтобы сдвинуться согласно команде, идет в отказ и остается чилить в текущей позиции. И, внезапно, для штурмана роботонавигации вечер престаёт быть томным.
Понятно, что в такой постановке координата робота перестает быть детерминированной величиной и мы можем рассуждать лишь о вероятности нахождения робота в той или иной позиции (ну чисто электрон в атоме, только попроще).
Обозначим вероятность нахождения в точке i в момент времени t как
, тогда начальная позиция имеет вид:
При команде на перемещение вправо вероятности преобразуются следующим образом:
p_{i-1}^t,)
а при команде на перемещение влево, соответственно
p_{i+1}^t.)
Это просто-напросто сумма вероятностей того, что робот остался в данной ячейке отдыхать и того, что робот успешно прибыл из соседней.
Обратите внимание, что обе эти операции сохраняют инвариант
Следить за тем, что общая вероятность остается единицей при таких увеселениях крайне полезно, сразу отсекает самые грубые ошибки.
Разобравшись с функционированием модели, давайте уже начнем с ней играться. Возьмем для примера
и подадим нашему роботу команду "вправо" 10 раз подряд. В детерминированном случае, понятно, робот бы попал в точку
а в нашей модели мы получим вот такую милую диаграммку вероятностей:
Чтобы стало понятнее, подадим нашему роботу команду "вправо" не 10, а 100 раз подряд:
Да-да, это она (почти). Почему так происходит - тема отдельной беседы, для желающих, сейчас важно то, что мы можем достаточно уверенно сказать "робот находится где-то между точкой 60 и точкой 90", но на этом наша уверенность заканчивается. Допустим, службу доставки Икеи такой результат устраивает, а если бы робот вез патроны?
Дабы более лучше (хе-хе) осознать проблему, давайте еще сильнее упростим постановку: забудем на время ходячего робота, пусть у нас есть некий агрегат, который может находиться либо в нулевом, либо в единичном состоянии и эти состояния инвертируются по команде "переход", с вероятностью отказа
. Пусть изначально наш агрегат находится в нулевом состоянии и мы подаем команду "переход" 100 раз. В детерменированом случае, агрегат должен был вернуться в исходное состояние. В нашем же
Строго говоря, они не совсем равны, но разница проявляется в очень, очень далеком знаке после запятой. Таким образом, информация о состоянии агрегата за сто переходов полностью потеряна (кстати, в качестве несложного упражнения, разберитесь, как я это посчитал).
Я вам тут даже табличку небольшую сварганил, для пущего эффекту (100 "переходов"):
Обратите внимание, мы радикально увеличиваем надежность исполнительного механизма, но при этом агрегат как косячил, так и косячит, в общем-то. Нам потребовался рост надёжности на 3 (три) порядка (бедный инженер!), чтобы агрегат попадал в запланированное состояние в 99% случаев. Тоже не бог весть что, замечу, баллистическую ракету такой системе не очень-то доверишь.
О том, что с этим делать и причем тут формула Байеса - в следующий раз.
Продолжение следует.
(рандомная КДПВ с роботом из гугла, наш робот попроще будет)
Позиция такого робота в любой момент времени элементарно находится суммированием шагов вправо и влево (ваш К.О.). Однако, предположим, что исполнительный механизм робота не 100% надежен. В данный момент нас не интересует, проскальзывают ли обрезиненные колесики на кафеле или силовое реле искрит от близких термоядерных взрывов, мы просто постулируем, что с некоторой вероятностью
, робот, вместо того чтобы сдвинуться согласно команде, идет в отказ и остается чилить в текущей позиции. И, внезапно, для штурмана роботонавигации вечер престаёт быть томным.
Понятно, что в такой постановке координата робота перестает быть детерминированной величиной и мы можем рассуждать лишь о вероятности нахождения робота в той или иной позиции (ну чисто электрон в атоме, только попроще).
Обозначим вероятность нахождения в точке i в момент времени t как
, тогда начальная позиция имеет вид:
При команде на перемещение вправо вероятности преобразуются следующим образом:
а при команде на перемещение влево, соответственно
Это просто-напросто сумма вероятностей того, что робот остался в данной ячейке отдыхать и того, что робот успешно прибыл из соседней.
Обратите внимание, что обе эти операции сохраняют инвариант
Следить за тем, что общая вероятность остается единицей при таких увеселениях крайне полезно, сразу отсекает самые грубые ошибки.
Разобравшись с функционированием модели, давайте уже начнем с ней играться. Возьмем для примера
и подадим нашему роботу команду "вправо" 10 раз подряд. В детерминированном случае, понятно, робот бы попал в точку
а в нашей модели мы получим вот такую милую диаграммку вероятностей:
Чтобы стало понятнее, подадим нашему роботу команду "вправо" не 10, а 100 раз подряд:
Да-да, это она (почти). Почему так происходит - тема отдельной беседы, для желающих, сейчас важно то, что мы можем достаточно уверенно сказать "робот находится где-то между точкой 60 и точкой 90", но на этом наша уверенность заканчивается. Допустим, службу доставки Икеи такой результат устраивает, а если бы робот вез патроны?
Дабы более лучше (хе-хе) осознать проблему, давайте еще сильнее упростим постановку: забудем на время ходячего робота, пусть у нас есть некий агрегат, который может находиться либо в нулевом, либо в единичном состоянии и эти состояния инвертируются по команде "переход", с вероятностью отказа
. Пусть изначально наш агрегат находится в нулевом состоянии и мы подаем команду "переход" 100 раз. В детерменированом случае, агрегат должен был вернуться в исходное состояние. В нашем же
Строго говоря, они не совсем равны, но разница проявляется в очень, очень далеком знаке после запятой. Таким образом, информация о состоянии агрегата за сто переходов полностью потеряна (кстати, в качестве несложного упражнения, разберитесь, как я это посчитал).
Я вам тут даже табличку небольшую сварганил, для пущего эффекту (100 "переходов"):
Обратите внимание, мы радикально увеличиваем надежность исполнительного механизма, но при этом агрегат как косячил, так и косячит, в общем-то. Нам потребовался рост надёжности на 3 (три) порядка (бедный инженер!), чтобы агрегат попадал в запланированное состояние в 99% случаев. Тоже не бог весть что, замечу, баллистическую ракету такой системе не очень-то доверишь.
О том, что с этим делать и причем тут формула Байеса - в следующий раз.
Продолжение следует.