TEMY pre obdobie 2006 - 2008

Andrej Lucny

Modelovanie kognicie pomocou reaktivnych agentov

3D rekonstrukcia sceny z pohybu mono a stereo kamery

Dipl.-Ing. PETER GEMEINER

Research assistant

ACIN | AUTOMATION & CONTROL INSTITUTE

INSTITUT F=DCR AUTOMATISIERUNGS- & REGELUNGSTECHNIK

TECHNISCHE UNIVERSIT=C4T WIEN

Gu=DFhausstra=DFe 27-29 | 376. 1040 Wien

Tel. +43 (0)1 58801 - 37667

Fax. +43 (0)1 58801 - 37699

gemeiner@acin.tuwien.ac.at | www.acin.tuwien.ac.at=20

Maria Markosova

Pocet riesitelov: 1 student

Skolitel: RNDr Maria Markosova, PhD

Popis zadania: V posledne jdobe sa vela bada v oblasti tzv. sieti maleho sveta [1] . Maju siroke moznosti aplikacii. Jednou z nich je aj tzv. "word net" [4,5] , kde sa lexikon jazyka chape ako graf. Ulohou projektu je pozriet sa na proces tvorby takejto siete pri uceni sa anglictiny [3].

Budeme analyzovat sposob, akym sa v procese ucenia slova pripajaju do slovnej zasoby [2]. Budeme zistovat, ci tvoriaci sa graf je prepojeny, budeme studovat ako sa menia jeho lokalne a globalne vlastnosti.

[1] Watts, Small Worlds, Princeton University Press, Princeton (2004)

[2] Barabasi, Albert, Science 286 (1999) 509

[3] Rozne ucebnice anglictiny a kurzy dostupne na internete

[4] Cancho, Sole, Proc. Royal. Soc.London B268 (2001) 2261

[5] Dorogovtsev, Mendes, Proc. Royal. Soc.London B269 (2001) 2603

Martin Takac

Peter Nather

Popis zadania: Vybrat alebo navrhnut vhodny algoritmus pre hladanie klastrov vo velkych grafoch, pricom klastre v grafe sa mozu navzajom prekryvat. 2D a 3D vizualizacia grafov so zvyraznenim ziskanych klastrov (volba a uprava vhodnych nastrojov pripadne vlastna impelmentacia). Jedna sa o grafy s velkym mnozstvom vrcholov a hran (asi stovky tisic). Vysledok sa vyuzije pri spracovani dat v oblasti vyskumu sieti maleho sveta.

[1] Q. Feng. Algorithms for Drawing Clustered Graphs. PhD thesis, Department of Computer Science and Software Engineering, University of Newcastle, Apr. 1997.

[2] Shamir, Sharan, Tsur, Cluster Graph Modification Problems (2002)

[3] Kanovsky Igor, Complex Networks Clustering and Edges Correlation. International Conference on Network Science (NetSci2006), Bloomington, Indiana, USA . May. 2006

[4] Jens Gramm, Jiong Guo, Falk Hffner, Rolf Niedermeier - Graph-Modeled Data Clustering: Fixed-Parameter Algorithms for Clique Generation (2003)

[5] Watts, Small Worlds, Princeton University Press, Princeton (2004)

Igor Farkas

1. Modelovanie semantickej pamati pomocou neuronovej siete.
2. Rekurzivne neuralne struktury pre reprezentaciu kontextu.
3. Modelovanie kognitivnej aktivity pomocou impulznej neuronovej siete.

Jan Sefranek

Dependency framework bol navrhnuty v [1,2] ako semantika pre multidimenzionalne dynamicke logicke programy resp. nemonotonne bazy znalosti. Ulohou diplomovej prace je - dotiahnut ho do vseobecneho tvaru (niektore casti boli rozpracovane iba pre elementarny pripad dvoch programov, z ktorych jeden predstavuje povodnu bazu znalosti a druhy jej update) a do relativne finalnej podoby. Porovnanie s Refined Semantics [3].

