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

 

Изобретениеотносится к области вычислительной техники и может быть применено в автоматизированных транспортных системах, например, внутрицехового назначения. Задача выбора кратчайшео-о маршрута движения транспортного средства заключается в идентификации соответствующей последовательности направлений движения транспортного средства относительно маркеров станций и ветвлений в транспортной сети с односторонними проездами, представляемой объединением транспортных петель. Целью изобретения является упрощение устройства выбора кратчайшего маршрута. Поставленная цель достигается тем, что устройство, содержаш,ее блок 1 адресной памяти, счетчик 2, первый 3, второй 4, третий 5 и четвертый 6 блоки сравнения, сумматор 8, первый регистр 9, введены элемент И 7, второй регистр 10, первый и второй триггеры 11 и 12 и элемент 2И-ИЛИ-НЕ 13. Использойание устройства позволяет автоматизвдовать управлзние транспортными средствами в условиях частого измерения целевых установок. В частности, его можно использовать при реализации гибкого автоматического производства с его мелкосерийностью и частыми именами маршрутной технологии. 1 ил. 3CLntJClf I , (О го QD СП пкши

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

З0»1295412

А3 (51)4 G 06 F 15 20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ 1а ЦИй

:Сл

«Р«

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

IlO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3943272/24-24 (22) 09,08.85 (46) 07.03.87. Бюл. М- 9 (71) Ленинградский институт авиационного приборостроения (72) В.И.Петров, В.Е.Сорокин и И.В.Ефремова (53) 681.333 (088.8) (56) Авторское свидетельство СССР

У 851411, кл. G 06 F 15/20, 1979.

Авторское свидетельство СССР

N - 1206792, кл. G 06 F 15/20, 1984. (54) УСТРОЙСТВО ДЛЯ ВЫБОРА КРАТЧАЙШЕГО МАРШРУТА (57) Изобретение. относится к области вычислительной техники и может быть применено в автоматизированных транспортных системах, например, внутрицехового назначения. Задача выбора кратчайшего маршрута движения транспортного средства заключается в идентификации соответствующей последовательности направлений движения транспортного средства относительно маркеров станций и ветвлений в транспортной сети с односторонними проездами, представляемой объединением транспортных петель, Целью изобретения является упрощение устройства выбора кратчайшего маршрута. Поставленная цель достигается тем, что устройство, содержащее блок 1 адресной памяти, счетчик 2, первый 3, второй 4, третий 5 и четвертый 6 блоки сравнения, сумматор 8, первый регистр 9, введены элемент И 7, второй регистр 10, первый и второй триггеры 11 и 12 .и элемент 2И-ИЛИ-HE 13, Использование устройства позволяет автоматизировать управление транспортными средствами в условиях частого измерения целевых установок. В частности, его можно использовать при реализации гибкого автоматического производства с его мелкосерийностью и частыми Сменами маршрутной технологии. 1 ил.

1 12

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

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

Цель изобретения — упрощение устройства выбора кратчайшего маршрута.

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

Устройство для выбора кратчайшего маршрута содержит блок 1 адресной памяти, счетчик 2, первый 3, второй 4, третий 5 и четвертый 6 блоки сравнения, элемент И 7, сумматор 8, первый регистр 9, второй регистр 10, первый 11 и второй 12 триггеры, элемент 2И-ИЛИ-НЕ 13 и генератор 14 импульсов. Информационными входами устройства, предназначенными для ввода соответственно кода станций отправления и станции назначения, являются вторые входы блоков 3 и 4 сравнения, шина запуска устройства соединена с входом запуска генератора 14 импульсов. Информационным выходом устройства, предназначенным для вывода результатов работы устройства в виде кода направления движения транспортного средства, является третий выход блока 1 адресной памяти. Осведомительным выходом устройства, предназначенным для вывода сигнала готовности к внешнему устройству, является первыи выход триггера 11, Входом устройства для запросов выдачи кодов маршрута движения служит четвертый вход элемента 2И-ИЛИ-НЕ 13.

Выход генератора 14 импульсов связан с первым входом элемента 2И-ИЛИНЕ 13, например один из двух элементов микросхемы 2И-ИЛИ-НЕ, второй и третий входы которого соединены соответственно с прямым и инверсным выходами триггера 11.

Счетный вход счетчика связан с выходом элемента 2И-ИЛИ-НЕ 13. Вход разрешения записи счетчика 2 связан с прямым выходом триггера 11, отку95412 2

45 разрешения записи регистра 10. По сигналу в этой цепи взводится триггер 12 и в регистр 10 происходит запись адреса с выхода счетчика 2.

Выход второго блока 4 сравнения

50 соединен с первым входом элемента И 7 происходит сброс триггера 11, Выход триггера 12 соединен с вторым входом

55 элемента И 7, а также с синхронизи5

30 да на счетчик 2 поступает сигнал разрешения записи. Группа установочных входов счетчика 2 подключена к вторым выходам младших разрядов регистра 9, по которому считываются младшие раз яды, содержащие адрес ячейки, хранящей код станции отправления в кратчайшем маршруте. Выход сигнала переполнения счетчика 2 связан с входом установки в "1" триггера 11 и входом останова генератора 14 импульсов. Этот сигнал взводит триггер 11 и сбрасывает генератор 14 импульсов, Информационный выход счетчика 2 связан с входом блока 1 адресной памяти. С помощью этой связи коды состояний счетчика 2 используются в качестве задающих адресов для блока 1 адресной памяти. Информационный выход счетчика 2 также связан с информационным входом регистра 10.

Первый выход блока 1 адресной памяти, по которому считываются данные из полей А (полей адреса маркера станции или разделителя), связан с первыми входами первого 3 и второго 4 блоков сравнения, а также с входом третьего 5 блока сравнения.

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

Выход блока 5 сравнения соединен с установочном входом сумматора 8 и с входом установки в "0" триггера 12, от него поступает сигнал, по которому происходи г сброс этих элементов при обнаружении разделителя петель в памяти. Выход первого блока 3 сравнения связан с входом установки в единицу триггера 12, а также с входом и с входом установки в "0" триггера

11. При наличии сигнала в этой цепи рующим входом сумматора 8. По этой цепи передается сигнал разрешения суммирования, з 1295

Выход сумматора 8 соединен с информационным входом старших разрядов регистра 9 и первым входом четвертого блока 6 сравнения. На этой шине постоянно присутствуют сигналы, пред †ставляющие текущее состояние сум— матора 8. Второй вход блока 6 сравнения связан с выходом старших разрядов регистра 9. Сигналы на этой шине постоянно представляют состоя- 10 ние старших разрядов регистра. Выход блока 6 сравнения связан с третьим входом элемента И 7, Сигнал в этой цепи присутствует лишь в случае, когда содержимое сумматора 8 меньше f5 данных, поступающих в блок 6 сравнения из регистра 9.

Вход разрешения записи регистра 9 соединен с выходом элемента И 7. По этой цепи передается сигнал разреше- 20 ния записи в регистр 9, по которому в его старшие разряды переписывается содержимое сумматора 8, в младшие— содержимое регистра 10. Третий вход регистра 9 соединен с выходом ре- 25 гистра 10. Сигналы на этой шине постоянно представляют содержимое регистр"". 10.

Устройство работает следующим образом, 30

При описании транспортной сети принята сквозная адресация (кодирование) станций и ветвлений в пределах всей транспортной сети и описание последней совокупностью всех возмбжных различающихся транспортных петель. Каждая транспортная петля описывается двухкратным последовательным перечислением адресов маркеров станций и ветвлений, проходимых при 40 движении вдоль транспортной петли в разрешенном направлении, В поле адресной памяти устройства описания транспортных петель располагаются в произвольном порядке не- 4> посредственно друг за другом и отде- ляются специально закодированными словами-разделителями. Слова, хранимые в блоке 1 адресной памяти, представляются тремя полями: полем адре- 50 са маркера станции или разделителя—

А; полем веса (длины) соответствующего элемента трассы — В; и полем кода направления движения — С. Элементом трассы считается участок трассы в пределах одной транспортной петли от предыдущего по ходу петли маркера до вассматриваемого. Код направления

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

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

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

Во втором регистре 10 записывается адрес маркера станции отправления в описании данной петли. Если длина маршрута в данном описании меньше длины маршрута, записанной в первом регистре 9, то адрес маркера станции отправления вместе с новой длииой маршрута перезаписывается в первый регистр 9, Работа устройства разбивается на

2 этапа — нахождение кратчайшего маршрута и выдача этого маршрута по

? 95412 6

45

5 t запросам от внешнего устройства (потребителя).

Использованию устройства предшествует формирование адресной памяти в блоке 1, сброс в нулевое состояние счетчика 2, сумматора 8, регистра 10 регистров 11 и 12, заполнение единицами всех разрядов регистра 9 и по дача на вторые входы первого 3 и вто рого 4 блоков сравнения адресов соответственно станции отправления и станции назначения.

При появлении сигнала на шине запуска начинает работать генератор 14 импульсов. Импульсы от него проходят через элемент 13, так как триггер 11 сброшен. Под действием этих сигналов счетчик 2 начинает просматривать адресную память 1. Как только в описании встретится адрес станции отправления, на выходе первого блока 3 сравнения появится сигнал, По этому сигналу взводится триггер 12 и адрес ячейки памяти, в которой хранится код станции отправления, записывается из счетчика 2 в регистр 10. С выхода триггера 12 на сумматор 8 поступает сигнал разрешения накапливания. Продолжается просмотр адресной памяти, в сумматоре 8 накапливается длина маршрута путем суммирования длин перегонов между маркерами.

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

Если при сравнении длины данного маршрута, находящегося в сумматоре 8, с содержимым регистра 9 (старшие разряды) окажется, что она меньше длины маршрута, хранимого в регистре 9,, то на выходе блока б сравнения появится единичный сигнал.

Сигналы с выходов триггера 12,, второго блока 4 сравнения и блока 6 сравнения поступают на вход элемента И 7, При наличии всех трех сигналов, что означает существование в рассматриваемои петле маршрута между станциями отправления и назначения и имеющего длину меньшую, чем у всех предыдущих маршрутов, на выходе элемента И 7 появится сигнал разрешения записи в регистр 9 длины данного маршрута из сумматора 8 и адреса ячейки памяти из регистра 10.

Если в описании этой петли еще раз встретится данный маршрут, то он еще раз вычисляется, но перезаписи не будет, так как он будет не меньше предыдущего. Если в описании петли не встретится код станции назначения, то при обнаружении разделителя на выходе блока 5 сравнения появится сигнал, по которому происходит сброс сумматора 8 и триггера 12.

Если в описании петли раньше кода станции отправления (и до разделителя, так как им оканчивается описание петли) встретится код станции назначения, то на выходе второго блока 4 сравнения появится сигнал, но так как триггер 12 не взведен, то на выходе элемента И 7 нулевой сигнал и никаких действий не производится, Когда просмотрена вся адресная память, появляется сигнал переполнения на. выходе счетчика 2, При наличии

20 этого сигнала триггер 11 взведен, а генератор импульсов 14 сброшен, В регистре 9 хранится длина кратчайшего маршрута и адрес ячейки памяти, в которой хранится код станции отправления, соответствующей этому маршруту, По сигналу на первом выходе триггера 11 произойдет запись в счетчик

2 из регистра 9 адреса ячейки памяти начала маршрута, выдача сигнала готовности к внешнему устройству, отклонение генератора 14 импульсов и подключение:внешнего устройства через элемент 13 к входу счетчика 2.

По каждому запросу внешнего устройства через элемент 13 подается импульс увеличения на единицу состояния счетчика 2, в результате чего адресуется слецующая ячейка блока 1 памяти и с его третьего выхода выдается следующий код направления движения, При достижении кода станции назначения на выходе блока 4 сравнения появляется сигнал, по которому происходит сброс триггера 11 и устройство переходит в свое исходное состояние, Формула изобретения

50 Устройство для выбора кратчайшего маршрута, соцержащее генератор импульсов, счетчик, блок адресной памяти, первый, второй, третий и четвертый блоки сравнения, накапливающий

55 сумматор и первый регистр, информационный выход счетчика соединен с входом адресной памяти, выход адреса маркера станции которого подключен к первым входам первого, второго и треСоставитель г.Сапунова

Техред И.Попович

Корректор М,Самборская

Редактор С.Патрушева

Тираж 673

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб,, д. 4/5

Подписное

Заказ 619/56

Производственно-полиграфическое предприятие, г,ужгород, ул. Проектная, 4

7 12954 тьего блоков сравнения, второй вход первого блока сравнения является входом кода станции назначения устройства, второй вход второго блока сравнения является входом кода станции отправления устройства, группа выходов накапливающего сумматора подключена к первой группе входов четвертого блока сравнения и к входам старших разрядов первого регистра, 10 вторая группа входов четвертого блока сравнения подключена к выходам старших разрядов первого регистра, отличающееся тем, что, с целью упрощения устройства, в него введены второй регистр, первый и второй триггеры, элемент И и элемент

2И-ИЛИ-НЕ, вход запуска генератора импульсов является входом запуска устройства, а выход генератора импульсов подключен к первому входу элемента 2И-ИЛИ-НЕ, второй вход которого подключен к инверсному выходу первого триггера, третий вход элемента 2И-ИЛИ-НЕ подключен к прямому входу первого триггера, а четвертый вход элемента 2И-ИЛИ-НЕ является входом кода маршрута движения устройства, выход элемента 2И-ИЛИ-НЕ подключен к счетному входу счетчика, вход разрешения записи которого подключен к инверсному выходу первого триггера, группа установочных входов .счетчика подключена соответственно к выходам младших разрядов первого ре- 35 гистра, информационный выход счетчи12 8 ка подключен к информационному входу второго регистра, выход сигнала переполнения счетчика подключен к входу останова генератора импульсов и к входу установки в " 1 первого триггера, инверсный выход которого является выходом сигнала готовности устройства, выход кода веса элемента трассы блока адресной памяти подключен к входу накапливающего сумматора, вход установки в "0" которого объединен с входом установки в "0" второго триггера и подключен к выходу третьего блока сравнения, второй вход которого является входом кода промежуточньж станций устройства, вход синхронизации накапливающего сумматора подключен к выходу второго триггера, вход установки в " 1" которого подключен к выходу первого блока сравнения, выход первого блока сравнения подключен к входу разрешения записи второго регистра, выход которого подключен к входам младших разрядов первого регистра, выход второго блока сравнения подключен к входу установки в "0" первого триггера и к первому входу элемента И, выход второго триггера подключен к второму входу элемента И, выход четвертого блока сравнения подключен к третьему входу элемента И, выход которого подключен к входу разрешения записи первого регистра, выкод кода направления движения блока адресной памяти является информационным выходом устройства,