Bakalaŭra disertaĵo pri programado per limigoj
junio 2019
Superrigardo
Ju pli da eblaj eventoj simulado enhavas, des pli da kondiĉoj ĝi devas ripete taksi. Sed se ĝia progreso establas, ke kondiĉo neniam plu povas veriĝi, ĉu eblas sekure preterlasi ĝin? Mi dezajnis kaj realigis metodon por HydLa, lingvo por modeligi hibridajn sistemojn, kiu uzas la direkton de variabloŝanĝoj por forigi kondiĉojn ne plu kontrolendajn.
En la taksa modelo, la metodo reduktis la rultempon proksimume je duono kompare kun la origina algoritmo, sen ŝanĝi la simulado-rezultojn. La plibonigo venis de uzo de la strukturo de la problemo por redukti la konsideratajn eblojn.
La perspektivo de programado per limigoj, evoluigita dum ĉi tiu esploro, nun subtenas mian aliron al la projektoj en mia verkaro: anstataŭ rekte specifi ĉiun rezulton, difini la regulojn, prioritatojn kaj limojn, poste derivi solvojn, kiuj kontentigas ilin.
Problemo: pli da ebloj signifas pli longan rultempon
HydLa priskribas hibridajn sistemojn, kiuj kunigas kontinuajn ŝanĝojn kaj diskretajn eventojn, per matematikaj kaj logikaj limigoj. Anstataŭ specifi ĉiun proceduran paŝon, la modelo deklaras la kondiĉojn plenumendajn, kaj la simulilo trovas konduton, kiu kontentigas ilin.
En modeloj kun multaj kondiĉaj reguloj, la simulilo ripete kontrolas grandan aron de kandidatoj. Eĉ kondiĉoj, kiuj ne plu povas veriĝi, restas en tiu aro. Ju pli la modelo kreskas, des pli tiuj nenecesaj kontroloj aldonas al la komputa laboro.
Modelo: kunigi kontinuan kaj diskretan ŝanĝojn
Resaltanta pilko estas simpla ekzemplo de hibrida sistemo. Ĝiaj pozicio kaj rapido ŝanĝiĝas kontinue dum ĝi estas en la aero, kaj frapo kontraŭ la planko ekigas diskretan resaltan eventon. Termostatoj, aŭtoj kaj robotoj ankaŭ kunigas tiujn du specojn de ŝanĝo, je malsamaj skaloj.
La taksado uzis modelon de pilko moviĝanta horizontale kaj resaltanta sur surfaco dividita en segmentojn. Ĉiu segmento havas kondiĉan regulon, kiu igas la pilkon resalti kiam ĝi atingas tiun areon. Aldoni segmentojn ebligas al la modelo reprezenti pli da objektoj, sed ankaŭ pliigas la nombron de kondiĉoj kontrolendaj de la simulilo.
Malhelpo: pli da kondiĉoj pliigas la rultempon
Regulo, kiu aktiviĝas nur kiam kondiĉo estas kontentigita, nomiĝas gardata limigo. En la taksa modelo, la resaltregulo de segmento aktiviĝas nur kiam la pilko atingas la plankon kaj ĝia horizontala pozicio troviĝas ene de tiu segmento.
Kiam la nombro de segmentoj kreskis de 10 ĝis 200, la rultempo de la origina simulilo kreskis proksimume laŭ la kvadrato de tiu nombro. Pli grandaj modeloj povas plifortigi tiun problemon, ĉar ili inkluzivas pli da objektoj, tuŝregionoj kaj eblaj eventoj.
Esploro: kien iris 96 % de la rultempo?
Profilado de la modelo kun 100 segmentoj montris, ke FindMinTime okupis 96 % de la tuta rultempo. Tiu proceduro trovas la plej fruan eblan sekvan eventon per ripeta taksado de ĉiuj kandidataj gardkondiĉoj.
Tio identigis konkretan plibonigeblon: sekure redukti la kandidatojn transdonatajn al FindMinTime. La celo estis preterlasi nur eblojn ne plu taksendajn, konservante la simulado-rezultojn.
Aliro: forigi kondiĉojn, kiuj ne povas denove veriĝi
Imagu pilkon resaltantan malsupren laŭ ŝtuparo. Post kiam ĝi preterpasis ŝtupon kaj daŭre iras antaŭen, tiu ŝtupo ne plu povas influi ĝin. Homo rigardanta la diagramon tuj ignoras la ŝtupojn malantaŭ la pilko; la origina algoritmo daŭre kontrolis ĉiun el ili.
La malfacila parto estas pruvi, ke forigita gardo ne estos bezonata poste. Forigi ĝin nur ĉar ĝi nun estas falsa povus nerimarkite produkti malĝustan rezulton, se ĝi denove veriĝos. La proponita metodo tial uzas monotonecon: ĉu oni povas garantii, ke variablo daŭre kreskos aŭ malkreskos dum difinita intervalo.
Kiam la direkto de ŝanĝo ne ŝanĝiĝas
La unua aliro aplikiĝas kiam variablo ŝanĝiĝas en unu direkto tra la tuta simulado. En la modelo kun segmentita surfaco, la horizontala pozicio de la pilko ĉiam kreskas. Post kiam ĝi preterpasis segmenton, la gardo de tiu segmento ne povas denove veriĝi. Teknikoj de modelkontrolado povas konfirmi tiun econ antaŭ simulado, ebligante sekure forigi gardojn kiam ili fariĝas ne plu koncernaj dum rulado.
Kiam la direkto de ŝanĝo inversiĝas
Multaj sistemoj ne ŝanĝiĝas en unu direkto senfine: variablo povas kreski, inversigi direkton kaj poste malkreski. La disertaĵo tial proponis duan aliron. Ĝi supozas direkton de ŝanĝo kaj kontrolas tiun supozon per asertoj. Kiam la direkto ŝanĝiĝas, la redukta procezo rekomenciĝas, restarigante gardojn forigitajn dum la antaŭa monotona intervalo. Tiu aliro estis dezajnita sed nek realigita nek taksita en ĉi tiu projekto.
Rezulto: proksimume duonigita rultempo en la taksa modelo
Mi realigis la aliron por unuforma monotoneco kaj taksis ĝin per la modelo kun segmentita surfaco. Rultempo kreskis kun la nombro de segmentoj ĉe ambaŭ algoritmoj, sed la proponita metodo konstante bezonis malpli da tempo. En la adaptitaj kurboj, la koeficiento de la plej altgrada termo malpliiĝis de 1,1463 al 0,6083. La tuta simuladotempo en tiu referenca testo estis proksimume duonigita.
La rezulto estas specifa al tiu referenca testo. La metodo utilas kiam modelo enhavas multajn gardatajn objektojn, la direkto de ŝanĝo estas pruvebla kaj gardoj fariĝas konstante ne plu koncernaj dum rulado. Tio ne implicas, ke ĉiu HydLa-modelo rulos duoble pli rapide.
Kion mi lernis
Ĉi tiu esploro uzis konatajn ecojn de la konduto de sistemo por redukti la aron de ebloj konsiderendaj de la simulilo. Mallarĝigi la serĉospacon konservante la rezultojn estas forto de programado per limigoj.
La realigo kaj taksado ampleksis variablojn, kiuj daŭre ŝanĝiĝis en unu direkto. Traktado de direktoinversiĝoj restis en la dezajna stadio kaj ankoraŭ bezonis taksadon. Ankaŭ ecoj krom monotoneco eble helpos identigi nenecesajn limigojn.
Tiu sperto kontribuas al mia nuna intereso dezajni la kondiĉojn kaj limojn, ene de kiuj AI povas serĉi solvojn. Laborante kun kompleksaj rezultoj, difini tion, kion oni povas sekure ignori, gravas same kiel difini tion, kion oni devas kalkuli.
Takafumi Horiuchi kaj Kazunori Ueda. “Dynamic Reduction of Guarded Constraints for the Hybrid Systems Modeling Language HydLa.” Proceedings of the 33rd Annual Conference of the Japanese Society for Artificial Intelligence, 2019. DOI: 10.11517/pjsai.JSAI2019.0_1E3OS3b02