[1] Sefranek, Rethinking semantics of multidimenzional dynamic logic programming; Proc.NMR 2006

[2] Sefranek, Irrelevant updates and nonmonotonic assumptions, Proc. of JELIA 2006

[3] Alferes, Banti, Brogi, Leite: Refined extension principle. Studia Logica, 2005.

2. Implementacia (optimalizacia) nedeterministickeho algoritmu z [1]; jeho zlozitostna charakterizacia

ARCHIV

TEMY pre obdobie 2005-2007

• Martin Balaz
• Igor Farkas
• Andrej Lucny
• Marek Nagy
• Jan Sefranek
• Jozef Siska
• Martin Takac
• starsie temy

SW vybavenie autonomneho robota

Ide o cast projektu ktoreho cielom je cez webove rozhranie programovat v behavioralnom jazyku autonomneho robota na baze PC s OS Linux s vybavenim 7xIR, 2xservo, 1xkamera. Nevyzaduju sa ziadne hw vedomosti. Vyzaduje sa znalost jazyka Java, a vseobecna znalost OOP. Absolvovanie predmetu multiagentove systemy je vyhodou Seriozny pristup nevyhnutny

Rozpoznavanie chodcov z iduceho auta

Cielom je vyvoj a evaluaciu urcitych agentov v ramci multiagentoveho systemu na rozpoznavanie chodcov z iduceho auta. Tento system ma generovat zo sekvencie snimkov z kamery v aute sekvenciu 3D modelov v zmysle ramcovej reprezentacie. Konkretna uloha dohodou Poziadavky: znalost jazyka Java, zapisat si predmet multiagentove systemy.

Spracovanie dat z prenosneho meteorologickeho radaru

Meteorologicky radar poskytuje trojrozmernu informaciu o stave atmosfery. Tuto mozno vizualizovat a analyzovat meteorologom, s narastajucim poctom tychto zariadeni sa vsak coraz viac vyskytuje potreba automatickeho spracovania. V prvom rade ide o klasifikaciu a lokalizaciu meteorologickych javov (burka, smrst, dazd, krupy, ...). Pouzitelnost technik umelej inteligencie ako su neuronove siete, by tu mohla byt uzitocna. Konkretna uloha bude vyspecifikova po vzajomnej dohode. Podmienkou je akceptovatelnost pre hlavneho riesitela projektu, ktoreho bude tato diplomova praca sucastou. (Vzhladom na to ze ide o komercny subjekt je vitane aby diplomant nebol zamestnany v inej komercnej spolocnosti.)

Marek Nagy

Prostredie pre specifikaciu multiagentovych systemov

Diplomove prace su navrhovane v kontexte projektu, podporeneho grantom APVT. Ciele projektu mozno vidiet v niekolkych urovniach:

• Ide o pristup zalozeny na logike. Racionalne spravanie agentov sa pri tomto pristupe opiera o usudzovanie. Doraz budeme klast na nemonotonne usudzovanie, revizie, abdukciu (schopnost vysvetlovat) a usudzovanie za pritomnosti nekonzistentnosti. Rozne diplomove prace mozu konstruovat rozne usudzovacie schopnosti pre agentov (roznu "logiku agentov").
• Ocakava sa realny vystup projektu. Jeho odberatelom je firma Whitestein Technologies, ktora ma vlastnu platformu na implementaciu multiagentovych systemov ( LS/TS ). Pozadovanym vystupom je zosilnenie schopnosti LS/TS o moznosti deklarativnej specifikacie, zalozenej na logike.
• Vzhladom na to, ze logicke metody su z vypoctoveho hladiska neefektivne alebo malo efektivne, cielom je aj rozpracovat a realizovat model, ktory kombinuje logicke usudzovanie s rychlym, ale omylnem usudzovanim (podobne usudzuju ludia - iba malokedy pouzivaju dlhe odvodenia, spravidla pouzivaju nejake osvojene vzory, schemy). Islo by o originalny pristup, ktory suvisi so sucasnymi vyskumami v oblasti limitovanej racionality.

