Существуют два способа усовершенствования метода декомпозиции ячеек, позволяющие исправить эти недостатки. Первый из них состоит в том, что допускается дальнейшее разделение смешанных ячеек, возможно, с использованием ячеек, вдвое меньших по сравнению с первоначальным размером. Такая операция может продолжаться рекурсивно до тех пор, пока не будет найден путь, полностью проходящий по свободным ячейкам. (Безусловно, этот метод может применяться, только если есть возможность определить, является ли данная конкретная ячейка смешанной, а эта операция является простой, только если границы пространства конфигураций определяются с помощью относительно простых математических описаний.) Такой метод является полным, при условии, что заданы ограничения на величину наименьшего прохода, через который должен пройти искомый путь. Хотя при этом основная часть усилий, связанных с вычислениями, сосредоточивается на наиболее сложных участках в пространстве конфигураций, данный метод все еще не позволяет добиться успешного масштабирования и распространения его на многомерные задачи, поскольку при каждом рекурсивном разбиении ячейки создаютсяменьших ячеек. Второй способ получения полного алгоритма состоит в том, чтобы неуклонно соблюдалось требование точной декомпозиции ячеек свободного пространства. Этот метод должен допускать, чтобы ячейки принимали неправильную форму в тех местах, где они встречаются с границами свободного пространства, но эти формы все еще должны оставаться "простыми" в том смысле, что при их использовании можно было легко вычислить траекторию прохождения через любую свободную ячейку. Для реализации этого метода требуется использование некоторых весьма сложных геометрических понятий, поэтому данный метод не будет рассматриваться здесь более подробно.

Рассматривая путь решения, показанный на рис. 25.13, a, можно заметить дополнительные сложности, которые необходимо преодолеть. Во-первых, следует отметить, что этот путь содержит произвольно острые углы; робот, движущийся с какой-либо конечной скоростью, не сможет пройти по такому пути. Во-вторых, заслуживает внимания то, что путь проходит очень близко от препятствия. Любой, кто занимается вождением автомобиля, знает, что парковочная площадка, на которой оставлено по одному миллиметру просвета с каждой стороны, в действительности вообще не годится для парковки; по той же причине следует предпочесть такие пути решения, которые не чувствительны к небольшим погрешностям движения.