Алгоритм EKF составления карты напоминает алгоритм локализации EKF, описанный в предыдущем разделе. Основное различие между ними определяется тем, что в распределении апостериорных вероятностей учитываются дополнительные переменные отметок. Модель движения для отметок является тривиальной, поскольку они не движутся. Таким образом, для этих переменных функция f представляет собой единичную функцию, а функция измерения по существу остается такой же, как и прежде. Единственное различие состоит в том, что якобианв уравнении обновления EKF берется не только по отношению к позе робота, но также и по отношению к местонахождению отметки, которая наблюдалась во время t. Результирующие уравнения EKF являются еще более устрашающими по своей сложности, чем те, которые были сформулированы перед этим; именно по этой причине мы их здесь опускаем.

Однако существует еще одна сложность, которая до сих пор нами игнорировалась, — тот факт, что размер карты Μ заранее не известен. Поэтому не известно также количество элементов в окончательной оценке. Эти данные приходится переопределять динамически, по мере обнаружения роботом все новых и новых отметок. Но эту проблему можно решить чрезвычайно просто — как только робот обнаруживает новую отметку, он добавляет новый элемент к распределению апостериорных вероятностей. Если же значение дисперсии этого нового элемента инициализируется очень большим числом, то результирующее распределение апостериорных вероятностей становится таким же, как если бы робот заранее знал о существовании этой отметки.