Temy su dostupne tu

STARSIE TEMY (obdobie 2004-2006)

"Busy Beaver" problem selekciou klonov

"Busy Beaver" problem znie: Aky je maximalny pocet jedniciek, ktore moze N-stavovy Turingov stroj napisat, ked zacne prazdnou paskou? N-stavovy stroj ktory napise maximalne mnozstvo jedniciek (a sam sa potom zastavi) sa vola "Busy Beaver".

Cielom prace je navrhnut taky evolucny algoritmus na zaklade klonalnej selekcie, spolu so specializovanym typom krizenia ohodnotenym grafom presentovaneho Turingovho stroja, ktory najde "Busy Beaver" co najmensim poctom pokusov (NP uplny problem).

Andrej Lucny

2. Kolektivne riesenie uloh skupinov robotov simulovanou vo VRML Ide o pouzitie a vylepsenie existujuceho prostredia na simulaciu robotov vo VRML za ucelom vykonanie experimentov pri ktorych vzajomne nekomunikujuce roboty riesia kolektivnu ulohu, napr. tlacia objekt k cielu alebo chytaju korist. Platforma: VRML + JavaScript + Ja va Poziadavky: uspesne zvladnutie predmetu multiagentove systemy, zaujem o virtualnu realitu

3. Evolucia pohybu robota po ciare. Cielom je naprogramovat system umoznujuci pouzitie genetickych algoritmov na vytvorenie riadiaceho systemu LEGO robota. Platforma: Lejos + Java Poziadavky: aktivna praca v robotickom laboratoriu.

Pavel Petrovic

