Исследование методов и разработка алгоритмов автоматического планирования траектории на плоскости тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Яковлев, Константин Сергеевич

• Яковлев, Константин Сергеевич
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Яковлев, Константин Сергеевич

ВВЕДЕНИЕ.4>

Актуальность темы.

Цели и задачи исследования.

Методы исследования.

Научная новизна работы и результаты, выносимые на защиту.б

Практическая значимость рХботы.

Апробация работы.

Публикации.

Структура и объем работы.

Основное содержание работы.91. АНАЛИЗ МЕТОДОВ И АЛГОРИТМОВ ПЛАНИРОВАНИЯ ТРАЕКТОРИИ.

1.1 Предметная область. 1.2 Задача планирования как задача поиска пути на графе.

1.3 Методы поиска пути на графе.

1.3.1 Поиск пути на графе как расчет g*-знaчeнuй.

1.3.2 Эвристические алгоритмы поиска пути.

1.3.3 Обзор работ, посвященных алгоритмам поиска пути на графе для задачи планирования траектории.

1.3.4 Выводы.

1.4 Методы построения графов для решения задачи планирования траектории.

1.4.1 Методы построения графов видимости.

1.4.2 Методы построения разбиения Вороного.

1.4.3 Методы извлечения графовых моделей непосредственно из цифровой карты местности .:.

1.4.4 Выводы.

1.5. Выводы.

2. МЕТРИЧЕСКИЕ ТОПОЛОГИЧЕСКИЕ ГРАФЫ И ИХ ПРИМЕНЕНИЕ В ЗАДАЧАХ ПЛАНИРОВАНИЯ ТРАЕКТОРИИ.

2.1. Основные определения.

2.2 Метрики на МТ-графах.

2.2.1 Метрика кратчайшего пути.

2.2.2 Диагональная метрика.

2.3 Эвристический поиск пути на МТ-графах.

2.4 Проблема локального минимума.

2.5 Выводы.

3. ИЕРАРХИЧЕСКИЙ ПОДХОД К ЗАДАЧЕ ПОИСКА ПУТИ НА МТ-ГРАФЕ.

3.1 Множество кратчайших путей на МТ-графе.

3.1.1 Операция поворота и взаимное расположение клеток МТ-графа.

3.1.2 Структура множества кратчайших путей полностью проходимого МТ-графа.

3.1.3 Нуль-траектории на МТ-графе.

3.2 Простейшие иерархические алгоритмы поиска пути на МТ-графе.

3.2.1 Основные определения и утверждения.

3.2.2 Простейшие реализации иерархического подхода к поиску пути на МТ-графе.

3.3 Алгоритм ША*.

3.3.1 Препятствия на МТ-графе.

3.3.2 Стратегия выделения опорных клеток алгоритма НСА*.

3.3.3 Базовая реализация алгоритма НСА*.•.

3.3.4 Теоретические свойства базовой реализации алгоритма НСА *.

3.3.5 Эвристическая реализация алгоритма НСА *.

3.4. Выводы.

4. ЭКСПЕРИМЕНТАЛЬНОЕ ОБОСНОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМА НвА*.

4.1 Прогтаммно-аппаратный комплекс для проведения экспериментов.

4.1.1 Аппаратный комплекс.

4.1.2 Программный комплекс.

4.2 Первая серия экспериментов.

4.3. Вторая серия экспериментов.

4.4. Третья серия экспериментов.

4.5. Выводы.

Введение диссертации (часть автореферата) на тему «Исследование методов и разработка алгоритмов автоматического планирования траектории на плоскости»

Актуальность темы

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

Задача планирования траектории в- контексте автоматизации управления сложными техническим объектами (роботами, транспортными средствами и др.) изучается с 50-х годов XX века. Одним из первых проектов в этой области являлся известный проект Стэнфордского университета США по созданию робота SHAKEY в 1966-1972 гг. Именно он положил начало многолетним исследованиям методов и подходов к решению- задач планирования траектории, продолжающимся по сей день. За последние годы были успешно реализованы десятки крупных проектов в этой области, например:

- DARPA URBAN CHALLENGE (соревнования беспилотных автомобилей в городских условиях, 2008г., США)

- NASA ARP (создание системы управления малым беспилотным вертолетом Yamaha RMAX II, предназначенным для разведки и мониторинга, 1998-2003 гг. США)

