Устройство для определения кратчайшего пути автономного транспортного робота

ОПИСАНИЕ ИЗОБРЕТЕ 4-2 юл.11политехнический инселикой Октябрьской солюцииин и О. Н. Костюк8,8)свидетельство СССРб 06 Г 15/20, 1984,титут оциаПРЕДЕВТОНОАк вычирименени ман ЛЕ НИЯ МНОГО ител в си улят ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ К АВТОРСКОМУ СВИДЕТЕЛЬСТВ(54) УСТРОЙСТВО ДЛЯ О КРАТЧАЙШЕГО ПУТИ А ТРАНСПОРТНОГО РОБО (57) Изобретение относитс ной технике и может быть темах управления роботам рами. Целью изобретения является повышение быстродействия устройства путем совмещения во времени следования тактов ввода весов дуг и тактов расчета кратчайшего пути графа. Устройство содержит регистры 1, матрицу моделей дуг из счетчиков 2 и триггеров 3, элементы И 4, элементы ИЛИ 5, элемент НЕ 6, генератор тактовых импульсов 7. Причем выходы регистров 1 моделей дуг соединены с соответствующими входами занесения информации счетчиков 2 и триггеров 3 моделей дуг, а входы регистров 1 моделей дуг являются информационными входами устройства. Введенные регистры моделей дуг выполняют роль буферной памяти и обеспечивают совмещение во времени тактов ввода и обработки информации в устройстве. 1 ил.5 10 Формула изобретения Изобретение относится к вычислительной технике, может быть применено в системах управления роботами и манипуляторами для решения задач нахождения кратчайшего пути между пунктами при перемещении транспортного робота и является усовершенствованием изобретения по авт. св.1215116,Целью изобретения является повышение быстродейстия за счет совмещения во времени следования тактов ввода весов дуг и тактов расчета кратчайшего пути графа.На чертеже приведена структурная схема устройства.Устройство содержит группу регистров 1, счетчики 2;, и триггеры 3 моделей дуг матрицы, первую группу элементов И 4;, первую группу элементов ИЛИ 5;, элемент НЕ 6, генератор 7 тактовых импульсов, вход 8 пуска, вторую группу элементов И 9, вторую группу элементов ИЛИ 10;, линию 11 задержки, выход 12 признака окончания счета, группу информационных входов 13, вход 14 разрешения ввода информации.Устройство работает следующим образом.В исходном состоянии счет в счетчиках 2 моделей дуг заблокирован. Исходная информация о весах и топологии графа заносится в регистры 1 моделей дуг и по сигналу с входа 14, поступающему через элемент 5 и линию 11 задержки к элементам матричной модели, переписывается в счетчики 2 и триггеры 3, после чего устройство готово к счету и приему следующей порции информации о графе маршрутов, которая вводится в регистры 1 моделей дуг одновременно с работой устройства в режиме счета. Счет в устройстве начинается с момента подачи сигнала на вход 8 пуска, после чего импульсы с генератора 7 начинают проходить через элемент И 4 на вычитающие входы счетчиков 2 первой строки матрицы моделей дуг. Далее устройство функционирует согласно следующему алгоритму: при переполнении (обнулении) любого 1)-го счетчика 2 на выходе элемента ИЛИ 5; появляется логическая 1, сбрасывающая триггеры 3, что обеспечивает блокировку счета на счетчиках 2,-го столбца матрицы моделей дуг, одновременно 1 с выхода элемента ИЛИ 5, разрешает прохождение тактовых импульсов через элемент И 4 к счетчикам 1-ой строки матрицы моделей дуг, на счетчики 2 разблокированных строк матрицы поступают тактовые импульсы, обеспечивающие счет счетчиков 2, за исключением принадлежащих заблокированнымстолбцам.Так продолжается до переполнения любого счетчика 2 последнего столбца матрицы моделей дуг, при этом на выходе элемента ИЛИ 5 появляется логическая 1, сбрасывающая в О триггеры и-го столбца матрицы моделей дуг, а на втором входе элемента И 4 появляется О, запрещающий поступление импульсов с генератора 7 к счет 15 20 25 30 35 40 45 50 чикам 2. При этом на выходах ряда счетчиков 2 присутствует сигнал переполнения, зафиксированный в процессе работы устройства.Код кратчайшего пути считывается при появлении единичного сигнала на выходе элемента ИЛИ 5 с выходов элементов И 9, при этом на выходе элемента И 9;, присутствует логическая 1 с выхода счетчика 2, если соответствующая дуга принадлежит кратчайшему пути, О - в противном случае. Код кратчайшего пути формируется следующим образом. Единичный сигнал с выхода элемента ИЛИ 5 поступает на входы элементов И 9;, при этом на выходе элемента 9;И, соответствующего. переполненному счетчику 2;, появляется логическая 1, на выходах остальных элементов 9 И присутствует О; логическая 1 с выхода элемента 9 И поступает в соответствующий вход элемента 10 ИЛИ, на выходе которого также появляется 1, позволяющая идентифицировать очередную дугу, принадлежащую кратчайшему пути, при этом на выходе элемента 9; И появляется 1 (К; - индекс переполнившегося счетчика 2 столбцаи так далее до появления логической 1 на выходе любого элемента И 9 и (1 = 2,п), соответствующего счетчику 2 п первой строки матрицы моделей дуг, что завершает формирование кода кратчайшего пути и служит признаком окончания расчета кратчайшего пути в графе по информации, занесенной в счетчики 2 и триггеры 3 модели дуг на текущем цикле обработки. Содержащаяся в регистрах 1 информация по топологии и весах графа для следующего цикла расчета по сигналу окончания счета с элемента ИЛИ 5 задержанного линией 11 задержки на время, необходимое для вывода результатов текущего цикла расчета, заносится в счетчики 2 и триггеры 3 моделей дуг, Устройство готово к следующему циклу работы.Таким образом, регистры моделей дуг выполняют роль буфера входной информации, обеспечивая ее ввод в счетчики моделей дуг за один такт. Совмещение тактов занесения информации в устройство с тактами расчета кратчайшего пути позволяет сократить время выполнения операций ввода не менее чем в (и - 1) раз, по сравнению с известным устройством, при циклическом использовании устройства для расчета кратчайшего пути в графе. Устройство для определения кратчайшего пути автономного транспортного робота по авт, св.1215116, отличающееся тем, что, с целью повышения быстродействия за счет совмещения во времени следования тактов1383387 Составитель С. КошелевРедактор Н. Лазаренко Техред И. Верес Корректор М. Г 1 ожоЗаказ 915/49 Тираж 704 ПодписноеВНИИПИ Государственного комитета СССР по делам изобретений и открытий113035, Москва, Ж - 35, Раушская наб., д. 45Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 ввода весов дуг и тактов расчета кратчайшего пути графа, в него введены линия задержки, группа (и - 1) Х (п - 1) регистров, первый выход ц.го регистра группы (1= 1, и - 1, 1 = 2,п) соединен с входом задания коэффициента счетчика 11-й модели дуги ( =:1, п - , /: - " 2;п) матрицы (п - 1) )и - 1) моделей дуг графа, вход установки в 1 триггера 11-й модели дуги соединен с вторым выходом 11-го регистра, входы регистров группы являются группой(п - 1) Х ( - 1) информационных входов устройства, выход линии задержки соединен с входами разрешения счета счетчиков и входами синхронизации триггеров всех моделей дуг матрицы, вход линии задержки соединен с выходом п-го элемента ИЛИ первой группы и является выходом признака окончания счета устройства, и-й вход п-го элемента ИЛИ первой группы является входом разрешения ввода информации устройства.