2. Distributed computing pre evolucne algoritmy Evolucne algoritmy sa vyuzivaju na riesenie roznych zlozitych problemov, kde nepozname dostatocne rychly deterministicky ani vhodny aproximacny algoritmus. Kedze ide o slepe stochasticke prehladavanie, ma velke naroky na vypoctovu silu. Jednou moznostou je pouzit specializovane vypoctove clustre, ina cesta spociva vo vyuziti volnych CPU v pocitacoch v laboratoriach alebo miestnostiach, ktore sa vyuzivaju len niekolko hodin denne. Umoznuje to napriklad open-source nastroj Q2ADPZ (http://qadpz.sourceforge.net/), ktory je stale vo vyvoji. Cielom prace bude navrhnut vyuzitie nastroja QADPZ pre evolucne algoritmy - integrovat ho s vhodnou kniznicou pre paralelne geneticke algoritmy a demonstrovat to na vybranom priklade. Ocakava sa, ze sa autor zapoji do vyvoja, kde je viacero otvorenych oblasti - klient s naslednostou zadavanych uloh, scheduling uloh, cashovanie uloh, inteligentne migrovanie uloh medzi vypoctovymi uzlami, a pod. Poziadavka: C++.

3. Evolucia trojrozmernych struktur Problem navhrnutia struktury trojzmernych objektov zo zakladnych stavebnych blokov je mozne riesit pomocou evolucnych algoritmov. Zaujima nas celkova pevnost modelu zlozeneho z LEGO kociek. Existuje implementacia v C++, ktora navrhne rozlozenie LEGO kociek podla specifikovanych podorysov jednolivych vrstiev trojrozmerneho modelu. Cielom prace je rozsirenie tohoto projektu o: - dalsie LEGO kocky, ktore zasahuju do viacerych vrstiev a vytvaraju celkovy skeleton modelu - nove heuristiky, ktore zlepsuju a urychluju vysledok vypoctu - lepsie funkcie na vypocet pevnosti modelu, ktora je v sucasnosti urcena len heuristikami.

Jan Habdak

• zatriedenie hudby podla zanru, interpreta, albumu

• spusta digitalnych fotiek si vyzaduje nejaky sposob, ako zaradit fotografie do albumov.
• zatriedenie podla ludi, pamiatok, artefaktov.

• - travelling salesman - najdi co najrychlejsie miesta v bratislave a posli > ich obrazky (timy?)

• - unigramovy model, indexovanie slov v urcitom intervale
• - indexovanie dvojic (a n-tic) slov, ktore sa v indexe maju objavit
• - pre slovencinu?

Dalsie namety:
• Generator novych slov v jazyku
• 3d neuronove siete v subsumpcnej architekture
• Kompilacna praca support vector machines

Igor Farkas

Peter Borovansky

Martin Takac

1. Ochota pracovat priebezne
2. Anglictina na slusnej urovni (vysledny text DP aj priebezne reporty v anglictine)
3. Znalost programovania v JAVA

Marek Nagy

mozno si dohodnut aj inu temu (okrem uvedenych v specifikacii)

Tibor Hegedus

Jan Sefranek

Obdobie 2003-2005

Chitta Baral

http://www.public.asu.edu/~cbaral/

Splitting theorems for extensions of AnsProlog

Thomas Eiter

http://www.kr.tuwien.ac.at/staff/eiter/eiter.html 3 Master Theses in the frame of the Project

Optimizing Logic Programs under the Answer-Set Programming Paradigm

Scientific Context

With the rise of Answer Set Programming as a problem solving paradigm, in which solutions are computed in the answer sets of a non-monotonic logic program, a lot of research is nowadays being carried out in this area. A strength of this approach is its capability of dealing with nondeterminism in a simple manner, such that multiple solutions to a problem can be naturally generated. This has been exploited to model and solve problems which involve nondeterminism such as planning in nondeterministic domains [5;6], or in diagnosis of systems [7], to mention a few.

In fact, implementations of nonmonotonic logic-programming systems such as DLV [1], Smodels [2], or ASSAT [3], which have been built in the last years, led to the consideration of a wide range of practical applications. in nonmonotonic logic programming. Besides the applications mentioned above, other promising applications are e.g. in data-integration [4] or model checking [8], with other areas to be explored.

This increasing practical impact of Answer Set Programming has also renewed the interest in the study of foundational properties, and creates a need for improvement of the current algorithms for computing answer sets. One of the currently investigated links between theory and practice, which has a crucial role, is program optimization.

Program optimization deals with syntactic and semantic criterions which allow to simplify a given program. Simplifications can be considered as an elimination of redundant rules or redundant literals within a rule, as well as a rewriting of the entire program into a program of a simpler class (for instance, by elimination of disjunctions). There have been proposed different semantical notions of equivalence between logic programs (cf. [9,15,16]), including the important notions of strong equivalence [9] and uniform equivalence [16].

While optimization of logic programs as such is not new, previous work in the literature did not pay much attention (almost no) to negation in programs; in particular, unstratified negation as in non-monotonic logic programs for Answer Set Programming was not considered.

2. Project Goals

There is preliminary theoretical work [9,11,12] by the project leader on optimizing non-monotonic logic programs under the equivalences mentioned above, which describes some basic aspects as well as suggests some plain core algorithms for concrete realizations.

The goal of the proposed project is to deepen and complement this theoretical work, in particular in connection with experimental studies which indeed require a number of implementations. Among this needs is the realization of a general simplification algorithm which makes use of several important sub-modules, each of them testing whether and in which way a program can be simplified by a particular method. It is an open issue how these basic tests can be optimized themselves, in order to significantly improve answer set solving in the aforecited practical domains.

Simplifying logic programs enjoys a further important justification, when programs are automatically generated by domain-specific front-ends (for instance, the planning front-end DLV^K; see [5]), since in this case the burden of optimization is left to the underlying system, rather than to the programmer.

As a particular area to implement several simplification strategies, we plan to investigate their impact in the case of data integration [4], where we focus on the problem of query optimization.

3. Objectives and Expected Results

As an outcome of the project, a sophisticated implementation of a component-based simplification-toolbox is planned. The implementation should be done by students from Comenius-University of Bratislava. The students benefit from the scientific support they gain by visiting TU Wien.

The needed additional theoretical research should result in Master's Theses for each of the students and should be integrated to the current research at TU WIEN.

Joint scientific publications based on the results from the project are therefore expected as well.

References

[1] T. Eiter, W. Faber, N. Leone, and G. Pfeifer. Declarative Problem-Solving Using the DLV System. In J. Minker, ed., Logic-Based Artificial Intelligence, pp. 79-103. Kluwer, 2000. Link: http://www.dbai.tuwien.ac.at/proj/dlv/

[2] P. Simons, I. Niemel{\"a}, and T. Soininen. Extending and Implementing the Stable Model Semantics. Artificial Intelligence, 138:181-234, June 2002. Link: http://www.tcs.hut.fi/Software/smodels/

[3] F. Lin and Y. Zhao. ASSAT: Computing Answer Sets of a Logic Program by SAT Solvers. In Proc. AAAI-2002. AAAI Press / MIT Press, 2002. Link: http://assat.cs.ust.hk/

[4] T. Eiter, M. Fink, G. Greco, and D. Lembo. Efficient Evaluation of Logic Programs for Querying Data Integration Systems. Proc. ICLP-03. To appear.

[5] T. Eiter, W. Faber, N. Leone, G. Pfeifer, Axel Polleres. A Logic Programming Approach to Knowledge-State Planning, I+II. Tech.Rep. INFSYS RR-1843-03-11/12, TU Wien, 2003. Link: http://www.kr.tuwien.ac.at/research/reports/#2001 Link: http://www.dbai.tuwien.ac.at/proj/dlv/K/

[6] V. Lifschitz. Answer set planning. In Proc. ICLP-99 Link: http://www.cs.utexas.edu/users/vl/papers/asp.ps

[7] T. Eiter, W. Faber, N. Leone, and G. Pfeifer. The Diagnosis Frontend of the dlv-System, AI Communications, 12(1-2):99-111, 1999. Link: http://www.dbai.tuwien.ac.at/proj/dlv/

[8] K. Heljanko and I. Niemel=E4. Bounded LTL Model Checking with Stable Models. Theory and Practice of Logic Programming (TPLP), 3 (4&5): 519-550, 2003. Link: http://arXiv.org/abs/cs/0305040

[9] V. Lifschitz, D. Pearce, and A. Valverde. Strongly Equivalent Logic Programs. ACM Trans. on Computational Logic, 2(4):526--541, 2001. Link: http://www.cs.utexas.edu/users/vl/papers/ht.ps

[10] T. Eiter and M. Fink. Uniform Equivalence of Logic Programs under the Stable Model Semantics. Tech.Rep. INFSYS RR-1843-03-08, TU Wien, 2003. Short version in Proc. ICLP-03. To appear. Link: http://www.kr.tuwien.ac.at/research/reports/

[11] T. Eiter, M. Fink, H. Tompits, and S. Woltran. Simplifying logic programs under uniform and strong equivalence. Manuscript, submitted, July 2003.

[12] T. Eiter, M. Fink, H. Tompits, and S. Woltran. Eliminating Disjunction from Propositional Logic Programs under Stable Mod= el Preservation Manuscript, submitted, September 2003.

[13] Link: http://www.kr.tuwien.ac.at/research/infomix.html

[14] Link: http://wasp.unime.it/

[15] M.J. Maher. Equivalences of logic programs. In J.Minker, editor, Foundations of Deductive Databases and Logic Programming, pp. 627--658, Morgan Kaufmann, 1988.

[16] Y. Sagiv. Optimizing datalog programs In J.Minker, editor, Foundations of Deductive Databases and Logic Programming, pp. 659--698, Morgan Kaufmann, 1988.

[17] M. Osorio, J. Navarro, and J. Arrazola. Equivalence in Answer Set Programming In A. Pettorossi, ed., Proc. LOPSTR 2001, LNCS 2372, pp. 57--75. Springer, 2001.

Lubos Popelinsky

Caste vzory v sekvencnich datech

Cilem prace je

• 1. Podat prehled existujicich metod strojoveho uceni a statistickych metod pro vyhledavani castych vzoru - podsekvenci, logickych formuli - v sekvencnich datech,
• 2. Navrhnout a implementovat system pro hledani takovych castych podsekvenci.
• 3. Pouzit tento system pro analyzu sekvencnich dat, napr. posloupnosti Unixovskych prikazu, komunikace s webem, analyzu struktury molekul nebo textu.

Literatura:

• Sun R., Giles C.L.: Sequence Learning. LNCS Vol. 1828, Springer Verlag, 2001.
• clanky z konferenci

prof. ing. Vladimir Kvasnicka, DrSc.

Umela chemia a modelovanie evolucie molekul

Spolupraca a sutazenie v koaliciach agentov

Mikulas Popper

Aproximati­vna inferencia a heterogenne prostriedky reprezentacie neurcitosti

Inferencny mechanizmus na baze distribuovanych procesov

Gabriela Polcicova

Klastrovanie dokumentov pomocou pravdepodobnostnych modelov

1. Statisticky strojovy preklad z cestiny do slovenciny
   vytvorenie korpusov, bilingvalneho textu, jazykovy model, model prekladu.
2. Statisticky strojovy preklad z polstiny do slovenciny
   vytvorenie korpusov, bilingvalneho textu, jazykovy model, model prekladu.
3. Statisticky strojovy preklad z rustiny do slovenciny
   vytvorenie korpusov, bilingvalneho textu, jazykovy model, model prekladu.
4. Statisticke jazykove modely
   a) pre pribuzne jazyky
   b) na kontrolu textov
