Durant els anys 70, va aparèixer en el camp de la robòtica el concepte de robots modulars. Aquest, consisteix en sistemes robòtics que estan formats per diversos mòduls connectats, que poden tenir funcionalitats diferents. Aquests robots, també poden canviar la seva forma, recol·locant els seus mòduls.\newline Els robots modulars poden ser de molts tipus: arquitectura reticular, arquitectura en cadena o una barreja d'ambdues. A més a més, els mòduls poden variar en la seva forma. Quan es recol·loquen, cada mòdul pot moure's d'una forma diferent: comprimint-se, pivotant o lliscant. És per aquestes diferenciacions i l'habilitat de canviar de forma, que els robots modulars tenen un ampli ventall de possibilitats junt amb habilitats crítiques com l'adaptabilitat o la capacitat de fer feines diferents. Canviar de forma es una de les característiques més importants dels robots modulars, però també és on la major part dels problemes de computació resideixen. Per canviar de forma, els robots modulars poden fer ús de diferents mètodes: auto-reconfiguració, auto-ensamblament o desensamblament, embolcallament, etc. En aquest projecte ens centrem en l'auto-reconfiguració. L'objectiu d'aquest projecte és dissenyar i desenvolupar un algorisme de reconfiguració, centralitzat, per a mòduls amb forma quadrada i arquitectura reticular, que es mouen lliscant els uns sobre els altres, el qual reconfiguri una certa configuració C en una altra configuració, C', que tingui el mateix nombre de mòduls. Aquest procés de reconfiguració es pot dividir en tres parts diferents. Primer de tot, reconfigurem C en Rc, la qual és la configuració resultant de inundar la capsa contenidora de C de baix a dalt i d'esquerra a dreta amb el mateix nombre de mòduls. Després d'això, necessitem reconfigurar Rc en Rc', la configuració resultant de inundar la capsa contenidora de C'. Finalment, hem de reconfigurar Rc' en C'. Com el segon pas es un problema trivial de reconfiguració i el tercer pas és la inversió del primer, en aquest projecte ens hem centrat només en el primer pas. En aquest projecte hem analitzat els costos del nostre algorisme de forma tant teòrica com pràctica. Si n és el tamany de la graella d'entrada i m és el nombre mòduls del robot, el cost en computació de l'algorisme es O(n) i el nombre total de moviments fets pels mòduls del robot és O(m^2). Aquest límit està acotat.\newline En els experiments pràctics, vam executar l'algorisme amb diverses entrades de diferents tamanys i estructura. Els resultats mostren que contra més s'acosta m a n, més gran és el temps d'execució. De totes formes, quan tanquem tots els mòduls movibles a l'interior de les jerarquies de pseudo-forats augmenta el nombre de moviments realitzats durant la reconfiguració. |