- MARS (разработка программного обеспечения для автономных наземных роботов, США, 1999-2004 гг.)

- У1АС (создание беспилотной модификации гражданского' автомобиля и осуществление пробега протяженностью 13 ООО км., Европейский Союз, 2010)

- Робокросс (соревнования автомобилей-роботов, Россия, 2010).

К сожалению, почти все методы планирования' траектории, разработанные к текущему моменту и используемые в системах управления современными беспилотными транспортными' средствами, являются-достаточно ресурсоемкими. При этом большинство из них принципиально не способно решать задачи планирования траектории в условиях дефицита* вычислительных ресурсов. Следовательно, известные методы неприменимы тогда, когда^ речь об автоматизации малых, полностью« автономных беспилотных транспортных средств, т.к. подобные транспортные средства не" могут быть оснащены» мощными вычислителями в силу особенностей конструкции И' ограниченной грузоподъемности.

Таким образом, представляются достаточно* актуальными задачи создания эффективных (в вычислительном смысле) методов планирования траектории, применимых в системах управления, малыми, полностью автономными транспортными средствами нового поколения. Настоящая работа посвящена исследованию и решению некоторых возникающих в этой области задач, что свидетельствует о ее актуальности.

Цели и задачи исследования

Целью диссертационной работы является разработка новых вычислительно-эффективных методов планирования траектории на плоскости.

Для достижения поставленной цели в работе решены следующие задачи:

1. Выполнен анализ существующих методов построения графов, являющихся моделями предметной области в задачах планирования траектории и методов поиска пути на указанных графах. Предложена и исследована графовая модель, отражающая особенности задачи планирования траектории на плоскости — метрический топологический граф (МТ-граф).

2. Разработаны принципы иерархической декомпозиции задачи планирования траектории1 и алгоритм планирования траектории, реализующий эти принципы - БЮА*.

3. Исследованы свойства алгоритма НХЗА* при ^определенных ограничениях. Предложены модификации алгоритма ЕЮА*, предназначенные для решения различных типов задач планирования траектории на плоскости.

4. Разработаны программные средства для оценки вычислительной эффективности различных алгоритмов планирования траектории. Проведена серия вычислительных экспериментов, направленных на сравнение разработанного алгоритма НХЗА* с аналогами.

Методы исследования

В диссертационной работе использованы методы искусственного интеллекта, теории множеств, математической логики, теории графов.

Научная новизна работы и результаты, выносимые на защиту

Традиционно, для решения задачи планирования траектории в качестве модели предметной области используются взвешенные графы. Вершинам графа соответствуют географические координаты точек пространства, весам ребер - соответствующие расстояния. Такое представление предметной области позволяет использовать для решения поставленной задачи различные алгоритмы поиска пути на графе, среди которых особый интерес представляет алгоритмы эвристического поиска семейства А*. В настоящее время существует множество модификаций алгоритма А*, каждая из которых предназначена для решения задач планирования траектории с определенным типом ограничений. Однако, практически все алгоритмы семейства А*, разработанные к, настоящему времени, принципиально не способны решать задачу локального минимума и, как следствие, строить планы в условиях дефицита вычислительных ресурсов, а именно, процессорного времени и рабочей памяти., Таким образом, необходимы разработка: и исследование: новых методов поиска пути на графе, опирающихся на иные принципы, нежели известные алгоритмы семейства А*. В" настоящей работе; предлагается новый метод решения поставленной задачи, опирающийся на принцип иерархической декомпозиции. Описывается новый алгоритм поиска путщ реализующий указанный принцип;

Важным вопросом в решении задачи планирования траектории; является вопрос построения графа; моделирующего окружающую среду для объекта управления (беспилотного транспортного средства). К распространенным графовым моделям, используемым для решения подобного рода задач, относятся граф видимости и разбиение Вороного; Однако, методы построения указанных графов не применимы для решения практических задач навигации; беспилотных транспортных средств; т.к. основаны на использовании «непрерывных» моделей" окружающего пространства, в то время как в памяти бортового вычислителя транспортного средства хранится дискретная цифровая карта местности. В работе предлагается и исследуется новая графовая модель, отражающая особенности задачи планирования траектории на плоскости - метрический топологический граф, которая, может быть извлечена непосредственного из цифровой карты местности.

Таким образом, научная новизна работы заключается в исследовании и разработке новой графовой модели и нового метода поиска пути на графе в рамках решения задачи планирования траектории на плоскости;

Практическая значимость работы

Методы и алгоритмы, полученные в диссертации, могут быть использованы при разработке систем управления' беспилотными^ транспортными средствами нового поколения.

Методы и алгоритмы, реализованы в виде независимых программных модулей и используются в следующих проектах:

1. «Интеллектуальная система поддержки автоматизированного маловысотного полета вертолета», проект Российского Фонда Фундаментальных исследований № 09-07-00043-а

2. «Развитие методов анализа полуструктурированной информации и моделирования целенаправленного- поведения», выполняемого- в рамках федеральной целевой программы «Научные и научно-педагогические кадры инновационной России».

3. «Развитие методов- интеллектуального управления на основе анализа потоков данных», проект 2.2 Отделения нанотехнологий и информационных технологий Российский академии наук.

Апробация работы

Основные положения работы докладывались и обсуждались на следующих научных конференциях и семинарах:

1. XII национальная конференция по искусственному интеллекту с международным участием (КИИ-2010), сентябрь 2010, г. Тверь.

2. Общемосковский научный семинар «Проблемы искусственного интеллекта», март 2010, г. Москва.

3. III международная конференция «Системный анализ и-информационные технологии - САЙТ 2009», сентябрь 2009, г. Звенигород

4. IX международная научной конференция им. Таран Т.А «Интеллектуальный анализ информации - ИАИ-2009», май 2009, г. Киев, Украина.

5. ХЫП всероссийская конференции по проблемам математики, информатики, физики и химии Российского' университета дружбы народов, апрель 2008, г.Москва.

Публикации

Основные результаты, полученные по теме диссертационной работы, опубликованы в 9 печатных работах (в том числе 2 публикации' в ведущих ' рецензируемых научных изданиях, рекомендованных Высшей^ аттестационной комиссией, 6 публикаций в трудах научных конференций).

Структура и объем работы

Диссертация- состоит из введения, трех глав" заключения, списка

Заключение диссертации по теме «Теоретические основы информатики», Яковлев, Константин Сергеевич

Основные результаты работы.

Предложена и исследована новая графовая модель, отражающая особенности задачи планирования траектории на плоскости — метрический топологический граф (МТ-граф).

Разработан новый алгоритм планирования траектории на плоскости — НвА*, использующий принцип рекурсивного иерархического разбиения исходной задачи с использованием детерминированных критериев останова.

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

Предложены различные модификации алгоритма НвА* для различных типов задач планирования траектории.

Разработана экспериментальная программная система для решения задач планирования траектории, реализующая рассмотренные в работе алгоритмы.

С помощью разработанной программной системы выполнено более 200 вычислительных экспериментов, показавших значительное превосходство алгоритма БЮА* над существующими аналогами с точки зрения использования вычислительных ресурсов.

Заключение

Диссертационная работа посвящена исследованию подходов, методов и алгоритмов планирования траектории на плоскости, в контексте решения задачи автоматизации управления беспилотными транспортными средствами, обладающими ограниченными вычислительными ресурсами.

В ходе диссертационной работы задача планирования траектории сформулирована как задача построения графа специального вида, являющегося моделью рассматриваемой предметной области (окружающей среды), и поиска пути на нем. Выполнен анализ работ, посвященных графовым моделям, используемых в ходе решения задачи планирования. Исследованы методы построения<указанных графов и алгоритмы поиска пути на них. Особое внимание при этом уделено вопросам повышения эффективности поиска за счет использования эвристик, обладающих различными свойствами.

Список литературы диссертационного исследования кандидат физико-математических наук Яковлев, Константин Сергеевич, 2010 год

1. Т. Кормен и д/?., 2005. Кормен Т.Х., ЛейзерсошЧЖ, Ривест Р:Л;, Штайш К. Глава 33. Вычислительная: геометрия? // Алгоритмы: построение и анализ. 2-е издание. М.: «Вильяме». 2005.

2. Левитин, 2006.;; А. В. Левитин; Алгоритмы: введение: в разработку и анализ. М.: «Вильяме», 2006.

3. Люгер,, 2005.; Щ Ф1 Люгер; Искусственный* интеллект. Стратегии: и» методы решения сложных проблем;-М: Вильяме, 2005.

4. Прапарата и Шеймос, 1989. Прапарата Ф., Шеймос М. Вычислительная геометрия: введение. М;: Мир, 1989. С. 478.

5. Рассел и: Норвиг, 2006. Рассел С., Норвиг П. Искуственный интеллект: современный подход. Пер. с англ. и ред. К. А. Птицына. 2-е изд. М.: Вильяме, 2006.

6. Яковлев, 2008. Яковлев К.С. Архитектуры систем управления автономными, беспилотными аппаратами. Труды XLIV всероссийской конференции:по проблемам математики, физики и информатики. Секция «программные системы». М.: РУДН. 2008; С. 40-50.

7. Яковлев,,2009а.'Яковлев К.С. Методьърешения проблемы локального минимума при планировании траектории. // Труды- IX международной научной конференция им.Таран Т.А. «Интеллектуальный^ анализ информации ИАИ-2009», Киев: ПРОСВГГА, 2009. С. 451-457.

8. Яковлев, 20096. Яковлев К.С. Графы специальной.структуры в.задачах планирования траектории. Труды III международной конференции «Системный анализ и информационные технологии САИТ-2009». М: ИСА РАН, 2009. С. 226-234.

9. Albus J. et al, 2002. Albus J. et al, 4D/Real-time Control System (4D/RCS): AReference Model Architecture for Unmanned Vehicle Systemsv2.0, NIST, NISTIR6910, 2002.

10. Alt, 1995.iAlt O. S. H. The voronoi diagram of curved objects, in Proc. 11th Annual ACM Symposium on Computational Geometry, 1995.

11. Asano et al, 1986. T. Asano, T. Asano, L. J. Guibas, J. Hershberger, and H. Imai. Visibility of disjoint polygons. Algorithmica, 1:49-63, 1986.

12. Aurenhammer, 1991. F. Aurenhammer. Voronoi diagrams — A survey of a fundamental data structure. ACM Computer Surveys 23 (3), 1991.

13. Bagchi and Mahanti, 1983. Bagchi A. and Mahanti A. Search algorithms under different kinds of heuristics: a comparative study. Journal of the ACM, 30(1):1-21, 1983.

14. Berg et al, 2008. M. Berg, O. Cheong, M. Kreveld, and M. Overmars.

15. Computational Geometry: Algorithms and Applications, 3rd ed. Springer,1. April 2008.

16. Bole and Cytowski, 1992. Bole L. and Cytowski J. Search methods forartificial intelligence. Academic press, London, 1992.

17. Bresenham, 1965. J. E. Bresenham. Algorithm for computer control of adigital plotter. //IBM SystemsJournal, Vol. 4, No.l, 1965.4,

18. Choset and Burdick, 1995. Choset H. and Burdick J. Sensor based planning, part I: The generalized voronoi graph. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 1995.

19. Dean and Boddy, 1988. T. L. Dean and M. Boddy. An analysis of time-dependent planning. In Proceedings of the National Conference on Artificial Intelligence, AAAI-88, 1988.

20. Dechter and Pearl, 1985. Dechter R. and Pearl J. Generalized best-first search strategies and the optimality of A*. Journal of the ACM, 32(3):505-536, 1985.

21. Dehne and Klein, 1997. F. Dehne and R. Klein, "The big sweep": On the power of the wavefront approach to Voronoi diagrams, Algorithmica 17:19— 32, 1997.

22. Dijkstra, 1959. E. W. Dijkstra. A note on two problems in connexion with graphs. //Numerische Mathematik, 1:269-271, 1959.

23. Ebendt and Drechsler, 2009. Ebendt R. and Drechsler R. Weighted A* search unifying view and application. Artificial Intelligence, 173(14): 13101342,2009.

24. Edelkamp et al, 2008. Edelkamp S. et al, External-Memory Graph Search. In Proceedings of 18th International Conference on Automated Planning and Scheduling September 14-18, 2008, Sydney, Australia.

25. Edelsbrunner, 1987. H. Edelsbrunner. Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, vol. 10. Springer-Verlag, 1987.

26. Fortune, 1986. S. Fortune. A sweepline algorithm for Voronoi diagrams. Proceedings of the second annual symposium on Computational geometry. Yorktown Heights, New York, United States, pp.313-322. 1986.

27. Furcy and Koenig, 2005. Furcy D. and Koenig S. Scaling up WA* with commitment and diversity. In Proceedings of the International Joint Conference on Artificial Intelligence, IJCAI-05, 2005.

28. Gasching, 1979. Gasching J. Performance measurement and analysis of certain search algorithms. Ph.D. thesis, Carnegie-Mellon University. Department of Computer Science, 1979.

29. Gelperin, 1977. Gelperin D. On the optimality of A*. Artificial Intelligence 8(l):69-76, 1977.

30. Ghosh and Mount, 1991. Ghosh, S. and Mount, D., An output sensitive algorithm for computing visibility graphs // SIAM Journal on Computing, 20:888-910,1991.

31. Hart et al> 1968. Hart, P., Nilsson, N., & Raphael, B. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics (SSC), 4(2):100-107, 1968.

32. Heinz et alt 1995. Heinz B., Joseph G., David K., Werman M., Linear time Euclidean distance transform algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17:529-533, May 1995.

33. Held, 1998. M. Held, Voronoi diagrams and offset curves of curvilinear polygons // Computer-Aided Design, 30:287-300, 1998.

34. Huang and Chung, 2004. Huang, H.P. and Chung, S.Y. Dynamic visibility graph for path planning // In Proceedings of conference on Intelligent Robots and Systems, 2004 (IROS 2004), 3:2813-2818, 2004.

35. Ikeda and Imai, 1994. Ikeda T. and Imai T. Fast A* algorithms for multiple sequence alignment. In Genome Informatics Workshop, 1994.

36. Kitamura et al, 1998. Y. Kitamura, M. Yokoo, T. Miyaji, and S. Tatsumi. Multi-state commitment search. In Proceedings of 10th IEEE International Conference on Tools with Artificial Intelligence, 1998.

37. Klein and Wood, 1988. R. Klein and D. Wood. Voronoi diagrams based on general metrics in the plane, In Proc. 5th Annual Symposium on Theoretical Aspects of Computer Science (STACS '88), Berlin, 1988.

38. Koll and Kaindl, 1992. Koll A. and Kaindl H. A new approach to dynamic weighting. In Proceedings of the 10th European Conference on Arti cial Intelligence (ECAI-92), John Wiley and Sons, 1992.

39. Korf, 1985. Korf R. Depth-first iterative deepening: An optimal admissible tree search. Artificial Intelligence, 27(1):97-109, 1985.

40. Korf, 1990. Korf R. Real-time heuristic search. Artificial Intelligence, 42(2-3): 197-221, 1990.

41. Korf, 1993. Korf R. Linear-space best-first search. Artificial Intelligence, 62(l):41-78, 1993.

42. Korf, 1998. Korf R.E., Artificial intelligence search algorithms, CRC Handbook of Algorithms and Theory of Computation, M.J. Atallah (Ed.). Boca Raton, FL: CRC Press, 1998.

43. Latombe, 1991. Latombe, J., Robot Motion Planning. Kluwer Academic Publishers, 1991.

44. Lee, 1978. D. T. Lee. Proximity and reachability in the plane. PhD thesis, University of Illinois, Urbana, IL, 1978.

45. Likhachev et al, 2003. M. Likhachev, G. Gordon, and S. Tlirun. ARA*: Anytime A* with provable bounds on sub-optimality. In Proc. of Advances in Neural Information Processing Systems. MIT Press, 2003.

46. Likhachev et al, 2005a. M. Likhachev, D. Ferguson, G. Gordon, A. Stentz, S. Thrun, Anytime Dynamic A*: An Anytime, Replanning Algorithm, Proceedings of the International Conference on Automated Planning and Scheduling, ICAPS-05, 2005.

47. Likhachev et al, 2005b. M. Likhachev, Search-based planning for large dynamic environments, Ph.D. thesis, Carnegie Mellon University, 2005.

48. Liu and Arimoto, 1991. Liu, Y.H. and Arimoto, S;, Proposal of tangent graph and extended- tangent' graph for path planning of mobile robots // Próc. 1991 IEEE ICRA, 1:312-317, 1991.

49. Luger and Stubblefield, 2005. Luger G. and Stubblefield W. Artificial Intelligence: Structures and Strategies for Complex Problem Solving (5th ed.). The Benjamin/Cummings Publishing Company, Inc., 2005.

50. Mazon and Recio, 1991. M. L. Mazon and T. Recio. Voronoi diagrams based on strictly convex distances on the plane. Manuscript, Departamento De Matemáticas^ Universidad de Cantabria, Santander, España, 1991.

51. Nilsson, 1980. Nilsson N. J. Principles of Artificial Intelligence. Palo Alto, California: Tioga Publishing Company, 1980.

52. Pearl, 1984. Pearl J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984.

53. Pearl and Kim, 1982. Pearl J. and Kim,, J. Studies: in semi-admissible heuristics. IEEE Transactions on Pattern Analysis, and Machine Intelligence, PAMI-4. 1982. ' .

54. Pohl, 1970a. Pohl I. First results on the effect of error in heuristic search. Machine Intelligence, 5:219-236, 1970

55. Pohl, 1970b. Pohl I. Heuristic search viewed as pathfinding in a graph. Artificial Intelligence, l(3):193-204, 1970.

56. Pohl, 1977. Pohl I. Practical and theoretical considerations in heuristic search algorithms, Machine Intelligence 8, Elcock E. W. and Michie D. (Eds.). New York: Wiley, 1977.

57. Rabin, 2000. Rabin S. A* speed optimizations, Game Programming GemSj DeLoura M. (Ed.). Rockland, MA: Charles River Media, 2000.

58. Reese, 1999. B; Reese. AlphA*: An e-admissible Heuristic Search Algorithm. Institute for Production Technology, University of Southern Denmark 1999 -http://homel.stofanet.dk/breese/astaralpha-submitted.pdf.gz

59. Russel, 1992. Russel S. Efficient memory-bounded search method. In Proceedings of the 10th European Conference on Artifficial Intelligence, ECAI-92. 1992.

60. Russel and Norvig, 2003. Russell S. J', and Norvig P. ArtificialTntelligence: A Modern Approach. Upper Saddle River, N.J.: Prentice Hall, 2003

61. Sen and Bagchi, 1989. Sen A.K. and Bagchi A. Fast recursive formulations for best-first search- thah allow controlled use of memory. In Proceedings of International Joint Conference on Artificial Intelligence, IJCAI-89, 1989.

62. Shamos and Hoey, 1975. M. I. Shamos and D. Hoey. Closest-point problems. In Proceedings 16th IEEE Symposium on Foundations of Computer Science, 1975, pages 151-162.

63. Stentz and Likhachev, 2008. Stentz A. and Likhachev M., R* Search. Proceedings of the National1 Conference on Artificial Intelligence (AAAI), 2008.

64. Sun et al, 2007. X. Sun, M. Druzdzel, C. Yuan. Dynamic Weighting A* search-based MAP algorithm for Bayesian networks. In Proceedings of the International Joint Conference on Artificial Intelligence, IJCAI-07. 2007.

65. Vempaty et al, 1991. Vempaty N.R., Kumar V. and Korf R. Depth-first vs best-first search. In Proceedings of National Conference on Artificial Intelligence, AAAI-91, 1991

66. Wah and Shang, 1994. Wah B. and Shang Y. A comparative study of IDA*-style searches. In Proceedings of the 6th International Conference on Tools with Artificial Intelligence (ICTAI-94), IEEE Computer Society, 1994.

67. WeizI, 1985. E. Welzl. Constructing the visibility graph for n line segments in 0(n2) time. Inform. Process. Lett., 20:167-171, 1985.

68. Wong, 1991. K. Wong. An efficient implementation of Fortune's plane-sweep algorithm for Voronoi diagrams. Technical Report DCS-182-IR, Department of Computer Science, University of Victoria, Victoria, BC, Canada, October 1991.

69. Wooden, 2006. D.T. Wooden. Graph-based Path Planning for Mobile Robots, PhD thesis, Georgia Institute of Technology, 2006.

70. Yoshizumi et al, 2000. Yoshizumi T., Miura T., Ishida T. A* with partial expansion for large branching factor problems. In Proceedings of the 17th National Conference on Artificial Intelligence (AAAI-2000), AAAI/MIT Press, 2000.

71. Zhou and Hansen, 2002. R. Zhou and E. A. Hansen. Multiple sequence alignment using A*. In Proc. of the National Conference on Artificial Intelligence (AAAI), 2002.

72. Zhou and Hansen, 2007. R. Zhou and E. A. Hansen. Anytime Heuristics Search. Journal of Artificial Intelligence Research, 28 (1): 267-297, 2007.