5. Kategorizacia textov
   zaradenie podobnych textov do skupin
6. Dizajn nabytku (novej stolicky, stola alebo dveri)
   pouzitie genetickeho programovania v interierovom dizajne

TEMY pre obdobie 2002-2004

Jan Habdak

Casova klasifikacia textov

Prof. RNDr. Jozef Gruska, DrSc.

• Specialne kvantove stavy a podpriestory.
• Kvantove kanaly a ich kapacity
• Kvantove katalyzatori a suprkatalyzatori
• Minimalne mnoziny quantovych stvaov generujuce reverzible ostatne stavy
• Vztahy medzi mierami bipartitneho entanglovania

Lubica Benuskova

Marian Vittek

Objektovo orientovane prepisovacie systemy pre C#

Systemy na prepisovanie termov su vseobecne rozsirenym formalizmom pouzivanym najma pri implementacii symbolickych manipulacii. V sucastnosti existuje niekolko nastrojov a programovacich jazykov umoznujucich efektivnu implementaciu prepisovacich systemov. Tieto jazyky vacsinou pracuju s predefinovanou reprezentaciou termov. Niektore najnovsie prace sa snazia aplikovat prepisovanie termov na existujuce datove typy beznych imperativnych programovacich jazykov, t.j. na struktury a objekty. Cielom diplomovej prace by bolo prehlbit tento vyskum a aplikovat ho na objekty jazyka C#.

Refaktorovanie deklarativnych programov

Refaktorovanie programov je zaujimava technika softweroveho inzinierstva rozsirujuca sa hlavne v oblasti objektovo orientovaneho programovania. Zakladom refaktorovania su modifikacie programov, ktore nemenia spravanie sa programu avsak skvalitnuju samotny kod. Napriklad extrakcia casti kodu do novej funkcie s automaticky generovanou hlavickou je refaktorovanie. Cielom diplomovej prace by bolo preskumat aplikaciu refaktorovania v prostredi deklarativneho programovania, t.j. v jazykoch ako Lisp, Prolog a Elan. Islo by hlavne o studium existujucicg refaktorovani, napr. extract funciu, hladanie redundantnych casti kodu (akasi unifikacia kodu) a skumanie novych cisto deklarativnych refaktorovani.

Referencia: Martin Fowler: Refactoring: Improving the Design of Existing Code.