Planificarea Miscarii Robotilor Industriali
=== anexa ===
A N E X A
//Proiect De Diploma
//Autor:Vitioanu Camelia
//Iunie 2001
#include <stdio.h>
#include <conio.h>
#include <graphics.h>
#include <alloc.h>
#include <dos.h>
#include <dir.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
typedef struct
{
char acoperit;
char left,top,right,bottom;
}
temp;
typedef struct tagRECT
{
int left;
int top;
int right;
int bottom;
} RECT;
typedef struct tagPOINT
{
int x;
int y;
} POINT;
char nume[9]="";
static int XSize=639,YSize=479;
int pix,piy,pfx,pfy;
int madonna[30];
int nv[30];
POINT * coord[30];
static RECT drept[30];
static int cx[62];
unsigned char * king, *king2;
int sepulture;
static unsigned char diesel[1280];
static unsigned char power[1024];
static unsigned char desperado[1280];
static int cy[62];
static int pete[400];
static int nrpete=0;
static int nrfiguri=0;
static int metoda=3;
static char grafspee[625];
static int start[6];
static int stop[6];
static int nstart,nstop,nways,noldways;
static int path[20],oldpath[20];
static char used[30];
static POINT inter;
unsigned char klf(int,int);
void intersect(int,int);
void solution(void);
int starter(int);
int stopper(int);
void bushido(int);
int klf2(int,int);
void breathe(int level);
void annodomini(int,int);
void chaosad(int,int);
void capone(void);
void getm(void);
void silver(void);
void Image(void);
void MakeRectangle(void);
void MakeCoords(void);
void InitPete(void);
void sakura(void);
int check(int,int);
void nou(void);
void open(char *);
void save(char *);
void fileselect(void);
void getname(char *);
void dealloc(void);
void button(int,int,int,int);
void cave(int,int,int,int);
void show(void);
void hide(void);
void intro(void);
int readcom(void);
int readmet(void);
void initdef(void);
void neo(void);
void paint(void);
void bun(int,int);
void main(void)
{
int gdriver=DETECT,gmode,errorcode;
int com,met;
strcpy(nume,"default");
initgraph(&gdriver,&gmode,"");
intro();
initdef();
do
{
com=readcom();
switch(com)
{
case 1:nou();break;
case 2:fileselect();break;
case 3:if(strlen(nume)==0)
getname(nume);
save(nume);
break;
case 4:paint();break;
case 5:met=readmet();
switch(met)
{
case 1:
cleardevice();
Image();
silver();
break;
case 2: cleardevice();
Image();
capone();
break;
case 3: neo();
break;
}
break;
}
}
while(com!=6);
dealloc();
closegraph();
}
void button(int left,int top,int right,int bottom)
{
setcolor(DARKGRAY);
setfillstyle(1,DARKGRAY);
bar(left,top,right,bottom);
setcolor(LIGHTGRAY);
moveto(left,bottom);
lineto(left,top);
lineto(right,top);
setcolor(BLACK);
lineto(right,bottom);
lineto(left,bottom);
}
void intro(void)
{
unsigned int b,x,y;
settextstyle(10,0,1);
button(100,100,540,400);
setcolor(BLACK);
outtextxy(145,100,"Descompunerea celulara");
outtextxy(220,140,"aproximativa");
setcolor(LIGHTGRAY);
outtextxy(146,101,"Descompunerea celulara");
outtextxy(221,141,"aproximativa");
button(240,320,400,360);
cave(120,200,520,280);
settextstyle(0,0,2);
outtextxy(308,334,"Ok");
settextstyle(0,0,1);
outtextxy(170,240," VITIOANU CAMELIA ");
show();
do
{
do
{
_AX=3;
asm int 33h
b=_BX;
x=_CX;
y=_DX;
}
while(b==0);
}
while(!((x>240)&&(x<400)&&(y>320)&&(y<360)));
hide();
cave(240,320,400,360);
show();
do
{
_AX=3;
asm int 33h
b=_BX;
x=_CX;
y=_DX;
}
while(b!=0);
hide();
}
void cave(int left,int top,int right,int bottom)
{
setcolor(BLACK);
moveto(left,bottom);
lineto(left,top);
lineto(right,top);
setcolor(LIGHTGRAY);
lineto(right,bottom);
lineto(left,bottom);
}
void show(void)
{
_AX=1;
asm int 33h
}
void hide(void)
{
_AX=2;
asm int 33h
}
int readcom(void)
{
int bool,b,x,y;
cleardevice();
button(240,10,400,40);
button(40,40,600,440);
cave(45,45,595,435);
setcolor(DARKGRAY);
moveto(240,40);
lineto(400,40);
button(240,80,400,120);
button(240,140,400,180);
button(240,200,400,240);
button(240,260,400,300);
button(240,320,400,360);
button(240,380,400,420);
cave(245,15,395,40);
settextstyle(1,0,2);
settextjustify(1,1);
outtextxy(320,25,nume);
settextjustify(1,1);
settextstyle(0,0,2);
outtextxy(320,95,"New");
outtextxy(320,155,"Open");
outtextxy(320,215,"Save");
outtextxy(320,275,"Paint");
outtextxy(320,335,"Run");
outtextxy(320,395,"Exit");
show();
do
{
bool=0;
do
{
_AX=3;
asm int 33h
b=_BX;
x=_CX;
y=_DX;
}
while(b==0);
if((x>240)&&(x<400))
{
if((y>80)&&(y<120)) bool=1;
if((y>140)&&(y<180)) bool=2;
if((y>200)&&(y<240)) bool=3;
if((y>260)&&(y<300)) bool=4;
if((y>320)&&(y<360)) bool=5;
if((y>380)&&(y<420)) bool=6;
}
}
while(!bool);
hide();
switch(bool)
{
case 1:cave(240,80,400,120);break;
case 2:cave(240,140,400,180);break;
case 3:cave(240,200,400,240);break;
case 4:cave(240,260,400,300);break;
case 5:cave(240,320,400,360);break;
case 6:cave(240,380,400,420);break;
}
show();
do
{
_AX=3;
asm int 33h
b=_BX;
x=_CX;
y=_DX;
}
while(b!=0);
hide();
// cleardevice();
return bool;
}
void initdef(void)
{
XSize=640;
YSize=480;
nrfiguri=3;
nv[0]=2;
coord[0]=(POINT *) malloc(2*sizeof(POINT));
(coord[0]+0)->x=200;
(coord[0]+0)->y=200;
(coord[0]+1)->x=350;
(coord[0]+1)->y=400;
nv[1]=2;
coord[1]=(POINT *) malloc(2*sizeof(POINT));
(coord[1]+0)->x=0;
(coord[1]+0)->y=11;
(coord[1]+1)->x=135;
(coord[1]+1)->y=135;
coord[2]=(POINT *) malloc(5*sizeof(POINT));
nv[2]=5;
(coord[2]+0)->x=410;
(coord[2]+0)->y=140;
(coord[2]+1)->x=430;
(coord[2]+1)->y=250;
(coord[2]+2)->x=480;
(coord[2]+2)->y=180;
(coord[2]+3)->x=445;
(coord[2]+3)->y=130;
(coord[2]+4)->x=410;
(coord[2]+4)->y=140;
}
void neo(void)
{
int i,j,b;
int x,y;
int mx,my,nx,ny;
char sir[30];
cleardevice();
MakeRectangle();
MakeCoords();
InitPete();
setfillstyle(9,15);
for(i=0;i<nrfiguri;i++)
bar(drept[i].left,drept[i].top,drept[i].right,drept[i].bottom);
setcolor(15);
for(i=0;i<2*nrfiguri+3;i++)
line(0,cy[i],640,cy[i]);
for(i=0;i<2*nrfiguri+3;i++)
line(cx[i],0,cx[i],480);
Image();
for(i=0;i<nrpete;i++)
{
setfillstyle(3,15);
bar(cx[pete[4*i]],cy[pete[4*i+1]],
cx[1+pete[4*i+2]],cy[1+pete[4*i+3]]);
rectangle(cx[pete[4*i]],cy[pete[4*i+1]],
cx[1+pete[4*i+2]],cy[1+pete[4*i+3]]);
settextjustify(1,1);
settextstyle(0,0,1);
sprintf(sir,"%c ",(char)(i+65));
outtextxy(cx[pete[4*i]]+(cx[1+pete[4*i+2]]-cx[pete[4*i]])/2,
cy[pete[4*i+1]]+(cy[1+pete[4*i+3]]-cy[pete[4*i+1]])/2,sir);
show();
do
{
_AX=3;
asm int 33h
b=_BX;
}
while(b==0);
do
{
_AX=3;
asm int 33h
b=_BX;
}
while(b==1);
hide();
setfillstyle(0,2);
bar(cx[pete[4*i]],cy[pete[4*i+1]],
cx[1+pete[4*i+2]],cy[1+pete[4*i+3]]);
for(j=0;j<2*nrfiguri+3;j++)
line(0,cy[j],640,cy[j]);
for(j=0;j<2*nrfiguri+3;j++)
line(cx[j],0,cx[j],480);
}
for(i=0;i<625;i++) grafspee[i]=0;
for(i=0;i<nrpete-1;i++)
for(j=i+1;j<nrpete;j++)
{
if((pete[4*i+3]>=pete[4*j+1])&&(pete[4*i+1]<=pete[4*j+1]))
{
if((pete[4*i+2]>=pete[4*j])&&(pete[4*i]<=pete[4*j]))
bun(i,j);
if((pete[4*j+2]>=pete[4*i])&&(pete[4*j]<=pete[4*i]))
bun(i,j);
}
if((pete[4*j+3]>=pete[4*i+1])&&(pete[4*j+1]<=pete[4*i+1]))
{
if((pete[4*i+2]>=pete[4*j])&&(pete[4*i]<=pete[4*j]))
bun(i,j);
if((pete[4*j+2]>=pete[4*i])&&(pete[4*j]<=pete[4*i]))
bun(i,j);
}
}
settextjustify(1,1);
for(i=0;i<nrpete-1;i++)
for(j=i+1;j<nrpete;j++)
if(grafspee[i*25+j]==1)
{
mx=cx[pete[4*i]]+(cx[1+pete[4*i+2]]-cx[pete[4*i]])/2;
my=cy[pete[4*i+1]]+(cy[1+pete[4*i+3]]-cy[pete[4*i+1]])/2;
nx=cx[pete[4*j]]+(cx[1+pete[4*j+2]]-cx[pete[4*j]])/2;
ny=cy[pete[4*j+1]]+(cy[1+pete[4*j+3]]-cy[pete[4*j+1]])/2;
setcolor((i+1)&7);
setlinestyle(4,0xff00,3);
line(mx,my,nx,ny);
setcolor((j+1)&7);
setlinestyle(4,0x00ff,3);
line(mx,my,nx,ny);
}
setlinestyle(0,0,1);
for(i=0;i<nrpete;i++)
{
mx=cx[pete[4*i]]+(cx[1+pete[4*i+2]]-cx[pete[4*i]])/2;
my=cy[pete[4*i+1]]+(cy[1+pete[4*i+3]]-cy[pete[4*i+1]])/2;
setfillstyle(1,(i&7)+1);
fillellipse(mx,my,7,7);
setcolor(14);
sprintf(sir,"%c ",(char)(i+65));
outtextxy(mx+5,my+1,sir);
}
show();
do
{
do
{
_AX=3;
asm int 33h
b=_BX;
}while(b==0);
do
{
_AX=3;
asm int 33h
b=_BX;
x=_CX;
y=_DX;
}while(b==1);
}
while(check(x,y));
hide();
pix=x;
piy=y;
setfillstyle(1,4);
fillellipse(pix,piy,4,4);
show();
do
{
do
{
_AX=3;
asm int 33h
b=_BX;
}while(b==0);
do
{
_AX=3;
asm int 33h
b=_BX;
x=_CX;
y=_DX;
}while(b==1);
}
while(check(x,y));
hide();
pfx=x;
pfy=y;
fillellipse(pfx,pfy,4,4);
show();
do{_AX=3;asm int 33h; b=_BX;}while(b==0);
do{_AX=3;asm int 33h; b=_BX;}while(b==1);
hide();
sakura();
}
void MakeRectangle(void)
{
int i,j;
for(i=0;i<nrfiguri;i++)
{
if(nv[i]==2)
{
drept[i].left=coord[i]->x;
drept[i].top=coord[i]->y;
drept[i].right=(coord[i]+1)->x;
drept[i].bottom=(coord[i]+1)->y;
if (drept[i].left>drept[i].right)
{
j=drept[i].left;
drept[i].left=drept[i].right;
drept[i].right=j;
}
if (drept[i].top>drept[i].bottom)
{
j=drept[i].top;
drept[i].top=drept[i].bottom;
drept[i].bottom=j;
}
}
else
{
drept[i].left=coord[i]->x;
drept[i].top=coord[i]->y;
drept[i].right=coord[i]->x;
drept[i].bottom=coord[i]->y;
for(j=1;j<nv[i];j++)
{
if(drept[i].left>(coord[i]+j)->x) drept[i].left=(coord[i]+j)->x;
if(drept[i].top>(coord[i]+j)->y) drept[i].top=(coord[i]+j)->y;
if(drept[i].right<(coord[i]+j)->x) drept[i].right=(coord[i]+j)->x;
if(drept[i].bottom<(coord[i]+j)->y) drept[i].bottom=(coord[i]+j)->y;
}
}
}
}
void MakeCoords(void)
{
int i,j,min;
cx[0]=cy[0]=0;
for(i=0;i<nrfiguri;i++)
{
cx[1+i*2]=drept[i].left;
cx[2+i*2]=drept[i].right;
cy[1+i*2]=drept[i].top;
cy[2+i*2]=drept[i].bottom;
}
cx[nrfiguri*2+1]=639;
cy[nrfiguri*2+1]=479;
for(i=1;i<nrfiguri*2;i++)
{
min=i;
for(j=i+1;j<nrfiguri*2+1;j++)
if(cx[min]>cx[j]) min=j;
j=cx[i];
cx[i]=cx[min];
cx[min]=j;
}
for(i=1;i<nrfiguri*2;i++)
{
min=i;
for(j=i+1;j<nrfiguri*2+1;j++)
if(cy[min]>cy[j]) min=j;
j=cy[i];
cy[i]=cy[min];
cy[min]=j;
}
}
void InitPete(void)
{
int i,j,k,l;
int sirpete[61];
temp tp1[100],tp2[100];
int ntp1,ntp2;
for(i=0;i<100;i++)
pete[5*i]=0;
ntp1=0;
for(i=0;i<2*nrfiguri+1;i++)
{
for(j=0;j<2*nrfiguri+1;j++) sirpete[j]=1;
for(j=0;j<nrfiguri;j++)
{
if( ( drept[j].top<=cy[i] ) && (drept[j].bottom>=cy[i+1]) )
{
k=0;
while(cx[k]!=drept[j].left) k++;
while(cx[k]!=drept[j].right)
sirpete[k++]=0;
}
}
k=0;
while(k<nrfiguri*2+1)
{
while(!sirpete[k]) k++;
tp1[ntp1].acoperit=1;
tp1[ntp1].top=(char)i;
tp1[ntp1].bottom=(char)i;
tp1[ntp1].left=k;
while((sirpete[k])&&(k<nrfiguri*2+1)) k++;
tp1[ntp1].right=k-1;
ntp1++;
}
}
nrpete=0;
for(i=0;i<nrfiguri*2;i++)
{
ntp2=0;
for(j=0;j<2*nrfiguri-i;j++)
for(k=0;k<ntp1;k++)
if(tp1[k].top==j)
for(l=k+1;l<ntp1;l++)
if(tp1[l].top==j+1)
{
if((tp1[l].left>=tp1[k].left)&&(tp1[l].left<=tp1[k].right))
{
tp2[ntp2].left=tp1[l].left;
tp2[ntp2].right=tp1[l].right<=tp1[k].right?tp1[l].right:tp1[k].right;
tp2[ntp2].top=tp1[k].top;
tp2[ntp2].bottom=tp1[l].bottom;
tp2[ntp2].acoperit=1;
if((tp1[k].left>=tp2[ntp2].left)&&(tp1[k].right<=tp2[ntp2].right))
tp1[k].acoperit=0;
if((tp1[l].left>=tp2[ntp2].left)&&(tp1[l].right<=tp2[ntp2].right))
tp1[l].acoperit=0;
ntp2++;
}
else
if((tp1[l].right>=tp1[k].left)&&(tp1[l].right<=tp1[k].right))
{
tp2[ntp2].right=tp1[l].right;
tp2[ntp2].left=tp1[l].left>=tp1[k].left?tp1[l].left:tp1[k].left;
tp2[ntp2].top=tp1[k].top;
tp2[ntp2].bottom=tp1[l].bottom;
tp2[ntp2].acoperit=1;
if((tp1[k].left>=tp2[ntp2].left)&&(tp1[k].right<=tp2[ntp2].right))
tp1[k].acoperit=0;
if((tp1[l].left>=tp2[ntp2].left)&&(tp1[l].right<=tp2[ntp2].right))
tp1[l].acoperit=0;
ntp2++;
}
}
for(j=0;j<ntp1;j++)
if(tp1[j].acoperit)
{
pete[nrpete*4]=tp1[j].left;
pete[nrpete*4+1]=tp1[j].top;
pete[nrpete*4+2]=tp1[j].right;
pete[nrpete*4+3]=tp1[j].bottom;
nrpete++;
}
ntp1=ntp2;
for(j=0;j<ntp2;j++)
tp1[j]=tp2[j];
}
for(j=0;j<ntp1;j++)
if((tp1[j].acoperit)&&(cx[tp1[j].left]<cx[1+tp1[j].right])
&&(cy[tp1[j].top]<cy[1+tp1[j].bottom]))
{
pete[nrpete*4]=tp1[j].left;
pete[nrpete*4+1]=tp1[j].top;
pete[nrpete*4+2]=tp1[j].right;
pete[nrpete*4+3]=tp1[j].bottom;
nrpete++;
}
}
void Image(void)
{
int i;
setfillstyle(1,15);
setbkcolor(0);
setcolor(15);
for(i=0;i<nrfiguri;i++)
switch(nv[i])
{
case 2:bar(coord[i]->x,coord[i]->y,(coord[i]+1)->x,(coord[i]+1)->y);
default:
fillpoly(nv[i],(int far *)(coord[i]));
}
}
void dealloc(void)
{
int i;
for(i=0;i<nrfiguri;i++)
free(coord[i]);
}
void paint(void)
{
int i,b,x,y,t,ox,oy,oox,ooy,c,busy,lx,ly;
unsigned char far * buff;
busy=0;
c=1;
cleardevice();
settextstyle(0,0,1);
Image();
t=1;
do
{
if(!busy) nv[nrfiguri]=2;
show();
do
{
_AX=3;
asm int 33h
b=_BX;
x=_CX;
y=_DX;
}
while(b==0);
if(busy)
{
oox=x;
ooy=y;
}
else
{
oox=ox=x;
ooy=oy=y;
}
if(c==1)
{
coord[nrfiguri]=(POINT *)malloc(2*sizeof(POINT));
coord[nrfiguri]->x=x;
coord[nrfiguri]->y=y;
}
else
if(!busy)
{
coord[nrfiguri]=(POINT *)malloc(10*sizeof(POINT));
coord[nrfiguri]->x=x;
coord[nrfiguri]->y=y;
}
switch(b)
{
case 2:
if(busy)
{
do
{
_AX=3;
asm int 33h
b=_BX;
}
while(b==2);
(coord[nrfiguri]+nv[nrfiguri]-1)->x=
(coord[nrfiguri])->x;
(coord[nrfiguri]+nv[nrfiguri]-1)->y=
(coord[nrfiguri])->y;
hide();
setcolor(15);
setfillstyle(1,15);
fillpoly(nv[nrfiguri],(int far *)coord[nrfiguri]);
show();
b=0;
nrfiguri++;
busy=0;
}
else
{
do
{
_AX=3;
asm int 33h
b=_BX;
}
while(b==2);
hide();
buff=(unsigned char far *)malloc(imagesize(x,y,x+120,y+150));
if(buff==NULL) return;
getimage(x,y,x+120,y+150,buff);
button(x,y,x+120,y+150);
button(x+20,y+20,x+100,y+50);
button(x+20,y+60,x+100,y+90);
button(x+20,y+100,x+100,y+130);
setcolor(LIGHTGRAY);
settextstyle(0,0,1);
settextjustify(1,1);
outtextxy(x+60,y+35,"Rectangle");
outtextxy(x+60,y+75,"Polygon");
outtextxy(x+60,y+115,"Done");
do
{
show();
do
{
_AX=3;
asm int 33h
b=_BX;
ox=_CX;
oy=_DX;
}
while(b==0);
hide();
c=0;
if((ox>x+20)&&(ox<x+100))
{
if((oy>y+20)&&(oy<y+50)) c=1;
if((oy>y+60)&&(oy<y+90)) c=2;
if((oy>y+100)&&(oy<y+130)) c=3;
}
switch(c)
{
case 1:
cave(x+20,y+20,x+100,y+50);
break;
case 2:
cave(x+20,y+60,x+100,y+90);
break;
case 3:
cave(x+20,y+100,x+100,y+130);
break;
}
do
{
_AX=3;
asm int 33h
b=_BX;
}
while(b==1);
}
while(c==0);
putimage(oox,ooy,buff,COPY_PUT);
free((void *)buff);
setcolor(15);
show();
}
break;
case 1:
if(c==1)
{
nv[nrfiguri]=2;
setwritemode(XOR_PUT);
hide();
do
{
oox=x;
ooy=y;
_AX=3;
asm int 33h
b=_BX;
x=_CX;
y=_DX;
if((oox!=x)||(ooy!=y))
{
rectangle(ox,oy,oox,ooy);
rectangle(ox,oy,x,y);
}
}
while(b==1);
(coord[nrfiguri]+1)->x=x;
(coord[nrfiguri]+1)->y=y;
nrfiguri++;
setcolor(15);
setfillstyle(1,15);
bar(ox,oy,x,y);
show();
setwritemode(COPY_PUT);
busy=0;
}
if(c==2)
{
hide();
setwritemode(XOR_PUT);
line(ox,oy,x,y);
do
{
oox=x;
ooy=y;
_AX=3;
asm int 33h
b=_BX;
x=_CX;
y=_DX;
if((oox!=x)||(ooy!=y))
{
line(ox,oy,oox,ooy);
line(ox,oy,x,y);
}
}
while(b==1);
(coord[nrfiguri]+nv[nrfiguri]-1)->x=x;
(coord[nrfiguri]+nv[nrfiguri]-1)->y=y;
ox=x;
oy=y;
nv[nrfiguri]++;
busy=1;
show();
setwritemode(COPY_PUT);
}
break;
default:
break;
}
hide();
setcolor(15);
}
while(c!=3);
}
void nou(void)
{
nrfiguri=0;
strcpy(nume,"");
}
void fileselect(void)
{
int done,i,j;
int nr,poz,max,sus,nolimits;
int b,x,y,mr;
char fn[900];
char pnume[8]="";
static ffblk tupac;
i=0;
done=findfirst("*.mec",&tupac,0);
while(!done)
{
j=0;
while(tupac.ff_name[j]!='.') fn[i*9+j]=tupac.ff_name[j++];
fn[i*9+j]=0;
i++;
done=findnext(&tupac);
}
max=33;
settextstyle(0,0,1);
button(240,45,400,440);
cave(250,60,350,80);
cave(250,90,350,430);
button(360,90,390,130);
button(360,390,390,430);
button(360,180,390,200);
button(360,220,390,240);
setcolor(LIGHTGRAY);
settextjustify(1,1);
outtextxy(375,190,"DA");
outtextxy(375,230,"NU");
moveto(375,95);
lineto(365,115);
lineto(385,115);
lineto(375,95);
moveto(375,425);
lineto(365,405);
lineto(385,405);
lineto(375,425);
nr=i;
poz=0;
do
{
button(360,90,390,130);
button(360,390,390,430);
setcolor(LIGHTGRAY);
moveto(375,95);
lineto(365,115);
lineto(385,115);
lineto(375,95);
moveto(375,425);
lineto(365,405);
lineto(385,405);
lineto(375,425);
nolimits=0;
settextjustify(1,1);
setcolor(LIGHTGRAY);
bar(251,61,349,79);
bar(251,91,349,429);
setcolor(LIGHTGRAY);
outtextxy(300,70,pnume);
sus=nr-poz<max?nr-poz:max;
for(i=0;i<sus;i++)
outtextxy(300,100+i*10,&fn[(poz+i)*9]);
show();
do
{
_AX=3;
asm int 33h
b=_BX;
x=_CX;
y=_DX;
}
while(b==0);
if((x>360)&&(x<390))
{
if((y>90)&&(y<130)) nolimits=1;
if((y>390)&&(y<430)) nolimits=2;
if((y>180)&&(y<200)) nolimits=3;
if((y>220)&&(y<240)) nolimits=4;
}
if((nolimits==2)&&(max+poz<nr)) poz++;
if((nolimits==1)&&(poz>0)) poz–;
if(nolimits==3)
if(strlen(pnume)>0)
{
strncpy(nume,pnume,8);
open(nume);
}
if((x>250)&&(x<350)&&(y>90)&&(y<430))
{
mr=(y-95) /10;
if((mr+poz+1)>nr)
{
}
else
{
strncpy(pnume,&fn[9*(mr+poz)],8);
}
}
do
{
_AX=3;
asm int 33h
b=_BX;
}
while(b==1);
hide();
}
while(nolimits<3);
nume[8]=0;
}
void open(char * name)
{
char fn[12];
int i,k,x,y;
FILE *f;
strncpy(fn,name,8);
k=strlen(name);
strcpy(fn+k,".mec");
dealloc();
f=fopen(fn,"rt");
fscanf(f,"%d\n",&nrfiguri);
for(i=0;i<nrfiguri;i++)
{
fscanf(f,"%d\n",&(nv[i]));
coord[i]=(POINT *)malloc(nv[i]*sizeof(POINT));
for(k=0;k<nv[i];k++)
{
fscanf(f,"%d %d\n",&x,&y);
(coord[i]+k)->x=x;
(coord[i]+k)->y=y;
}
}
fclose(f);
}
void save(char * name)
{
int i,k;
char fn[12];
FILE *f;
strncpy(fn,name,8);
k=strlen(name);
strcpy(fn+k,".mec");
f=fopen(fn,"wt");
fprintf(f,"%d\n",nrfiguri);
for(i=0;i<nrfiguri;i++)
{
fprintf(f,"%d\n",nv[i]);
for(k=0;k<nv[i];k++)
fprintf(f,"%d %d\n",(coord[i]+k)->x,(coord[i]+k)->y);
}
fclose(f);
}
void getname(char * name)
{
char prov[10];
char c;
int i,j,k,iesi;
button(200,180,440,260);
cave(220,200,420,240);
settextstyle(1,0,3);
settextjustify(1,1);
iesi=1;
k=0;
while(iesi)
{
c=getch();
if(isalnum(c))
{
prov[k]=c;
if(k<8) k++;
if(k<7) prov[k]=0;
else prov[8]=0;
setcolor(DARKGRAY);
bar(221,201,419,239);
setcolor(LIGHTGRAY);
outtextxy(320,220,prov);
}
if((c==8)&&(k>0))
{
prov[–k]=0;
setcolor(DARKGRAY);
bar(221,201,419,239);
setcolor(LIGHTGRAY);
outtextxy(320,220,prov);
}
if(c==13)
iesi=0;
}
strncpy(name,prov,9);
}
void bun(int i,int j)
{
grafspee[i*25+j]=1;
grafspee[j*25+i]=1;
}
int check(int x,int y)
{
int jones,i;
jones=0;
for(i=0;i<nrfiguri;i++)
if((x>=drept[i].left)&&(x<=drept[i].right)
&&(y>=drept[i].top)&&(y<=drept[i].bottom)) jones=1;
return jones;
}
void sakura(void)
{
int i;
int bx,by;
nstart=0;
nstop=0;
for(i=1;i<2*nrfiguri+2;i++)
if(pix<cx[i]) {bx=i-1;break;}
for(i=1;i<2*nrfiguri+2;i++)
if(piy<cy[i]) {by=i-1;break;}
for(i=0;i<nrpete;i++)
if((bx>=pete[4*i])&&(bx<=pete[4*i+2])
&&(by>=pete[4*i+1])&&(by<=pete[4*i+3]))
start[nstart++]=i;
for(i=1;i<2*nrfiguri+2;i++)
if(pfx<cx[i]) {bx=i-1;break;}
for(i=1;i<2*nrfiguri+2;i++)
if(pfy<cy[i]) {by=i-1;break;}
for(i=0;i<nrpete;i++)
if((bx>=pete[4*i])&&(bx<=pete[4*i+2])
&&(by>=pete[4*i+1])&&(by<=pete[4*i+3]))
stop[nstop++]=i;
nways=0;
noldways=30;
for(i=1;i<30;i++) used[i]=0;
for(i=0;i<nrpete;i++)
if (starter(i))
bushido(i);
cleardevice();
setfillstyle(10,7);
bar(0,0,639,479);
Image();
setcolor(0);
setfillstyle(0,0);
int j;
for(j=0;j<noldways;j++)
{
i=oldpath[j];
bar(cx[pete[4*i]],cy[pete[4*i+1]],
cx[1+pete[4*i+2]],cy[1+pete[4*i+3]]);
}
int a,b,c,d;
setcolor(4);
setlinestyle(0,0,3);
if((noldways>1)&&(noldways<30))
{intersect(oldpath[0],oldpath[1]);
line(pix,piy,inter.x,inter.y);
for(i=1;i<noldways-1;i++)
{
intersect(oldpath[i-1],oldpath[i]);
a=inter.x;
b=inter.y;
intersect(oldpath[i],oldpath[i+1]);
c=inter.x;
d=inter.y;
line(a,b,c,d);
}
intersect(oldpath[noldways-2],oldpath[noldways-1]);
line(inter.x,inter.y,pfx,pfy);
}
else
if(noldways==1)
line(pix,piy,pfx,pfy);
setcolor(15);
outtextxy(pix,piy,"Ci");
outtextxy(pfx,pfy,"Cf");
show();
do
{
_AX=3;
asm int 33h
b=_BX;
}
while(b==0);
do
{
_AX=3;
asm int 33h
b=_BX;
}
while(b==1);
hide();
setlinestyle(0,0,1);
}
void bushido(int k)
{
int i;
if(stopper(k))
{
path[nways++]=k;
solution();
nways–;
}
else
if(!used[k])
{
used[k]=1;
path[nways++]=k;
for(i=0;i<nrpete;i++)
if(grafspee[k*25+i])
bushido(i);
used[k]=0;
nways–;
}
}
int starter(int p)
{
int i,j;
j=0;
for(i=0;i<nstart;i++)
if(p==start[i]) j=1;
return j;
}
int stopper(int p)
{
int i,j;
j=0;
for(i=0;i<nstop;i++)
if(p==stop[i]) j=1;
return j;
}
void solution(void)
{
int i;
if(noldways>nways)
{
for(i=0;i<nways;i++)
oldpath[i]=path[i];
noldways=nways;
}
}
void intersect(int i,int j)
{
int min,ii,jj,aux;
int tab[5];
tab[1]=cx[0+pete[4*i]];
tab[2]=cx[1+pete[4*i+2]];
tab[3]=cx[0+pete[4*j]];
tab[4]=cx[1+pete[4*j+2]];
for(ii=1;ii<4;ii++)
{
min=ii;
for(jj=ii+1;jj<5;jj++)
if (tab[jj]<tab[min]) min=jj;
aux=tab[ii];
tab[ii]=tab[min];
tab[min]=aux;
}
inter.x=(tab[2]+tab[3])/2;
tab[1]=cy[0+pete[4*i+1]];
tab[2]=cy[1+pete[4*i+3]];
tab[3]=cy[0+pete[4*j+1]];
tab[4]=cy[1+pete[4*j+3]];
for(ii=1;ii<4;ii++)
{
min=ii;
for(jj=ii+1;jj<5;jj++)
if (tab[jj]<tab[min]) min=jj;
aux=tab[ii];
tab[ii]=tab[min];
tab[min]=aux;
}
inter.y=(tab[2]+tab[3])/2;
}
int readmet(void)
{
int b,x,y,a;
button(240,80,400,300);
button(260,140,380,170);
button(260,190,380,220);
button(260,240,380,270);
settextstyle(0,0,1);
settextjustify(1,1);
setcolor(LIGHTGRAY);
outtextxy(320,100,"Select the method");
outtextxy(320,155,"I");
outtextxy(320,205,"II");
outtextxy(320,255,"III");
show();
do{
do{
_AX=3;
asm int 33h
b=_BX;x=_CX;y=_DX;
}while(b==0);
a=0;
if((x>260)&&(x<380))
{
if((y>140)&&(y<170)) a=1;
if((y>190)&&(y<220)) a=2;
if((y>240)&&(y<270)) a=3;
}
}while(a==0);
switch(a)
{
case 1: cave(260,140,380,170);break;
case 2: cave(260,190,380,220);break;
case 3: cave(260,240,380,270);
}
do{
_AX=3;
asm int 33h
b=_BX;
}while(b==1);
hide();
return a;
}
unsigned char klf(int x,int y)
{
int zero,one,i;
unsigned int bitmap[255];
getimage(x*16,y*15,(x+1)*16-1,(y+1)*15-1,(void far *)bitmap);
zero=one=1;
for(i=0;i<60;i++)
if(bitmap[i+2]!=0xffff) one=0;
if(!one)
{
for(i=0;i<56;i++)
if(bitmap[i+2]!=0) zero=0;
if(zero) return 1;
return 3;
}
return 2;
}
void silver(void)
{
int i,j,b,x,y;
setlinestyle(0,0,1);
for(i=0;i<40;i++)
for(j=0;j<32;j++)
{
desperado[40*j+i]=0;
diesel[j*40+i]=klf(i,j);
}
for(i=0;i<40;i++)
for(j=0;j<32;j++)
{
line(i*16,0,i*16,479);
line(0,j*15,639,j*15);
}
getm();
setfillstyle(1,LIGHTGRAY);
for(i=0;i<40;i++)
for(j=0;j<32;j++)
if(diesel[j*40+i]==3)
bar(i*16,j*15,(i+1)*16-1,(j+1)*15-1);
show();
do{do{
_AX=3;
asm int 33h
b=_BX;
}while(b==0);
do{
_AX=3;
asm int 33h
b=_BX;
x=_CX;
y=_DX;
}while(b==1);
x=x/16;y=y/15;
}while(diesel[y*40+x]!=1);
pix=x;piy=y;
hide();
setfillstyle(1,4);
bar(x*16,y*15,(x+1)*16-1,(y+1)*15-1);
show();
do{
do{
_AX=3;
asm int 33h
b=_BX;
}while(b==0);
do{
_AX=3;
asm int 33h
b=_BX;
x=_CX;
y=_DX;
}while(b==1);
x=x/16;y=y/15;
}while(diesel[y*40+x]!=1);
pfx=x;pfy=y;
hide();
bar(x*16,y*15,(x+1)*16-1,(y+1)*15-1);
getm();
sepulture=0;
annodomini(pix,piy);
}
void getm(void)
{
int b;
show();
do
{_AX=3;
asm int 33h
b=_BX;
}while(b==0);
do
{_AX=3;
asm int 33h
b=_BX;
}while(b==1);
hide();
}
void capone(void)
{
int i,j,uno,zero,ii,jj,kolon,b,x,y;
setlinestyle(0,0,3);
king=(unsigned char *)malloc(1024);
for(i=0;i<32;i++)
for(j=0;j<32;j++)
{
power[j*32+i]=*(king+i*32+j)=(unsigned char)klf2(i*20,j*15);
}
setfillstyle(1,7);
setcolor(15);
for(i=0;i<32;i++)
for(j=0;j<32;j++)
{
if(*(king+i*32+j)==3)
{
bar(i*20,j*15,(i+1)*20,(j+1)*15);
rectangle(i*20,j*15,(i+1)*20,(j+1)*15);
}
}
king2=(unsigned char *)malloc(256);
setcolor(4);
for(kolon=2;kolon<17;kolon*=2)
{
breathe(kolon);
free(king);
king=king2;
}
free(king2);
if(king!=NULL) free(king);
line(320,0,320,479);
line(0,240,639,240);
rectangle(0,0,639,479);
setlinestyle(0,0,1);
show();
do{do{
_AX=3;
asm int 33h
b=_BX;
}while(b==0);
do{
_AX=3;
asm int 33h
b=_BX;
x=_CX;
y=_DX;
}while(b==1);
x=x/20;y=y/15;
}while(power[y*32+x]!=1);
pix=x;piy=y;
hide();
setfillstyle(1,4);
bar(x*20,y*15,(x+1)*20-1,(y+1)*15-1);
show();
do{
do{
_AX=3;
asm int 33h
b=_BX;
}while(b==0);
do{
_AX=3;
asm int 33h
b=_BX;
x=_CX;
y=_DX;
}while(b==1);
x=x/20;y=y/15;
}while(power[y*32+x]!=1);
pfx=x;pfy=y;
hide();
bar(x*20,y*15,(x+1)*20-1,(y+1)*15-1);
for(i=0;i<1024;i++) desperado[i]=0;
sepulture=0;
chaosad(pix,piy);
}
void breathe(int level)
{
int i,j,ii,jj,kill,blow,pusy;
int uno,zero;
kill=32/level;
blow=20*level/2;
pusy=15*level/2;
for(i=0;i<kill;i++)
for(j=0;j<kill;j++)
{
uno=0;
zero=0;
for(ii=0;ii<2;ii++)
for(jj=0;jj<2;jj++)
switch(*(king+(2*i+ii)*2*kill+2*j+jj))
{
case 1: zero=1;break;
case 2: uno=1;break;
case 3: uno=1;zero=1;break;
}
if(zero&&uno)
{
*(king2+i*kill+j)=3;
for(ii=0;ii<2;ii++)
for(jj=0;jj<2;jj++)
rectangle((2*i+ii)*blow,(2*j+jj)*pusy,
(2*i+ii+1)*blow,(2*j+jj+1)*pusy);
}
if(zero) *(king2+i*kill+j)=1;
if(uno) *(king2+i*kill+j)=2;
}
}
int klf2(int x,int y)
{
int i,j,uno,zero,g;
uno=zero=0;
for(i=x;i<x+20;i++)
for(j=y;j<y+15;j++)
{
g=getpixel(i,j);
if(g) uno=1;
else zero=1;
if(uno&&zero) return 3;
}
if(uno) return 2;
if(zero) return 1;
}
void annodomini(int x,int y)
{
int dx,dy,rx,ry;
if((x<0)||(x>39)||(y<0)||(y>31)) return;
if(sepulture) return;
if(desperado[40*y+x]==1) return;
if(diesel[y*40+x]!=1) return;
if((x==pfx)&&(y==pfy))
{
sepulture=1;
outtextxy(pix*16+8,piy*15+7,"Ci");
outtextxy(pfx*16+8,pfy*15+7,"Cf");
getm();}
else
{
desperado[40*y+x]=1;
rx=abs(pfx-x);
ry=abs(pfy-y);
if(x<pfx) dx=1;
else if(x==pfx) dx=0;
else dx=-1;
if(y<pfy) dy=1;
else if(y==pfy) dy=0;
else dy=-1;
setfillstyle(1,RED);
bar(x*16,y*15,(x+1)*16-1,(y+1)*15-1);
// getm();
if(dx==0)
{
bar(x*16,y*15,(x+1)*16-1,(y+1)*15-1);
annodomini(x,y+dy);
annodomini(x-1,y);
annodomini(x+1,y);
annodomini(x,y-dy);
desperado[40*y+x]=0;
setfillstyle(1,0);
bar(x*16,y*15,(x+1)*16-1,(y+1)*15-1);
return;
}
if(dy==0)
{
bar(x*16,y*15,(x+1)*16-1,(y+1)*15-1);
annodomini(x+dx,y);
annodomini(x,y-1);
annodomini(x,y+1);
annodomini(x-dx,y);
desperado[40*y+x]=0;
setfillstyle(1,0);
bar(x*16,y*15,(x+1)*16-1,(y+1)*15-1);
return;
}
annodomini(x+dx,y);
annodomini(x,y+dy);
if(rx>ry)
{
annodomini(x,y-dy);
annodomini(x-dx,y);
}
else
{
annodomini(x-dx,y);
annodomini(x,y-dy);
}
desperado[40*y+x]=0;
setfillstyle(1,0);
bar(x*16,y*15,(x+1)*16-1,(y+1)*15-1);
return;
}
}
void chaosad(int x,int y)
{
int dx,dy,rx,ry;
if((x<0)||(x>31)||(y<0)||(y>31)) return;
if(sepulture) return;
if(desperado[32*y+x]==1) return;
if(power[y*32+x]!=1) return;
if((x==pfx)&&(y==pfy))
{
sepulture=1;
setcolor(15);
outtextxy(pix*20+10,piy*15+7,"Ci");
outtextxy(pfx*20+10,pfy*15+7,"Cf");
getm();}
else
{
desperado[32*y+x]=1;
rx=abs(pfx-x);
ry=abs(pfy-y);
if(x<pfx) dx=1;
else if(x==pfx) dx=0;
else dx=-1;
if(y<pfy) dy=1;
else if(y==pfy) dy=0;
else dy=-1;
setfillstyle(1,RED);
bar(x*20,y*15,(x+1)*20-1,(y+1)*15-1);
// getm();
if(dx==0)
{
bar(x*20,y*15,(x+1)*20-1,(y+1)*15-1);
chaosad(x,y+dy);
chaosad(x-1,y);
chaosad(x+1,y);
chaosad(x,y-dy);
desperado[32*y+x]=0;
setfillstyle(1,0);
bar(x*20,y*15,(x+1)*20-1,(y+1)*15-1);
return;
}
if(dy==0)
{
bar(x*20,y*15,(x+1)*20-1,(y+1)*15-1);
chaosad(x+dx,y);
chaosad(x,y-1);
chaosad(x,y+1);
chaosad(x-dx,y);
desperado[32*y+x]=0;
setfillstyle(1,0);
bar(x*20,y*15,(x+1)*20-1,(y+1)*15-1);
return;
}
chaosad(x+dx,y);
chaosad(x,y+dy);
if(rx>ry)
{
chaosad(x,y-dy);
chaosad(x-dx,y);
}
else
{
chaosad(x-dx,y);
chaosad(x,y-dy);
}
desperado[32*y+x]=0;
setfillstyle(1,0);
bar(x*20,y*15,(x+1)*20-1,(y+1)*15-1);
return;
}
}
=== PMRItext ===
C A P I T O L U L 1
ASPECTE ALE PLANIFICĂRII MIȘCĂRII
Problema planificării mișcării unui robot mobil
Cercetarea roboților inteligenți, a roboților de servicii, constituie un domeniu de mare interes în prezent. Un robot trebuie să realizeze diferite sarcini fără a-i fi specificată fiecare acțiune care urmează să fie realizată [6]. Pentru a realiza un robot autonom, este necesar să fie sintetizate multe tehnici, inclusiv unele elemente de inteligență artificială. În mod obișnuit, robotul trebuie să obțină informații din lumea înconjurătoare folosind senzori vizuali și auditorii, să elaboreze un plan pentru executarea sarcinii date, să rezolve fenomenele neașteptate care vin fie din mediul exterior, fie de la robot și să învețe din experiență pentru a-și îmbunătăți performanțe [3], [5], [9], [56].
Problema planificării mișcării unui robot mobil este aceea a găsirii unei mișcări pentru un robot care trebuie să se deplaseze de la o configurație dată, la o destinație stabilită, într-un mediu care conține o mulțime de obstacole prestabilite, astfel încât robotul să nu intre în coliziune de nici unul din acestea. Într-o problemă concretă, obstacolele nu sunt întotdeauna statice, iar robotul nu poate fi modelat ca un singur obiect rigid, precum în cazul problemei de bază a planificării Este evident că un robot care se mișcă printre obstacolele mobile este capabil de performanțe mult mai mari și de o serie de sarcini mult mai complexe.
Această teorie are în vedere planificarea mișcării în medii de timp variabil unde atât obstacolele, cât și destinația, sunt în mișcare.
Abilitatea ocolirii obstacolelor în mișcare este indispensabilă pentru orice robot real [46]. Se consideră, spre exemplu, un robot tip mașină [42] ce se deplasează de-a lungul unui drum stabilit. Sistemul senzorial al robotului [20] poate dintr-o dată să depisteze un obiect mișcător care îi taie drumul. În cazul acesta ar trebui să fie capabil să producă și să execute o mișcare pentru a evita cu siguranță obiectul, astfel încât, prin frânare să lase obiectul să treacă pe lângă, sau prin accelerare să-l ocolească. De asemenea, într-un mediu echipat cu calculatoare, unui robot i se poate cere să ajungă la un obiect aflat în mișcare, în timp ce evită obstacolele aflate în mișcare. După cum se poate vedea din aceste exemple, abilitatea de a se descurca cu obstacolele în mișcare sporește semnificativ potențialul capacităților și șirul aplicațiilor unui robot inteligent [7].
Din punct de vedere tehnic, prezența obstacolelor în mișcare conduce la apariția unor noi aspecte privind problema planificării mișcării [21], [22], [26], [39]. De exemplu, când este implicată mișcarea obstacolelor, cel mai scurt drum nu se face întotdeauna în cel mai scurt timp [28], [29].
Optimizarea unei probleme de planificare, în contextul amintit, presupune un consum foarte mic de energie, dar, în același timp, trebuie să se acorde atenție și studiului vitezelor și accelerațiilor robotului mobil [8], [33], [35], [36], [43]. Astfel problema planificării mișcării printre obiecte mobile este în mai multe feluri diferită și mai complexă decât problema planificării mișcării cu obstacole staționare [2].
1.2. Metode de planificare a mișcării roboților mobili într-un spațiu de lucru populat cu obstacole fixe și/sau mobile
Problema planificării traiectoriilor în prezența obstacolelor poate fi enunțată astfel: fiind dat un spațiu de lucru populat cu obstacole cunoscute prin frontierele lor, respectiv cu obiecte mobile, trebuie să se determine o traiectorie fără coliziuni cu obstacolele, aducând obiectele mobile din configurația inițială în cea finală [13], [14], [37].
Problema poate fi abordată în două moduri (global sau local), de unde rezultă două tipuri de metode de planificare: globale și locale.
Aplicarea unei metode globale necesită cunoașterea completă “a priori” a spațiului de lucru, modelarea corespunzătoare a spațiului liber, cercetarea tuturor traiectoriilor posibile și selectarea unei anumite traiectorii corespunzătoare unui criteriu de cost minim. O astfel de metodă garantează existența sau inexistența unei soluții. De asemenea, metodele globale de planificare se pot adapta ușor la programarea off-line.
Aplicarea unei metode locale necesită cunoașterea parțială a spațiului de lucru. O astfel de metodă nu garantează atingerea configurației finale, dar prezintă avantajul unei bune adaptări în timp real.
În ambele cazuri, globale sau locale, rezolvarea problemei de planificare presupune rezolvarea unor probleme de natură geometrică (geometrie pură) sau de geometrie combinată cu cinematică și/sau dinamică. În astfel de situații se utilizează cu precădere rezultatele geometriei algoritmice.
Pentru un robot la un post de lucru fix [38], mobilele pentru care trebuie să se determine traiectoriile fără coliziuni sunt constrânse între ele de anumite legături. Astfel, o problemă de planificare este deci "a priori" complexă. Totuși, prin transformări adecvate, operate asupra obstacolelor, o problemă de planificare poate fi redusă la o problemă de "navigare" a unui robot punctiform, considerat ca un mobil liber care evoluează printre obstacolele transformate.
Astfel, planificarea traiectoriilor unui robot comportă, în general, două etape:
modelarea spațiului de lucru, transformarea obstacolelor (determinarea C-obstacole-lor) astfel încât robotul poate fi considerat ca un punct material;
cercetarea unei traiectorii, fără coliziune, pentru acest punct.
În cadrul unui sistem CAD/CAM dotat cu un algoritm de cercetare a spațiului liber se poate aplica planificarea traiectoriilor fără coliziuni, în mod interactiv cu operatorul, prin vizualizarea acestui spațiu.
În general, aplicarea unei metode de planificare trebuie să satisfacă anumite restricții, ca de exemplu: drumul cel mai sigur, drumul cel mai scurt, etc.
Metoda hărții drumurilor se bazează pe ideea captării conexității spațiului liber al robotului într-o rețea de curbe unidimensionale, numită harta drumurilor HD. Odată construită, aceasta este utilizată ca o bancă de traiectorii standard dintre care se alege aceea ce unește configurația inițială cu cea finală. Utilizând diferite principii constructive se obțin diferite tipuri de hărți ca: graful vizibilității, diagrama Voronoï, rețeaua drumurilor libere, siluetele, etc.
Metoda grafului vizibilității se aplică cu precădere la spații ale configurațiilor bidimensionale populate cu C-obstacole poligonale. Harta drumurilor este un graf numit graful vizibilității, construit prin conectarea tuturor perechilor de vârfuri din frontiera lui SCliber prin segmente de dreaptă, dacă aceste segmente nu traversează interiorul unui C-obstacol [13], [37], [50].
O altă metodă, ce constă din construirea unei hărți a drumurilor prin definirea unei aplicații continue (numită retractare) a lui SCliber pe HD se numește metoda retractării. Când spațiul configurațiilor este bidimensional, metoda conduce la retractarea lui SCliber la diagrama sa Voronoï. Aceasta este definită ca submulțime unidimensională a lui SCliber ce maximizează intervalele spațiale libere dintre robot și obstacole.
Metoda drumului liber este înrudită cu metoda retractării, punctul de referință al robotului fiind constrâns să rămână pe o rețea de segmente de dreaptă reminiscente dintr-o diagramă Voronoï [13], [37], [51].
Metoda siluetelor constă din schițarea unei siluete a spațiului liber al robotului când acesta este privit dintr-un punct situat la infinit și adăugând câteva segmente de curbă obținute prin unirea unor puncte critice ale siluetei cu alte porțiuni de curbă ale acesteia. Silueta și curbele de legătură formează harta drumurilor HD, care va fi cercetată în vederea găsirii unei traiectorii.
Toate metodele enumerate sunt deosebit de eficace în probleme de planificare în spații ale configurațiilor de dimensiuni mici (2 sau 3).
O altă metodă globală este metoda descompunerii celulare, cu ambele variante: descompunerea celulară exactă și descompunerea celulară aproximativă [12], [13], [15], [37]. Principiul acestei metode constă în descompunerea spațiului de lucru al robotului în celule. Descompunerea celulară exactă se bazează pe determinarea unor regiuni necritice, delimitate de curbe critice [12]. Reuniunea tuturor celulelor obținute este egală cu spațiul liber al robotului. Descompunerea celulară aproximativă se bazează pe metoda arborelui pentru descompunerea spațiului de lucru al robotului [17], [8], [41], [52]. În acest caz, reuniunea celulelor obținute este diferită de spațiul liber.
Una din cele mai atractive metode locale de planificare a mișcării roboților mobili este metoda câmpului potențial [10], [11], [16], [19], [23], [24], [25], [27], [30], [31], [32], [34], [37], [40], [44], [45], [48], [49], [53], [54], [55]. Această metodă tratează robotul, reprezentat ca un punct în spațiul configurațiilor, ca pe o particulă aflată sub influența unui câmp potențial artificial U, ale cărui variații locale reflectă "structura" spațiului liber. Funcția potențial este definită pe spațiul liber ca suma dintre un potențial atractiv, ce atrage robotul spre configurația finală, și un potențial repulsiv, ce îndepărtează robotul de obstacole.
Planificarea mișcării este făcută în mod iterativ. La fiecare iterație, forța artificială indusă de funcția potențial în configurația curentă este considerată ca direcția cea mai promițătoare a mișcării și generarea traiectoriei înaintează de-a lungul acestei direcții. Metoda a fost dezvoltată inițial ca o metodă "on line" de evitare a coliziunilor, aplicabilă când robotul nu are un model aprioric al obstacolelor, dar le poate sesiza în timpul execuției mișcării. În particular, procedura se poate bloca într-un minim local al funcției potențial, altul decât configurația finală, deoarece acționează ca o procedură rapidă.
Ideea câmpului potențial a putut fi asociată cu tehnici de cercetare a grafurilor, apoi, utilizând un model aprioric al spațiului de lucru, a putut fi transformată într-o metodă de planificare frecvent utilizată.
1.3. Planificarea mișcării roboților articulați, mobili, printre obstacole în mișcare
Se consideră că spațiul de lucru al robotului este populat atât cu obstacole staționare, cât și cu obstacole în mișcare. Se presupune că toate informațiile privind obstacolele sunt complet cunoscute. Se dorește să se planifice o mișcare pentru robot de la o configurație de start dată, la o configurație finală, în prezența acestor obstacole. Această problemă este “problema planificării dinamice a mișcării” [37], [47]. Când spațiul de lucru al robotului este populat doar cu obstacole staționare, problema este “problema planificării statice a mișcării”.
În problema planificării statice a mișcării, se determină un drum pentru robot astfel încât, în tot timpul mișcării drumul nu intersectează nici unul din obstacolele staționare. Termenul “traiectorie” este folosit uneori deoarece sunt necesare și informații despre viteza și accelerația robotului de-a lungul drumului. Pentru început este determinat un drum posibil, apoi, ținând seama de considerațiile dinamice, cum ar fi viteza și accelerația, se caută optimizarea acestuia. Într-un mediu dinamic, un drum liber la un moment dat poate să nu fie liber pentru o altă perioadă de timp. De aceea, în acest caz, drumul trebuie să fie specificat ca funcție de timp de la început.
În majoritatea cazurilor, criteriul de optimizare constă în minimizarea timpului de parcurgere a drumului de către robot, deoarece factorul de timp joacă un rol crucial în mediile dinamice.
Rezultatele cercetărilor efectuate indică faptul că planificarea mișcării printre obstacole în mișcare este în sine mai dificilă decât planificarea mișcării printre obstacole staționare [1]. Multe dintre problemele ce au de-a face cu obstacolele staționare pot fi rezolvate într-un timp polinomial, în timp ce câteva probleme de bază, care sunt cu obstacole în mișcare, nu sunt rezolvabile într-un timp polinomial. Totuși, există un număr de algoritmi care au fost propuși să rezolve problemele planificării dinamice a mișcării. Acești algoritmi lucrează în domenii limitate și produc o mișcare într-un timp polinomial.
Reif și Sharir [37] arată că problema planificării mișcărilor unui corp rigid tridimensional într-un mediu ce conține obstacole staționare și în mișcare este PSPACE–hard când viteza de mișcare a obiectului este ponderată și NP–hard nu este ca o graniță. De asemenea, planificarea dinamică a mișcării într-un plan se poate rezolva într-un timp O(n2(k+2)k), unde n este numărul total al vârfurilor și k este numărul total al obstacolelor din mediul respectiv. Cannz și Reif [37] au arătat că planificarea mișcării pentru un punct într-un plan cu viteză redusă este NP–hard, chiar și când obstacolele în mișcare sunt poligoane convexe mișcându-se cu viteze liniare constante.
Kant și Zucker [37] au propus primul algoritm practic pentru planificarea mișcării printre obstacolele în mișcare. Problema de planificare este divizată în două subprobleme: problema planificării drumului printre obstacole staționare și problema planificării vitezei de-a lungul unui drum fixat. În problema planificării drumului printre obstacole staționare se planifică un drum printre obstacole staționare în timp ce toate obstacolele în mișcare sunt ignorate. În problema planificării vitezei de-a lungul unui drum fixat este folosit un graf ordonat pentru a defini regiuni printre care un robot nu poarte să treacă când urmează drumul estimat. Poziția acestor regiuni influențează alegerea vitezei.
După cum Kant și Zucker au arătat, acestea sunt cazurile în care această apropiere eșuează în producerea unei mișcări chiar și atunci când acolo există mișcare. Acest lucru se întâmplă când o parte a unui obstacol coincide cu drumul fixat în prima parte. Aceasta pentru că drumul este fixat în a doua etapă; de aceea robotului nu i se permite să înconjoare obstacolul în mișcare. De asemenea, deoarece drumul este fixat în prima etapă, metoda propusă nu poate incorpora cu ușurință un punct de destinație aflat în mișcare.
Problema planificării dinamice a mișcării interacționează în unele cazuri cu o altă categorie de probleme, numite “problemele mișcării coordonate”. O astfel de problemă presupune planificarea mișcărilor coordonate pentru mai mulți roboți [4]. Această problemă este dinamică în sensul că cel ce planifică trebuie să ia în considerare mișcările mai multor roboți în același timp (Problema planificării mișcării roboților multipli), unde mai mulți roboti se mișcă independent în același spațiu de lucru, printre obstacole staționare. O abordare simplă conceptual a acestei probleme este de a considera diferiții roboți ca și componente ale unui robot compus și de a planifica un drum liber în spațiul configurațiilor acestui robot (planificare centralizată). Dificultatea acestei abordări constă în dimensiunea mare a spațiului configurațiilor, complexitatea temporală a planificării variind exponențial cu această dimensiune. Altă abordare constă în planificarea unui drum pentru fiecare robot, mai mult sau mai puțin independent față de ceilalți roboți, și considerând interacțiunile dintre drumuri (planificare decuplată). Această abordare reduce din calcul, dar se pierde din completitudinea algoritmului.
C A P I T O L U L 2
METODE DE PLANIFICARE A MIȘCĂRII ROBOȚILOR MOBILI ÎNTR-UN SPAȚIU CU OBSTACOLE FIXE
2.1. Drumul cel mai sigur. Diagrama Voronoi
Se presupune pentru început că obstacolele sunt modelate prin puncte. Trebuie să se determine o traiectorie care să permită mobilului punctiform să se deplaseze printre obstacole astfel încât să se afle în tot timpul mișcării la distanță maximă față de obstacole. Traiectoria obținută este formată din segmentele diagramei Voronoi a punctelor obstacolelor.
Fie o mulțime finită de n puncte X = {X1, …, Xn} în Rp, unde p este dimensiunea spațiului. Diagrama Voronoi (DV) este un "caroiaj" în Rp, format din celulele Ki, i=1, …, n definite prin:
Ki = {X Rp / d(X',Xi) d(X',Xj), j i}
unde d(X',Xi) este distanța euclidiană între punctele X' și Xi.
Se poate arăta că în R2 diagrama Voronoi (DV) nu are mai mult de 2n-5 vârfuri, respectiv 3n-6 laturi. Vârfurile diagramei Voronoi sunt centrele tuturor cercurilor construite determinate de trei puncte mi echidistante și care nu conțin nici-un alt punct.
În vecinătatea obstacolelor, robotul se poate deplasa pe laturile (DV). Acestea reprezintă locul cel mai sigur unde robotul evită coliziunile. Pentru a planifica traiectoria, trebuie rezolvate două probleme:
elaborarea unor algoritmi eficace pentru cercetarea (DV);
alegerea, dintre toate drumurile posibile, a drumului minim.
Se poate generaliza diagrama Voronoi la un ansamblu de C-obstacole care nu mai sunt modelate ca puncte. "Caroiajul" format din celulele Ki, i=1, …, n, definite în aceeași manieră:
Ki = {X Rp / d(X', SCBi) d(X', SCBj), j i}
unde d(X', SCBi) este distanța euclidiană de la punctul X' la C-obstacolul SCBi, determină (DVG).
Într-un spațiu de lucru bi-dimensional, când C-obstacolele sunt modelate ca poligoane, (DVG) este formată din segmente de dreaptă și parabole. Astfel, un punct X', aflat la frontiera între două celule poate fi:
la egală distanță de două vârfuri de C-obstacol. Locul lui X' este local un segment de
dreaptă (mediatoarea segmentului ce unește cele două vârfuri);
la egală distanță de vârful unui C-obstacol și latura altui C-obstacol. Locul lui X' este local o parabolă (vârful este focarul, iar latura este axa parabolei);
la egală distanță de două laturi de C-obstacol. Locul lui X' este local un segment de dreaptă (bisectoarea unghiului format de cele două laturi).
Cercetarea diagramei Voronoi conduce deci la determinarea drumului "cel mai sigur".
2.2. Metoda grafului vizibilității (GV)
Prezentarea metodei. Construcția grafului
Se consideră un obiect poligonal A ce translatează în spațiul de lucru bidimensional W = R2. În acest caz, spațiul configurațiilor lui A este SC=R2, iar regiunea SCB a C-obstacolelor este o regiune poligonală a lui R2. Spațiul SCliber este complementara lui SCB pe SC .
Deoarece metoda grafului vizibilității necesită cunoașterea tuturor C-obstacolelor a priori, poate fi calificată ca o metodă globală.
Principiul metodei constă în construirea unei traiectorii semilibere ca o linie poligonală ce conectează configurația inițială Cinițial de configurația finală Cfinal, trecând prin vârfuri ale lui SCB [13], [37].
Dacă există o astfel de traiectorie, atunci cu siguranță va exista o traiectorie semiliberă T de lungime euclidiană minimă între aceste două configurații. Pentru ca traiectoria T să fie cea mai scurtă, ea trebuie să fie formată din subtraiectorii care să fie cele mai scurte posibil între două configurații date. Aceasta înseamnă că, în orice configurație C, traversată de T, dacă C nu este un vârf al lui SCB, T trebuie să aibă curbura nulă. Deci, vârfurile traiectoriei poligonale T sunt vârfuri ale lui SCB.
Este astfel evident că pentru a găsi o traiectorie semiliberă între oricare două configurații este suficient pentru un planificator să considere liniile poligonale ce unesc vârfurile lui SCB. Această mulțime de linii poligonale, numită graf al vizibilității, conține cu siguranță și cea mai scurtă traiectorie (figura 2.1).
Figura 2.1. Construcția grafului vizibilității.
Figura ilustrează graful vizibilității în cazul unui spațiu al configurațiilor simplu, în care SCB constă din trei regiuni separate. Legăturile grafului includ și muchiile lui SCB. Traiectoria cea mai scurtă între Cinițial și Cfinal este reprezentată cu linie îngroșată.
Din cele precizate rezultă că graful vizibilității este graful neorientat (GV), definit astfel: nodurile lui (GV) sunt Cinițial, Cfinal și vârfurile lui SCB; două noduri ale lui (GV) sunt conectate printr-o legătură, dacă și numai dacă, fie segmentul de dreaptă ce le unește este o muchie a lui SCB, fie se află în întregime în SCliber, condiție de la care sunt exceptate cele două capete.
Graful vizibilității redus
Eficiența metodei grafului vizibilității poate fi crescută observând că unele legături nu sunt necesare. Pentru simplificarea suplimentară a grafului vizibilității mai este necesară introducerea noțiunii de segment tangent la SCB într-un vârf X. Astfel, dacă X este un vârf al lui SCB și L este un segment de dreaptă ce trece prin X, L este tangent la SCB în X dacă și numai dacă într-o vecinătate U a lui X interiorul lui SCB se află în întregime de o singură parte a lui L.
Între două poligoane convexe disjuncte există exact patru segmente tangente:
două sunt segmente tangente "suport", cele două poligoane aflându-se de aceeași parte a dreptei care conține segmentul;
două sunt segmente tangente "separatoare", cele două poligoane aflându-se pe părți diferite ale dreptei care conține segmentul.
Dacă un vârf X este concav, atunci nici un segment tangent nu se termină în X.
Se poate proceda astfel la o simplificare a lui (GV) observând că, dacă un segment între X și X' nu este tangent, el nu trebuie introdus în graful de cercetat.
Subgraful (GV'), obținut din (GV) prin înlăturarea tuturor segmentelor netangente și a tuturor vârfurilor concave, se numește graful vizibilității redus. De câte ori există o traiectorie semiliberă între Cinițial și Cfinal, (GV') conține cea mai scurtă traiectorie între aceste configurații.
Graful vizibilității redus este graful neorientat (GV') definit astfel: nodurile sunt Cinițial , Cfinal și toate vârfurile convexe ale lui SCB; legăturile sunt muchiile lui SCB ce conectează vârfurile convexe și segmentele tangente între Cinițial , Cfinal și vârfurile lui SCB ce se află în spațiul liber.
Extinderea metodei grafului vizibilității
Metoda grafului vizibilității poate fi extinsă în cazul în care C-obstacolele sunt "poligoane generalizate", adică regiuni mărginite de segmente de dreaptă și/sau arce de cerc. Astfel de C-obstacole apar când A este un poligon generalizat care translatează printre obstacole modelate de asemenea ca poligoane generalizate. Modelarea obiectelor din W ca poligoane generalizate este mai frecvent utilizată deoarece caracterizează cu fidelitate conturul acestora și conduce la o precizie mai bună.
Se consideră SC=R2 populat cu C-obstacole de tip poligoane generalizate, a căror reuniune este SCB.
Figura 2.2 prezintă graful vizibilității redus pentru același spațiu al configurațiilor ca și figura 2.1.
Graful vizibilității (redus) generalizat (GV'G) este definit astfel:
Cinițial, Cfinal și vârfurile convexe ale lui SCB sunt nodurile lui (GV'G);
Fie X și X' două noduri din cele definite mai sus. Dacă segmentul deschis care unește X și X' se află integral în SCliber și este un segment tangent la SCB, atunci el este o legătură a lui (GV'G);
Fie X un nod din cele definite mai sus și E' o latură circulară a lui SCB. Dacă există un punct X' care aparține lui E', astfel încât segmentul deschis care unește X și X' se află integral în SCliber și dreapta suport a acestui segment este tangentă la SCB în X și X', atunci punctul X' este nod al lui (GV'G) și segmentul care unește X și X' este o legătură a lui (GV'G);
Fie E și E' două laturi circulare ale lui SCB. Dacă există un punct X în E și un punct X' în E', astfel încât segmentul deschis care unește X și X' se află integral în SCliber și dreapta suport a acestui segment este tangentă la SCB în X și X', atunci cele două puncte X și X' sunt noduri ale lui (GV'G) și segmentul care le unește este o legătură a lui (GV'G);
Fiecare latură dreaptă a lui SCB, care conectează două vârfuri convexe, este o legătură a lui (GV'G);
Fiecare două noduri X și X' ale lui (GV'G), conținute în aceeași latură circulară E a lui SCB, sunt conectate printr-o legătură în (GV'G), dacă nu există un alt nod X" al lui (GV'G) care se află în E, între X și X'.
În figura 2.3 este prezentat graful vizibilității redus generalizat pentru un spațiu al configurațiilor SC=R2, populat cu C-obstacole de tip poligoane generalizate.
Figura 2.3. Graful vizibilității redus generalizat pentru un spațiu al configurațiilor SC=R2, populat cu C-obstacole de tip poligoane generalizate.
Se poate arăta că există o traiectorie semi-liberă între Cinițial și Cfinal dacă și numai dacă există o traiectorie între aceste două noduri în (GV'G). În plus, dacă există o traiectorie semi-liberă, atunci (GV'G) o conține pe cea mai scurtă.
Când metoda grafului vizibilității se aplică într-un spațiu al configurațiilor poliedric se pot obține traiectorii mai scurte adăugând vârfuri fictive, astfel încât nici o muchie ce rezultă în felul acesta să nu fie mai lungă decât o anumită lungime prespecificată.
Metoda grafului vizibilității nu se poate aplica în cazul când robotul modelat ca un poligon translatează și se rotește în spațiul de lucru bidimensional printre obstacole poligonale. În acest caz, spațiul configurațiilor SC = R2 x S1, iar C-obstacolele sunt regiuni tridimensionale mărginite de suprafețe curbe riglate. Pentru a trata rotația, metoda poate fi combinată cu alte tehnici. Metoda grafului vizibilității a fost rareori folosită pentru planificarea mișcărilor într-un spațiu al configurațiilor de dimensiune mai mare decât doi. În acest caz sunt mai potrivite alte metode.
2.3. Metoda retractării
2.3.1. Principiul metodei retractării
Principiul metodei retractării constă în definirea unei aplicații continue a lui SCliber pe o rețea de curbe unidimensionale HD în SCliber. Noțiunea de retractare este clasică în topologie. Astfel, dacă este un spațiu topologic și o submulțime a sa, aplicația surjectivă se numește retractare de la la dacă și numai dacă este continuă, iar restricția sa la n este aplicația identitate. Dacă este o retractare a spațiului topologic la , ea păstrează conexitatea lui dacă și numai dacă pentru orice x, x și r(x) aparțin aceleiași componente conexe a lui .
Se consideră o retractare a lui SCliber ce păstrează conexitatea definită prin aplicația : SCliber HD, unde HD SCliber reprezintă o rețea de curbe unidimensionale. Între două configurații libere Cinițial și Cfinal există o traiectorie liberă dacă și numai dacă există o curbă în HD între (Cinițial) și (Cfinal) [13], [37].
Fie T:[0,1] SCliber o traiectorie liberă între Cinițial și Cfinal. Se aplică lui T. Datorită continuității lui se obține o altă traiectorie liberă T: [0, 1] HD între (Cinițial) și (Cfinal). Invers, dacă există o traiectorie în HD între (Cinițial) și (Cfinal), atunci Cinițial și Cfinal sunt conectate printr-o traiectorie liberă care este produsul a trei traiectorii:
traiectorie liberă de la Cinițial la (Cinițial);
traiectorie de la (Cinițial) la (Cfinal) în HD;
traiectorie liberă de la (Cfinal) la Cfinal.
Prima și a treia din aceste traiectorii există deoarece conservă conexitatea lui SCliber.
Eficiența metodei retractării este deci determinată de alegerea aplicației . Pentru aplicarea metodei este necesar un algoritm pentru construirea reprezentării de tip graf a lui HD, pentru calculul aplicațiilor (Cinițial) și (Cfinal) și pentru generarea traiectoriilor libere de la Cinițial la (Cinițial), respectiv de la (Cfinal) la Cfinal.
Exemplificarea metodei retractării pentru SC poligonal
Se exemplifică metoda retractării în SC = R2, pentru cazul în care SCliber este interiorul unei regiuni poligonale mărginite. Construirea reprezentării de tip graf constă din retractarea lui SCliber la diagrama sa Voronoi care se construiește maximizând spațiile neocupate dintre robot și obstacole.
Figura 2.3 prezintă un exemplu de diagramă Voronoi constituită din mulțimea punctelor a căror distanță minimă la frontiera lui SCliber este obținută pentru mai mult de un punct din această frontieră.
Când SCliber este o regiune poligonală mărginită, ca în cazul din figură, diagrama Voronoi constă din segmente de dreaptă și arce de parabolă. Un segment de dreaptă este format din mulțimea configurațiilor care sunt cele mai apropiate de aceeași pereche de vârfuri sau de laturi. Spre exemplu, segmentul de dreaptă S1 este cel mai apropiat de laturile E3 și E7. Un arc de parabolă este mulțimea configurațiilor care sunt cele mai apropiate de aceeași pereche, constând dintr-un vârf și o latură. Spre exemplu, arcul S2 este cel mai apropiat de latura E8 și vârful X5.
Perechile de elemente (latură, latură), (vârf, vârf) sau (latură, vârf) determină ecuațiile segmentelor de dreaptă sau de parabolă ce constituie diagrama.
Se consideră un SCliber a cărui frontieră prezintă n vârfuri. Construirea diagramei Voronoi se realizează considerând toate perechile de vârfuri și laturi și calculând intersecțiile curbelor echidistante corespunzătoare.
Dacă se cunosc configurațiile inițială și finală este necesar să se determine punctele (Cinițial) și (Cfinal) pentru a se putea trasa traiectoria dorită. Dacă una din configurațiile menționate se află pe o prelungire a unei laturi a unui C-obstacol, atunci corespunzător configurației respective se va afla la intersecția prelungirii acestei laturi cu diagrama Voronoi deja trasată. Dacă această condiție nu este satisfăcută, atunci se construiește perpendiculara pe latura cea mai apropiată a C-obstacolului și care trece prin configurația respectivă; intersecția acestei perpendiculare cu diagrama Voronoi reprezintă poziția aplicației a configurației respective.
Figura 2.3. Exemplu de diagramă Voronoi pentru un spațiu de lucru bidimensional. Obstacolele sunt modelate prin poligoane. SCliber este o regiune poligonală mărginită
Deci, metoda de planificare a traiectoriilor bazată pe retractarea utilizează diagrama Voronoi ca hartă a drumurilor. Ea se desfășoară după cum urmează:
construiește diagrama Voronoi;
calculează punctele (Cinițial) și (Cfinal) și apoi identifică arcele din diagramă ce conțin aceste două puncte;
cercetează diagrama Voronoi pentru a găsi o secvență de arce A1, …, Ap, astfel încât (Cinițial)A1, (Cfinal) Ap și pentru i[1, p-1], arcele Ai și Ai+1 să aibă un capăt comun;
dacă există o secvență de arce între (Cinițial) și (Cfinal), atunci cercetarea se termină cu succes; în caz contrar, se declară "eșec".
2.4. Metoda drumului liber
2.4.1. Principiul metodei
Metoda drumului liber se aplică obiectelor poligonale care se mișcă (translație și rotație) într-un spațiu de lucru poligonal (bi-dimensional). Această metodă constă din extragerea unor figuri geometrice, denumite drumuri libere, din spațiul de lucru, conectarea lor într-un graf numit rețeaua drumurilor libere și cercetarea acestui graf [13], [37].
Un drum liber este un cilindru generalizat, bi-dimensional,liniar, drept, a cărui axă este completată cu descrierea tuturor orientărilor libere ale robotului A când originea sistemului de referință atașat OA se deplasează de-a lungul său.
Figura 2.4 ilustrează geometria unui drum liber, iar figura 2.5 indică patru drumuri libere într-un spațiu de lucru mărginit. Se menționează că, în cazul prezentat în figura 2.5 se mai pot construi încă alte drumuri libere, deci descompunerea nu este unică.
Robotul A se poate deplasa de-a lungul unui drum liber, sau de-a lungul unei porțiuni a acestuia, dacă există o mulțime conexă de orientări libere ale lui A când originea OA se deplasează de-a lungul axei cilindrului generalizat corespunzător. În plus, ori de câte ori se intersectează două axe, A se poate transfera de la un drum liber la altul dacă intervalele de orientări libere ale lui A (când OA se deplasează de-a lungul ambelor axe) au o intersecție nenulă în punctul de concurență a axelor. Rețeaua drumurilor libere este o reprezentare a mișcărilor posibile ale lui A de-a lungul axelor și între acestea.
Figura 2.4. Geometria unui drum liber. Un cilindru generalizat poate fi generat de o pereche de laturi E1, E2 ce corespund la două obstacole B1 și B2.
2.4.2. Generarea, extragerea și geometria drumurilor libere
Un drum liber este determinat de două laturi ale unor obstacole. Dacă W este spațiul de lucru al robotului și B este reuniunea tuturor obstacolelor sale, atunci drumurile libere sunt extrase din W \ B, considerând toate perechile de laturi ale lui B. O pereche de laturi (E1, E2) produce un cilindru generalizat dacă și numai dacă sunt satisfăcute următoarele condiții:
pentru i,j {1, 2}, ij, ambele extremități ale lui Ei se află în semiplanul exterior lui Ej;
produsul scalar al versorilor normalelor exterioare la E1 și E2 este negativ.
Figura 2.5. Descompunerea spațiului de lucru în drumuri libere. Descompunerea nu este unică, se mai pot construi încă alte drumuri libere
Pe baza celor menționate se poate construi cilindrul generalizat ce reprezintă drumul liber când este dată o pereche de laturi E1 și E2 (figura 2.6). Axa cilindrului este bisectoarea unghiului format de dreptele suport ale cele două laturi. Dacă E1 este paralelă cu E2, atunci axa este paralelă și echidistantă în raport cu ele. Fiecare latură a cilindrului este reprezentată de câte o latură de obstacol prelungită la fiecare extremitate (vârf) cu o semidreaptă paralelă cu axa. Alegerea bisectoarei ca axă a drumului liber este, într-un fel, o reconsiderare a diagramei Voronoi în spațiul respectiv de lucru. De fapt, axele cilindrilor generalizați conțin unele din segmentele de dreaptă care aparțin diagramei Voronoi.
Fiind date două laturi de obstacole E1 și E2 aflate față în față, se construiește cilindrul generalizat după cum s-a descris. Acesta se află parțial în exteriorul spațiului W \ B. Pentru planificarea traiectoriilor se iau în considerare doar porțiunile drumurilor libere conținute în W \ B. Astfel, se selectează în continuare porțiunile cilindrului care se află în întregime în interiorul spațiului menționat (figura 2.7). În acest scop, se intersectează cilindrul generalizat generat de laturile E1 și E2 ale obstacolelor B1 și B2 cu regiunea obstacolelor B. Intersecția este proiectată normal pe axă, iar sectoarele corespunzătoare care (W \ B) sunt înlăturate din cilindru (în figura 2.7 se înlătură S1, S2, S3 și S4). Va rămâne o mulțime finită de cilindri trunchiați ce conține numai cilindrii care includ porțiuni din laturile E1 și E2. În exemplul din figura 2.7 se va păstra numai sectorul notat cu .
După ce s-au considerat toate perechile de laturi ale lui B, cilindrii generalizați trunchiați rămași constituie drumurile libere utilizate la planificarea traiectoriilor.
Figura 2.6. Construirea unui cilindru generalizat.
Axa cilindrului este bisectoarea unghiului format de dreptele suport ale cele două laturi. Fiecare latură a cilindrului este reprezentată de câte o latură de obstacol prelungită la fiecare extremitate (vârf) cu o semidreaptă paralelă cu axa.
Figura 2.7. Selectarea porțiunilor de drumuri libere conținute în W \ B.
Sunt înlăturate din cilindru sectoarele S1, S2, S3 și S4. Se păstrează numai sectorul notat cu .
2.4.3. Rețeaua drumurilor libere
Respectând metodologia indicată se ajunge la o colecție de drumuri libere. Se utilizează acum această reprezentare pentru a construi graful neorientat G, care .reprezintă rețeaua drumurilor libere. G determină toate drumurile posibile când A se deplasează de-a lungul axelor.
Fie mulțimea punctelor P de intersecție a axelor drumurilor libere; fiecare punct P se află în interiorul ambelor drumuri libere care se intersectează. Deoarece fiecare interval este definit inițial față de orientarea unei axe, ambelor extremități ale intervalului li se adaugă un unghi potrivit, astfel încât toate intervalele să fie definite față de aceeași orientare de referință, spre exemplu axa Ox a sistemului de referință SW.
Pozițiile inițială și finală ale punctului OA sunt utilizate pentru a crea nodurile, inițial și final, ale lui G. Se presupune că aceste poziții se află pe axele unor drumuri libere F1, respectiv F2, la abscisele sinițial, respectiv sfinal. Nodurile corespunzătoare ale lui G sunt astfel asociate intervalelor (sinițial) și (sfinal) care conțin orientările, inițială și finală, ale robotului. Dacă aceste poziții nu sunt situate pe axele unor drumuri libere, atunci trebuie concepută o tehnică de deplasare a lui A, din poziția inițială pe o axă și de pe o altă axă în poziția finală.
O traiectorie liberă particulară se poate obține rotind A doar la intersecția între două axe (figura 2.8). Robotul translatează de-a lungul axelor și se rotește, dacă este necesar, numai la intersecția a două axe.
Un aspect neplăcut în utilizarea acestei metode apare atunci când spațiul de lucru este atât de dens populat cu obstacole, încât drumurile libere sunt prea scurte pentru a putea conține dreptunghiul circumscris lui A. Într-un astfel de caz, metoda trebuie să ia în considerare, fie construirea unor drumuri libere adiționale, fie trasarea unor axe care nu sunt bisectoarele dreptelor suport ale muchiilor obstacolelor.
Metoda drumului liber nu este completă și deci se poate întâmpla să nu se găsească întotdeauna o traiectorie liberă, chiar dacă există.
2.5. Metoda descompunerii celulare exacte
2.5.1. Principiul metodei
Principiul acestei metode de planificare a traiectoriilor constă în:
se descompune spațiul liber SCliber al robotului într-o colecție de regiuni numite celule, care nu se suprapun, și a căror reuniune este exact SCliber;
se construiește și se verifică graful de conexitate care reprezintă relațiile de adiacență între celule; în cazul reușitei, rezultatul verificării este o secvență de celule adiacente denumită canal, care conectează celula ce conține configurația inițială cu celula ce conține configurația finală;
se extrage traiectoria considerată favorabilă.
Nu toate descompunerile celulare ale spațiului liber sunt potrivite. Spre exemplu, o viziune extremă asupra acestei probleme, ar fi considerarea întregii mulțimi SCliber ca o singură celulă, dar extragerea unei traiectorii din această celulă ar conduce la problema inițială . Celulele generate de descompunere trebuie să aibă următoarele caracteristici:
geometria fiecărei celule trebuie să fie suficient de simplă , pentru a face posibilă calcularea unei traiectorii între oricare două configurații din celulă;
testarea adiacenței a două celule oarecare și găsirea unei traiectorii ce traversează porțiunea de frontieră corespunzătoare la două celule adiacente să nu se realizeze dificil.
Din cele precizate, rezultă că frontiera unei celule este o zonă critică, a cărei traversare impune anumite modificări. Celulele însă, sunt regiuni necritice, astfel încât toate traiectoriile
aflate în aceeași celulă, între oricare două configurații , sunt echivalente calitativ.
Există mai multe metode de planificare, bazate pe descompunerea celulară exactă, al căror avantaj comun este existența canalului ce conectează configurația inițială cu cea finală. Conceptul de canal este mai puțin restrictiv decât cel de traiectorie și poate asigura robotului informații utile pentru tratarea restricțiilor dinamice și a obstacolelor neașteptate în timpul execuției [13], [37].
2.5.2. Aplicarea metodei la spațiul configurațiilor poligonal
În cazul simplu, când SC = R2, regiunea SCB a C-obstacolelor este o regiune poligonală în spațiul configurațiilor. Pentru simplificare, se consideră că spațiul liber al robotului SCliber = SC \ SCB este mărginit, deși această presupunere nu este necesară efectiv. Mai târziu, această presupunere va fi retrasă.
O descompunere convex poligonală K a spațiului SCliber este o colecție finită de poligoane convexe, numite celule, astfel încât interioarele oricăror două celule nu se intersectează, iar reuniunea tuturor celulelor este egală cu SCliber (închiderea lui SCliber).
Două celule k și k' din K sunt adiacente dacă și numai dacă k k' este un segment de dreaptă de lungime diferită de zero. Graful de conexitate asociat unei descompuneri convex poligonale K a lui SCliber este graful neorientat G definit astfel:
nodurile lui G sunt celulele kj din descompunerea K a lui SCliber;
două noduri ale lui G sunt conectate printr-o legătură, dacă și numai dacă, celulele corespunzătoare din K sunt adiacente.
Figura 2.9 prezintă o descompunere convex poligonală a spațiului liber pentru un spațiu al configurațiilor bi-dimensional, în care sunt poziționate obstacole poligonale și sunt menționate pozițiile, inițială și finală, ale unui robot considerat punctiform. Figura prezintă și graful de conexitate asociat acestei descompuneri.
Algoritmul descompunerii celulare exacte pentru planificarea unei traiectorii libere ce conectează configurația inițială cu cea finală constă din:
se generează o descompunere convex poligonală K a lui SCliber, în care fiecare celulă este etichetată cu câte un număr întreg, diferit;
se construiește graful de conexitate G asociat lui K cu fiecare nod plasat în celula corespunzătoare;
se cercetează G, căutând o secvență de celule adiacente (un canal) între configurația inițială și cea finală;
dacă cercetarea se termină cu succes, se reține secvența respectivă de celule; în caz contrar, se declară "greșeală".
Figura 2.9 prezintă o descompunere convex poligonală a spațiului liber pentru un spațiu al configurațiilor bi-dimensional, în care sunt poziționate obstacole poligonale și sunt menționate pozițiile, inițială și finală, ale unui robot considerat punctiform. Figura prezintă și graful de conexitate asociat acestei descompuneri.
Rezultatul algoritmului este o secvență k1, …, kp de celule, astfel încât Cinițialk1, Cfinalkp, iar pentru orice j[1, p-1], kj și kj+1 sunt adiacente. Această secvență este denumită canal. În figura 2.9, spre exemplu, Cinițial este în celula 1, iar Cfinal în celula 6. Un canal posibil este secvența de celule: 1, 2, 3, 4, 5, 6. Interiorul unui canal trebuie să se afle în întregime în spațiul liber.
Un mod simplu de a genera o traiectorie liberă conținută în interiorul canalului rezultat din cercetarea lui G este de a considera punctul de mijloc Qj al fiecărui segment Lj și de a conecta Cinițial cu Cfinal printr-o linie poligonală, ale cărei vârfuri succesive sunt Q1, …, Qp-1 (figura 2.10). Dacă segmentul Qj-1Qj se află chiar în frontiera celulei kj, atunci în fiecare din respectivele celule va trebui introdus un punct suplimentar Qj'.
Figura 2.10.Generarea traiectoriei libere prin conectarea punctelor de mijloc Qj
2.5.3. Descompunerea trapezoidală
O descompunere convex poligonală particulară poate fi generată destul de eficient într-un alt mod (figura 2.11). Astfel, se generează o linie (L) paralelă , spre exemplu, cu axa Oy, care baleiază de-a lungul spațiului configurațiilor. Procesul de baleiere este întrerupt ori de câte ori linia (L) întâlnește câte un vârf X al lui SCB.
Rezultă întotdeauna maxim două segmente de dreaptă verticale ce leagă vârful X cu laturile lui SCB aflate imediat deasupra, respectiv imediat dedesubtul lui X. Frontiera lui SCB și segmentele de dreaptă verticale determină o descompunere trapezoidală a lui SCliber (numită și descompunere verticală). Fiecare celulă a descompunerii este fie un trapez, fie un triunghi. Două celule sunt adiacente dacă și numai dacă limita lor este un segment vertical. Când este traversat un astfel de segment, structura verticală a restricțiilor impuse de SCB mișcărilor lui A se modifică discontinuu.
Se observă că același algoritm se poate aplica și în cazul când SCliber nu este mărginit. În acest caz, descompunerea generată va include celule ce se extind la infinit pe direcția axei Oy. In timpul baleierii liniilor este posibilă crearea concomitentă a segmentelor de linii verticale emanate din vârfurile lui SCB, generarea grafului de conexitate G și identificarea celulelor ce conțin configurația inițială și finală.
În figura 2.11 este ilustrată metoda de planificare a traiectoriilor prin descompunere trapezoidală. Cercetarea lui G se poate realiza în diferite moduri, rezultând diferite căi posibile (spre exemplu, cea indicată cu linie îngroșată în figura 2.11.b) care, la rândul lor, determină canalul (zona hașurată din figura 2.11.c).
Ultima etapă este stabilirea efectivă a traiectoriei, spre exemplu, prin unirea mijloacelor segmentelor verticale întâlnite în canalul stabilit între punctele Cinițial și Cfinal.
Acestă metodă de planificare este frecvent utilizată pentru că realizează un optim între alegerea unei distanțe cât mai îndepărtate de obstacole și obținerea unei traiectorii cât mai scurte. Ea poate fi extinsă pentru cazul SC = R3, cu C-obstacole poliedrice. Se poate construi un algoritm de baleiere plană pentru realizarea descompunerii lui SCliber în celule paralelipipedice. Două celule sunt adiacente dacă și numai dacă două din fețele lor au în comun un trapez cu aria diferită de zero.
Figura prezintă: a) descompunerea trapezoidală;
b) graful de conexitate;
c) Canalul care conectează Cinițial și Cfinal; d)
drumul robotului
2.5.4. Curbe critice si regiuni necritice în plan
Se consideră cazul particular al unui robot A de forma unei bare, care se poate translata și roti într-un spațiu de lucru bi-dimensional W = R2. Robotul este modelat printr-un segment de dreaptă de lungime d, ale cărui capete sunt P și Q. W este populat cu obstacole a căror reuniune este regiunea poligonală B. Se presupune că B este o regiune mărginită.
Spațiul configurațiilor SC al lui A este R2 x S1, astfel încât fiecare configurație se parametrizează prin (x, y, ), unde x și y pot fi coordonatele lui P în sistemul fix SW, dacă se alege P = OA, ca origine a sistemului SA atașat robotului, iar unghiul [0,2) este format de axele Ox corespunzătoare ale celor două sisteme (în particular, se alege axa OAxA a sistemului atașat SA ca având direcția segmentului PQ). Perechea (x,y) a coordonatelor originii sistemului atașat este numită poziția lui A, iar unghiul este numit orientarea lui A.
Ideea de bază a planificării traiectoriilor, în acest caz, constă în descompunerea mulțimii de poziții ale lui A în regiuni bi-dimensionale necritice, transformarea acestor regiuni în celule tri-dimensionale și reprezentarea relației de adiacență între aceste celule într-un graf de conexitate. Celulele bi-dimensionale necritice sunt astfel alese, încât să mențină o structură omogenă în cilindrii de deasupra lor. Celulele conținute în astfel de cilindri explicitează această structură . Frontierele acestor regiuni necritice se numesc curbe critice.
Este astfel evident că regiunea C-obstacolelor SCB este o regiune tri-dimensională, mărginită de suprafețe care sunt porțiuni de C-suprafețe riglate de tip A sau B. O C-suprafață de tip A corespunde situației când segmentul PQ conține vârful unui obstacol. O C-suprafață de tip B corespunde situației în care, fie P, fie Q, este conținut în latura unui obstacol.
Se definește noțiunea de curba critica astfel:
proiecțiile pe planul xOy ale frontierelor suprafețelor regiunii SCB a C-obstacolelor;
proiecțiile pe planul xOy ale curbelor conținute în suprafețele lui SCB, unde planul tangent la SCB este perpendicular pe planul xOy.
Aceste curbe sunt mulțimea de puncte pentru care structura regiunii C-obstacolelor de deasupra planului xOy înregistrează schimbări calitative. Într-adevăr, când este traversată o astfel de curbă, fie se modifică mulțimea suprafețelor lui SCB care sunt intersectate de o linie perpendiculară pe planul xOy în poziția curentă, fie se modifică numărul punctelor de intersecție.
Curbele critice se clasifică în șase tipuri, după cum urmează (figura 2.12):
laturile E ale obstacolelor sunt curbe critice de tip 0;
segmentul de dreaptă situat la distanța d de latura E, având aceeași lungime cu E, este o curbă critică de tip 1 (figura 2.12.a);
arcul de cerc de rază d, cu centrul în vârful X al unui obstacol și mărginit de cele două semidrepte care conțin laturile ce se intersectează în X, este o curbă critică de tip 2 (figura 2.12.b și c);
dacă E este latura unui obstacol și X un vârf convex la unul din capetele lui E, segmentul de dreaptă trasat de capătul P când A glisează de-a lungul lui E până când Q rămâne încă în E (PQ este conținut în linia care conține latura E), este o curbă critică de tip 3 (figura 2.12.d);
fie X1 și X2 două vârfuri ale unui obstacol convex, astfel încât linia ce trece prin cele două vârfuri este tangentă la obstacol (regiunea SCB) în vârfurile respective; segmentul de dreaptă trasat de capătul P când A translatează atingând simultan X1 și X2 este o curbă critică de tip 4 (figura 2.12.e);
fie E latura unui obstacol și X vârful unui obstacol convex B, care nu este punct de capăt pentru E, situat la distanța h de E; dacă h < d, curba trasată de P când robotul se deplasează astfel încât atinge simultan E și X, fiind tangent la B în X, este o curbă critică de tip 5 (figura 2.12.f).
Figura 2.12. Clasificarea curbelor critice
Orice zonă deschisă, mărginită de curbe critice este o regiune necritică.
Pentru cazul particular al unui spațiu de lucru poligonal (figura 2.13) există 21 de curbe critice posibile, în afară de laturile obstacolelor. Astfel:
L1,…,L6 sunt curbe de tipul 1, generate de muchiile E1,…,E6;
L7,…,L10 sunt curbe de tipul 2, generate de vârfurile X1,…,X4;
L11,…,L16 sunt curbe de tipul 3, generate de E2 și X1, E1 și X1, E3 și X2, E2 și X2, E6 și X4, E5 și X4;
L17 și L18 sunt curbe de tipul 4, generate de vârfurile X2 și X4;
L19,…,L21 sunt curbe de tipul 5; L19 este generată de E4 și X4, L20 de E6 și X2, iar L21 de E2 și X4.
O porțiune (secțiune) de curbă critică este o submulțime maximală, închisă și conexă a curbei, care este intersectată de orice altă curbă critică doar la cele două capete.
O poziție (x, y) a lui A este admisibilă dacă există cel puțin o orientare , astfel încât (x,y,)SCliber.
O regiune necritică este o submulțime maximală de poziții admisibile ale lui A care nu intersectează nici-o curbă critică. Astfel, mulțimea finită de curbe critice determină o
colecție de regiuni necritice. Fiecare regiune necritică este o submulțime deschisă a planului xOy. De exemplu, în figura 2.13, R indică o regiune necritică, mărginită de porțiunile curbelor critice L4, L7, L2, L5 și L10.
Frontiera oricărei regiuni necritice este o reuniune finită de porțiuni de curbe critice. O poziție admisibilă (x, y) a lui A este necritică dacă și numai dacă se află într-o regiune necritică; în caz contrar, este critică.
Figura 2.13. Exemplu de determinare a curbelor critice pentru un spațiu de lucru poligonal
2.6. Descompunerea celulară aproximativă
Descompunerea celulară aproximativă constă din reprezentarea spațiului liber al robotului SCliber, sub forma unei colecții de celule, dar se deosebește de descompunerea celulară exactă prin faptul că celulele din acest caz au nevoie de o formă simplă specificată dinainte, de exemplu o formă rectangulară. Aceste celule nu permit, în general, reprezentarea cu exactitate a spațiului liber, dar permit o aproximare largă a acestui spațiu, de unde rezultă și numele acestei metode. Ca și în cazul descompunerii celulare exacte, se construiește un grafic de conexitate ce reprezintă relația de adiacență dintre celule [37].
Condițiile necesare pentru standardizarea formei celulelor sunt:
obținerea descompunerii spațiului prin repetarea acelorași calcule simple;
să fie insensibile la calcule numerice aproximative.
Prin metoda descompunerii celulare aproximative se poate controla direct spațiul liber din jurul unei traiectorii generate prin stabilirea unei dimensiuni minime a celulelor. Aceasta poate fi un important avantaj când erorile modelelor geometrice și/sau ale controlului robotului sunt semnificative.
Pe de altă parte, suprafețele elementelor generate prin metoda descompunerii aproximative sunt oarecum arbitrare. Acestea nu mai caracterizează discontinuitățile mișcărilor constrânse, ca în cazul descompunerii celulare exacte. Mai mult, când reprezintă pe larg spațiul liber al robotului, aceste metode pot eșua în găsirea unui drum liber, chiar dacă acesta există. Pe baza unor simple presupuneri ar putea fi rezolvat acest neajuns (metodele pot fi aplicate în întregime, dar se consumă un timp prea mare).
Majoritatea metodelor de descompunere celulară aproximativă permit ca mărimea celulelor să fie adaptată la geometria regiunii C-obstacol. De fapt, prestabilirea mărimii celulelor poate duce la dificultăți: o celulă mare ar preveni găsirea dimensiunilor libere în prea multe cazuri, pe când o celulă de dimensiuni mici pretinde mai multe calcule. De aceea, majoritatea metodelor operează în ordine ierarhică, generând o descompunere inițială și continuând apoi această descompunere la nivel local, până când este găsit un drum liber sau descompunerea nu mai este posibilă.
Principiul descompunerii celulare aproximative este general și poate fi aplicat (teoretic) în problema de bază a planificării mișcării. Oricum, în practică complexitatea temporală și spațială a metodelor bazate pe această aproximație crește rapid, în funcție de dimensiunea m a spațiului configurațiilor. Aceste metode sunt într-adevăr aplicabile numai atunci când această dimensiune este suficient de mică. În aceste cazuri, de exemplu când robotul este un poligon care execută mișcări de translație și rotație în mod liber printre obstacolele poligonale dintr-un spațiu de lucru bidimensional, sunt comparate adesea cu alte aproximări.
Metoda descompunerii celulare aproximative a fost introdusă pentru prima oară de Lozano-Perez și Brooks și a fost dezvoltată apoi de alți cercetători: Laugier și Germain, Faverjon, Kambhampati și Davis, Zhu și Latombe [37].
2.6.1. Prezentarea generală a metodei
Un corp dreptunghiular reprezintă o regiune închisă în spațiul cartezian Rn.
Diferențele , i=1, …, n, se numesc dimensiuni ale corpului dreptunghiular. Nici una din aceste dimensiuni nu este egală cu zero.
Se presupune că A este un robot al cărui spațiu al configurațiilor este SC în RN, sau cu N=2 sau 3. Dacă, o configurație C este reprezentată de coordonatele punctului de referință OA în raport cu sistemul fix Sw atașat spațiului de lucru. Dacă, o configurație C este reprezentată ca, unde este unghiul dintre axele x ale lui Sw și SA. Dacă, configurația este reprezentată astfel: , unde , și sunt unghiurile lui Euler. Fără să se renunțe la generalizarea problemei, se presupune că setul de poziții posibile ale lui A este conținut în dreptunghiul. SCliber este reprezentat sub forma , unde SCB este regiunea C-obstacolelor:
, dacă ,
, dacă, ;
, dacă .
Fie. este un rectangloid al lui, unde m este dimensiunea spațiului configurațiilor SC. O descompunere dreptunghiulară P a lui este o colecție finită a rectangloizilor {ki }i=1,…,r, astfel încât:
este egal cu mulțimea de reuniuni ki: ;
suprafețele interioare ale lui ki nu se intersectează:
fiecare rectangloid ki este denumit descompunere celulară P a lui .
Două celule sunt adiacente dacă și numai dacă intersecția lor este un ansamblu de măsuri diferite de zero în . Intersecția lor se calculează luând în considerare următoarele:
, este identificat cu
dacăsunt identificate cu .
O celulă ki este clasificată ca fiind:
GOALĂ, dacă și numai dacă interiorul său nu intersectează regiunea C-obstacol, ex: ;
PLINĂ, dacă și numai dacă ki este inclus în întregime în regiunea C-obstacol, ex: kI SCB ;
MIXTĂ – în alte condiții.
Graful de conexitate asociat cu descompunerea P a lui este graful G definit astfel:
nodurile lui G sunt celule GOALE și MIXTE ale lui P.
două noduri ale lui G sunt unite printr-o legătură dacă și numai dacă celulele corespunzătoare sunt adiacente.
Dându-se o descompunere rectangulară P a lui , canalul este definit ca fiind o serie de celule GOALE și/sau MIXTE, astfel încât oricare două celule consecutive kj și kj+1, j [1,p-1] sunt adiacente. Un canal care conține cel puțin o celulă mixtă se numește canal M. Dacă (k j) j=1,…, p este un canal, atunci orice direcție conectează orice configurație în kj cu orice configurație din kp și este un drum liber.
Dacă (k j) j=1, …, p este un canal M, atunci poate exista un drum liber între două configurații în kj și kp, și staționarea în , dar nu există garanții. Dându-se o configurație inițială și o configurație planificată, problema constă în generarea unui canal, astfel încât și . Dacă este generat un astfel de canal, se presupune că este intersecția limitelor celor două celule succesive. Un drum liber care unește configurația inițială cu cea planificată ar putea fi extras din canalul E, unind Cinițial și Cfinal printr-o linie poligonală ale cărei vârfuri sunt punctele . Pentru fiecare j, j, și j-1 aparțin aceleiași suprafețe ale lui kj,deci, un punct suplimentar localizat în interiorul lui kj trebuie inclus printre vârfurile drumului când segmentul de dreaptă Qj-1Qj nu garantează că va cuprinde întreg spațiul liber. Dacă este necesar, drumul poligonal poate fi netezit prin ajustare.
Planificarea ierarhică a drumului constă în generarea unui canal E prin construirea unor descompuneri rectangloide succesive ale lui și căutarea grafurilor de conectivitate (presupunem că este o celulă MIXTĂ). Fie Pi ,cu i =1,2,…., denotând descompunerile succesive ale lui . Fiecare descompunere Pi se obține din cea anterioară, Pi-1 (cu PO ={ }), prin descompunerea uneia sau a mai multor celule MIXTE, celelalte celule rămânând neschimbate. Ori de câte ori o descompunere Pi este calculată, graful de conectivitate asociat, definit de Gi , este căutat printr-un canal care unește pe Cinitial cu Cfinal
Un algoritm simplu de reprezentare este următorul:
calculează o descompunere rectangloidă P1 a lui Q, de la i la 1.
caută graful de conectivitate Gi asociat cu descompunerea Pi pentru un canal ce conectează celula inițială care-l conține pe Cinitial, cu celula planificată care-l conține pe Cfinal. Dacă rezultatul este un canal de tip E, se declară reușit. Dacă rezultatul este un canal de tip M, se trece la următorul pas. În alt caz, se declară eșec.
fie Hi canalul M generat în etapa 2. Se fixează Pi+1 la Pi. Pentru fiecare celulă MIXTĂ k din Hi se calculează o descompunere rectangloidă Pk a lui k și se fixează Pi+1 la . Fixează i la i+1. Se trece la etapa 2.
2.6.2. Metoda divide- and -label. Descompunerea prin metoda arborelui
Metoda este numită divide – and – label (împarte pe secțiuni și denumește). Ea constă într-o primă divizare a celulei în celule mai mici, urmând apoi alipirea fiecărei celule nou create – conform intersectării sale cu regiunea C-obstacolelor.
Există mai multe metode de a descompune un rectangloid în rectangloizi mai mici. Probabil că cea mai utilizată metodă este descompunerea , unde m reprezintă dimensiunea spațiului configurațiilor. O descompunere a lui este un arbore de gradul 2 (fiecare nod ce nu reprezintă nici o frunză are exact succesori). Fiecare nod al arborelui este o celulă rectangloidă, etichetată ca fiind GOALĂ, PLINĂ sau MIXTĂ. Rădăcina arborelui este . Doar acele noduri care au celule MIXTE pot avea descendenți și în acest caz, fiecare are. Toți descendenții unei celule k au aceleași dimensiuni și sunt obținuți prin descompunerea fiecărei muchii ale celulei k în două segmente de lungimi egale.
Dacă m=2, arborele se numește arbore cuadratic (binar). Dacă m=3, arborele se numește arbore octogonal.
Noțiunea de arbore a fost pentru prima dată utilizată în ''Solid Modeling, Cossmputer Graphics and Computer Vision" [37]: Jackins și Tanimoto (1980), Samet (1980), Meagher (1982) și Ayala (1985). Utilizarea sa în evitarea coliziunii și în planificarea mișcării este mai recentă și a apărut în câteva lucrări care includ pe cele ale lui: Ahuja (1980), Faverjon (1984), Boaz și Roach (1985), Hayward (1986), Herman (1986), Kambhampati și Davis (1986), Fujimura și Samet (1989).
Figura 2.14 prezintă o descompunere a unui spațiu bidimensional și afișează o porțiune din arborele cuadratic.
Adâncimea (numărul de arce care unesc rădăcina cu punctul) într-un arbore reprezentând , determină dimensiunile celulei corespunzătoare. Înălțimea h a arborelui determină rezoluția descompunerii lui , de aici rezultând mărimea celei mai mici celule. Pentru a pune în aplicație algoritmul prezentat, trebuie să se specifice înălțimea h a descompunerii P1 generată în etapa 1. Toate celulele MIXTE ale căror adâncimi sunt mai mici decât h1, sunt descompuse aici. Mai târziu, doar acele celule MIXTE care sunt localizate într-un canal M, vor fi descompuse mai departe. De obicei ,o înălțime maximă a arborelui – hmax , este specificată pentru a limita procesul iterativ precizat la etapele 2 și 3. Fiecare celulă MIXTĂ a cărei adâncime este egală cu hmax reetichetată ca fiind PLINĂ, rezultă un arbore trunchiat.
2.7. Metoda câmpului potențial
Această metodă de planificare tratează robotul, reprezentat ca un punct în spațiul configurațiilor, ca pe o particulă aflată sub influența unui câmp potențial artificial U, ale cărui variații locale reflectă "structura" spațiului liber. Funcția potențial este definită pe spațiul liber ca suma dintre un potențial atractiv, ce atrage robotul spre configurația finală, și un potențial repulsiv, ce îndepărtează robotul de obstacole.
Planificarea mișcării este făcută în mod iterativ. La fiecare iterație, forța artificială:
indusă de funcția potențial în configurația curentă este considerată ca direcția cea mai promițătoare a mișcării și generarea traiectoriei înaintează de-a lungul acestei direcții.
Metoda a fost dezvoltată inițial ca o metodă "on line" de evitare a coliziunilor, aplicabilă când robotul nu are un model aprioric al obstacolelor, dar le poate sesiza în timpul execuției mișcării.
În particular, procedura se poate bloca într-un minim local al funcției potențial, altul decât configurația finală, deoarece acționează ca o procedură rapidă.
Ideea câmpului potențial a putut fi asociată cu tehnici de cercetare a grafurilor, apoi, utilizând un model aprioric al spațiului de lucru, a putut fi transformată într-o metodă de planificare frecvent utilizată.
Chiar și în cazul utilizării tehnicilor de cercetare a grafurilor, minimele locale rămân o cauză importantă a unor deficiențe ale metodelor de câmp potențial.
Tratarea minimurilor locale este o problemă majoră ce trebuie rezolvată în proiectarea unui planificator bazat pe această metodă. Problema se poate aborda la două niveluri:
în definirea funcției potențial, prin încercarea de a introduce funcții fără minime locale sau cu puține minime locale;
în proiectarea algoritmului de cercetare, prin includerea de tehnici potrivite pentru a ieși din minimele locale sau pentru a le evita.
Metodele de câmp potențial sunt numite adesea metode locale. Aceasta se datorează faptului că cele mai multe funcții potențial nu rămân valabile dincolo de o vecinătate limitată, într-un spațiu al configurațiilor bine definit. Funcția potențial ideală ar fi în această situație cea cu un singur minim în configurația finală.
Caracterul metodelor de câmp potențial este profund empiric, putând conduce la greșeli în găsirea unei traiectorii libere, chiar dacă există una. Marele avantaj al acestei metode constă în rapiditatea deosebită într-o gamă largă de situații.
2.7.1. Câmpul potențial in translație
Se consideră că robotul A translatează liber în spațiul său de lucru RN. Câmpul de forțe artificiale în SC este produs de o funcție potențial diferențiabilă U : SCliber R, fiind valabilă definiția:
În spațiul configurațiilor SC = RN (N = 2 sau 3), cu orientarea fixată, fiecare configurație este C = (x, y), respectiv C = (x, y, z), astfel ca:
sau
Pentru ca robotul să fie atras de configurația finală și respins de obstacole, funcția U este considerată ca o sumă a două funcții:
U(C) = Ua(C) + Ur(C)
unde:
Ua este potențialul atractiv asociat cu configurația finală Cfinal;
Ur este potențialul repulsiv asociat cu regiunea C-obstacolelor.
Potențialul Ua este independent de regiunea C-obstacolelor, iar potențialul Ur este independent de configurația finală.
Cu aceste convenții, forța este suma a doi vectori: forța atractivă și forța repulsivă :
Funcția potențial atractiv Ua poate fi definită:
unde:
este un factor constant pozitiv;
dfinal = este distanța euclidiană între configurația curentă C și configurația finală Cfinal a robotului; funcția dfinal este diferențiabilă oriunde în spațiul configurațiilor.
Funcția Ua este pozitivă sau nulă și are minim în Cfinal unde U(Cfinal) = 0.
În orice configurație C, forța de atracție ce derivă din potențialul atractiv este:
Când este utilizat pentru evitarea coliziunilor "on line", potențialul parabolic Ua are un efect stabilizator bun, deoarece generează o forță care converge liniar spre zero, când configurația robotului se apropie de configurația finală. Stabilitatea robotului poate fi crescută prin adăugarea unor forțe disipative proporționale cu viteza . În acest caz, forța atractivă converge asimptotic.
Așa cum este definit, potențialul atractiv parabolic generează o forță, care crește cu distanța la configurația finală și tinde la infinit când dfinal(C) tinde la infinit.
Ua poate fi definit și prin:
Ua(C) = dfinal(C)
când forța atractivă devine:
În acest caz, amplitudinea forței de atracție este constantă în spațiul configurațiilor, cu excepția configurației finale Cfinal, unde potențialul de atracție este singular. Deoarece amplitudinea forței nu tinde la zero când C Cfinal, potențialul conic definit în acest mod nu are caracteristicile stabilizatoare ale celui definit anterior.
Un mod de a combina avantajele celor două definiții ale funcției potențial este de a utiliza prima definiție a potențialului atractiv până la o anumită distanță de configurația finală și a doua definiție dincolo de această distanță , cu o derivată definită la joncțiunea lor.
Trebuie menționat faptul că, în general, este utilizată prima definiție.
În ceea ce privește definirea potențialului repulsiv, ideea principală este de a crea o barieră de potențial în jurul regiunii C-obstacolelor, care nu poate fi traversată de configurația robotului. În plus, este de dorit ca potențialul repulsiv să nu afecteze mișcarea robotului când acesta este suficient de departe de C-obstacole. Un mod de a obține aceste restricții este de a defini funcția potențial repulsiv după cum urmează:
în care:
este un factor constant pozitiv;
d(C) reprezintă distanța de la configurația C la regiunea C-obstacolelor, adică:
d0 este o constantă pozitivă numită distanță de influență a C-obstacolelor.
Funcția Ur este pozitivă sau nulă; ea tinde la infinit când C se apropie de regiunea C-obstacolelor și este nulă când distanța de la configurația robotului la regiunea C-obstacolelor este mai mare ca d0.
Dacă SCB este o regiune convexă, cu o frontieră diferențiabilă pe porțiuni, d este diferențiabilă peste tot în spațiul SCliber.
Forța repulsivă care derivă din acest potențial este:
Fie Cc configurația unică în SCB cea mai apropiată de C, adică:
Gradientul este un vector care are ca suport dreapta ce trece prin Cc și C și care este orientat de la SCB spre exterior.
Dacă se renunță la presupunerea, de altfel nerealistă, că SCB este convex, d(C) rămâne diferențiabilă peste tot în SCliber, cu excepția acelor configurații C, pentru care există mai multe CcSCB care verifică condiția de configurație unică . Aceste configurații formează o mulțime de dimensiune zero în SC, care este, în general, (N-1)-dimensională local. Câmpul de forțe este definit pe ambele părți ale acestei mulțimi, dar cu valori diferite ale vectorilor orientați. Aceasta poate duce la traiectorii ce oscilează între cele două părți ale mulțimii.
Un mod de a elimina această dificultate este de a descompune SCB în componente convexe SCBk (k=1,…,r), care pot să se și suprapună, și de a asocia un potențial repulsiv USCBk fiecărei componente. Atunci, potențialul repulsiv este suma potențialelor create de fiecare C-obstacol:
în care:
unde dk(C) indică distanța de la C la SCBk.
Forța repulsivă care derivă din acest Ur va fi suma vectorială:
În spațiul configurațiilor SCB, SCBk pot fi construite descompunând A și obstacolele spațiului de lucru în componente convexe și apoi calculând C-obstacolele corespunzătoare fiecărei perechi ce constă dintr-o componentă a lui A și o componentă a unui obstacol.
Dezavantajul descompunerii regiunii C-obstacolelor este acela că mai multe componente mici, apropiate una de alta, produc în mod arbitrar o forță repulsivă combinată, mai mare decât cea produsă de o singură componentă mai mare. Un mod empiric de a trata acest dezavantaj este de a aprecia fiecare potențial individual printr-un coeficient care depinde de "importanța" componentei C-obstacolului care îl generează.
În definiția dată pentru Ur(C) se utilizează un factor unic și o distanță de influență d0 (de asemenea, unică). În particular, dacă configurația finală este apropiată de SCB, distanța de influență d0 ar trebui stabilită mai mică decât distanța de la Cfinal la SCB pentru submulțimea lui SCB situată în apropierea lui Cfinal, astfel încât robotul să nu fie împiedicat de câmpul potențial repulsiv să atingă configurația finală. Dacă potențialul repulsiv nu este nul în Cfinal, atunci în general, minimul global al funcției potențial totale nu este Cfinal. Distanța d0 poate fi stabilită la o valoare mai mare pentru restul lui SCB. În plus, dacă un anumit spațiu de lucru pare mai "primejdios" ca celelalte, este indicat să se folosească valori mai mari ale mărimilor și d0 pentru C-obstacolele corespunzătoare.
Potențialul repulsiv USCB(C) și câmpul de forțe asociat pot fi calculate ușor când regiunea C-obstacolelor este o regiune poligonală, poliedrică sau sferică. Totuși, în cazuri generale, nu există un algoritm direct de calcul. Când regiunea C-obstacolelor poate fi descompusă în componente convexe SCBk, fiecare descrisă ca o conjuncție de inegalități fjk0, j=1, 2, …, problema calculului lui dk(C) este o problemă de optimizare ce poate fi rezolvată prin tehnici numerice iterative.
2.7.2. Câmpul potențial în cazul general
O generalizare a evoluției robotului, când spațiul configurațiilor este SC = RN x SO(N), impune redefinirea funcțiilor potențial pentru acest caz.
Pentru introducerea funcției potențial atractiv se consideră N puncte aj (j = 1,…,N) selectate în robotul A, aflat într-un spațiu de lucru N-dimensional. Dacă N = 3, cele trei puncte ar trebui să fie necoliniare pentru a determina în mod unic configurația lui A.. Punctele aj sunt numite puncte de control supuse câmpului potențial atractiv.
Pentru fiecare punct aj se definește o funcție potențial atractiv distinctă Vaj : WR, cu relația:
unde este un factor pozitiv.
Fiecare potențial induce în spațiul de lucru un câmp de forțe . La acest câmp sunt sensibile doar punctele de control aj.
Astfel, în fiecare configurație C a lui A, forța de atracție , definită prin :
este exercitată asupra lui A în punctul aj.
Forța atractivă totală, situată în spațiul tangent al spațiului de lucru, are expresia:
Dacă :
Uaj(C) = Vaj(aj(C)),
atunci:
reprezintă potențialul atractiv în SC care produce forța atractivă :
Dacă numărul de puncte aj este mai mic decât N, specificarea poziției finale a acestor puncte determină numai parțial configurația finală a lui A, adică configurația finală formează o regiune a lui SC.
Dacă mai mult de un punct de control aj este supus câmpului potențial atractiv, definiția de mai sus a potențialului Ua face ca punctele de control să concureze în încercarea de a-și obține poziția finală. Această competiție poate produce minime locale ale potențialului total în pasaje înguste ale spațiului de lucru; de aceea o definiție mai bună ar putea fi:
unde este o constantă pozitivă mică ( = 0,1).
Aceasta corespunde alegerii unui "conducător" a1(C) printre punctele de control. De-a lungul traiectoriei generate, punctul conducător este puternic atras de poziția sa finală, în timp ce coeficientul mic m face ca orientarea lui A să fie în principal sub influența potențialului repulsiv. Al doilea termen al potențialului atractiv tinde să ducă robotul la obținerea configurației finale. Expresia de mai sus a potențialului atractiv dă rezultate bune când configurația finală este destul de departe de regiunea C-obstacolelor; în caz contrar, ea poate conduce la minime locale adânci, în apropierea configurației finale, ceea ce poate împiedica robotul să ajungă în poziția finală.
În mod similar se poate defini și calcula potențialul repulsiv. Pentru orice X W \ B, B fiind regiunea obstacolelor în spațiul de lucru W, se definește câmpul potențial repulsiv care acționează asupra a Q puncte aj (j = 1, …, Q) selectate din frontiera lui A, numite puncte de control supuse câmpului potențial repulsiv. Cele N puncte utilizate în definirea potențialului atractiv nu trebuie să fie printre acestea, deși ar putea să fie.
Astfel, funcția potențial repulsiv este definită într-un punct oarecare X, sub forma:
în care :
este un factor pozitiv;
d(X) este distanța euclidiană de la punctul X la B;
d0 este distanța de influență a lui B.
Când A este în configurația C, potențialul Vr exercită o forța asupra lui A, în punctul aj:
Dacă B este o regiune convexă cu frontiera diferențiabilă pe porțiuni, d este diferențiabilă oriunde în SCliber. Dacă B nu este convexă, ea se poate descompune în componente convexe și fiecărei componente i se poate asocia un potențial repulsiv.
Acestei forțe i se poate atașa un vector în planul tangent, astfel încât forța repulsivă rezultantă este:
Dacă:
Urj(C) = Vr(aj(C))
atunci potențialul repulsiv
produce forța repulsivă:
Pentru a exista siguranța că A nu se poate apropia de B fără să fie respins, se poate combina un anumit număr de puncte de control "fixe", cu un punct de control "variabil" ce depinde de configurația lui A. Punctul de control variabil este punctul a' din frontiera lui A care este cel mai apropiat de B în configurația curentă C a lui A.
Deci:
Pentru unele configurații critice ale lui A, în care o muchie (sau o față) a lui A este paralelă cu o muchie (sau o față) a lui B, distanța minimă se obține pentru mai mult de o pereche de puncte. În aceste configurații, punctul de control variabil a' se poate modifica discontinuu în frontiera lui A rezultând o discontinuitate a forței repulsive . Aceasta poate cauza generarea unei traiectorii oscilante. Un mod de a reduce discontinuitatea forței repulsive în aceste configurații este de a distribui forța repulsivă asupra mai multor puncte ale lui A(C), printre cele care sunt cele mai apropiate de B.
Dacă A și B sunt poligoane neconvexe, ele pot fi descompuse în două mulțimi de poligoane convexe {Ak} și {Bl}. Pentru fiecare pereche (Ak, Bl) se poate defini un punct de control variabil a'kl, ca fiind punctul din frontiera lui Ak cel mai apropiat de Bl.
Toate aceste puncte sunt luate simultan ca puncte de control variabile supuse câmpului potențial repulsiv. Dacă unul dintre Ak sau Bl este strict convex, celălalt fiind convex, și dacă ambele au frontiere diferențiabile pe porțiuni, atunci este unic definit și forța repulsivă exercitată în este continuu variabilă.
În ceea ce privește tehnicile de planificare a traiectoriilor, în acest caz, ele presupun o anumită funcție de potențial specifică .
În concepția sa originală, metoda câmpului potențial pentru generarea mișcării constă în a considera robotul în spațiul configurațiilor ca o particulă de masă unitară, mișcându-se sub influența unui câmp de forțe . În fiecare configurație C, forța generată determină accelerația particulei, astfel încât, prin aplicarea legilor dinamicii se pot calcula, în fiecare moment, forțele generalizate ce trebuie dezvoltate de elementele motoare pentru a asigura mișcarea propusă.
Acest mod de utilizare a funcției potențial este aplicabil pentru generarea traiectoriilor când obstacolele nu se cunosc dinainte, ci sunt sesizate în timpul execuției mișcării. Dacă este disponibil un model aprioric al obstacolelor, aceeași metodă poate fi utilizată pentru planificarea traiectoriilor prin simularea mișcării particulei.
C A P I T O L U L 3
METODE DE PLANIFICARE A MIȘCĂRII ROBOȚILOR MOBILI ÎNTR-UN SPAȚIU CU OBSTACOLE ȘI ROBOȚI ARTICULAȚI
În acest capitol se vor studia diversele extensii ale problemei de bază a planificării mișcării.
La început se consideră cazul în care câteva obstacole incluse în spațiul de lucru sunt în mișcare. Problema rezultată este numită Problema planificării dinamice a mișcării. Spre deosebire de problema de bază, statică, aceasta nu poate fi rezolvată întotdeauna prin construirea unui drum geometric. Astfel, este necesar să se genereze o funcție de timp, continuă care să specifice configurația robotului în fiecare moment al mișcării. Abordarea generală a problemei constă în adăugarea unei noi dimensiuni, timpul, la spațiul configurațiilor robotului. Astfel, în acest spațiu temporal al configurațiilor, robotul poate fi considerat ca un punct material în mișcare printre obstacolele staționare. Dintre metodele de planificare a mișcării roboților stabilite în cadrul problemei de bază a planificării, unele sunt aplicabile și în cadrul problemei dinamice a planificării, dar cu anumite modificări și extensii.
Problema planificării dinamice a mișcării poate fi abordată impunând restricții asupra vitezei și accelerației robotului. Se pot considera două cazuri mai simple: când modulul vitezei robotului nu este limitat superior și când modulul vitezei robotului este limitat (fără alte constrângeri asupra vitezei și accelerației). Problema cu limitarea vitezei robotului este mai complicată decât problema fără limitare de viteză.
O a doua extensie, consideră Problema planificării drumului roboților multipli, unde mai mulți roboti se mișcă independent în același spațiu de lucru, printre obstacole staționare. O abordare simplă conceptual a acestei probleme este de a considera diferiții roboți ca și componente ale unui robot compus și de a planifica un drum liber în spațiul configurațiilor acestui robot (planificare centralizată). Dificultatea acestei abordări constă în dimensiunea mare a spațiului configurațiilor, complexitatea temporală a planificării variind exponențial cu această dimensiune. Altă abordare constă în planificarea unui drum pentru fiecare robot, mai mult sau mai puțin independent față de ceilalți roboți, și considerând interacțiunile dintre drumuri (planificare decuplată). Această abordare reduce din calcul, dar se pierde din completitudinea algoritmului.
A treia extensie consideră roboții articulați, construiți din elemente rigide, mobile, conectate prin cuple cinematice care limitează mișcările relative ale obiectelor.
3.1. Obstacole mobile
3.1.1. Spațiul temporal al configurațiilor
Fie A un obiect rigid care se mișcă într-un spațiu de lucru W=RN, unde N=2 sau 3, populat cu obstacole Bi (obiecte rigide), i=1, …, q, care pot fi în mișcare. Obstacolul Bi(t) determină regiunea din W ocupată de obiectul Bi la momentul t (t>0). Se presupune că regiunile B1(t) până la Bq(t) sunt a priori cunoscute. Această presupunere cere ca mișcările obstacolelor să nu fie influențate de mișcarea lui A.
Fie SC spațiul configurațiilor lui A. La fiecare moment t, obstacolului Bi(t) îi corespunde C-obstacolul SCBi(t):
SCBi(t) = {C SC / A(C) Bi (t) 0 ).
Forma lui SCBi(t) nu depinde de t, dar poziția lui în SC depinde.
Problema planificării dinamice a mișcării este problema planificării unei mișcări fără coliziuni a lui A, din configurația inițială Cinițial, la momentul inițial, până la configurația destinație Cfinal la un moment T 0. Timpul T se numește timp de sosire. Problema planificării presupune generarea unei funcții de timp care să specifice configurația lui A în fiecare moment din intervalul [0, T]. O soluție a acestei probleme este o funcție continuă:
t [0,T] C (t) SC \ SCBi(t) unde t reprezintă timpul, C(0) = Cinițial și C(T) = Cfinal. Această funcție este numită traiectoria lui A.
Deoarece poziția C-obstacolelor se modifică în timp, acestea nu pot fi reprezentate în SC astfel încât să se poată reduce mișcarea lui A la mișcarea unui punct printre obiecte fixe. Problema este rezolvată adăugând încă o dimensiune numită timp la SC. Rezultă astfel un nou spațiu SCT = SC x [0, +], numit spațiul temporal al configurațiilor lui A. SCT este o suprafață topologică de dimensiune m+1, unde m este dimensiunea lui SC. O aplicație continuă : [0, 1] SCT se cheamă SCT-drum.
Robotului A îi corespunde în SCT o configurație temporală (C, t). Secțiunea transversală prin SCT la fiecare moment t este SC populată de obstacole SCBi(t), i=1, …, q. Astfel, fiecărui obstacol Bi îi corespunde în SCT o regiune staționară SCTBi, numită CT-obstacol, definită de următoarea ecuație: SCTBi = {(C, t) / A(C ) Bi(t) 0}.
Figura 3.1. Robotul A translatează liber, fără rotație în plan (a). Obstacolul B translatează cu orientare fixă, cu o viteză liniară constantă între momentele t1 și t2. Viteza este paralelă cu axa y și se îndreaptă în sus. La orice moment de timp t [t1, t2], B este în repaus. SCT–obstacolul SCTB este obținut prin baleierea SCB de-a lungul liniei perpendiculare pe planul xy, unde t [t1, t2] (b), și orientată de-a lungul vectorului (0, ,1) unde t [t1,t2].
Exemplul prezentat în figura 3.1 ilustrează construcția lui SCTB, unde W=R2, SC=R2 și SCT=R2x[0, +). Fie SCB(0) un C–obstacol în SC la momentul t=0. Pentru toate momentele t [t1, t2], SCB(t) rezultă prin translația lui SCB(0) cu VB(t-t1) în SC.
Astfel :
SCTB = {(C, t) / C SCB(0) și t [0, t1] }
{ (C + VB(t – t1), t) / C SCB(0) și t [t1, t2]}
{(C + VB(t2 – t1), t) / C SCB(0) și t t2}.
Spațiul liber în SCT se definește astfel:astfel :
SCTliber = SCT \ SCTBi
Închiderea SCTliber se numește spațiul semi-liber în SCT. O aplicație continuă :[0,1]SCTliber (sau închiderea SCTliber) se numește un drum SCT-liber. Problema planificării dinamice a mișcării poate fi privită ca o construcție de drumuri SCT-libere în SCT între două configurații temporale date (Cinițial, 0) și (Cfinal, T). Astfel problema se reduce la găsirea unui drum printre obstacolele staționare (SCTBi).
3.1.2. Rezultatele complexității
Problema planificării dinamice a mișcării pentru un robot poligonal A translatând în plan, cu modulul vitezei limitat, printre obstacole poligonale ce translatează cu viteză liniară constantă, poate fi rezolvată cu un algoritm care variază polinomial cu numărul total de vârfuri ale lui A și Bi. Timpul de calcul al algoritmului crește exponențial cu numărul de obstacole. Când toate limitările pot fi exprimate semi-algebric, problema planificării dinamice a mișcării fără limitări de viteză și obstacole multiple aleatoare poate fi rezolvată într-un timp polinomial față de numărul și gradul limitărilor semi-algebrice.
3.1.3. Planificarea fără limită de viteză
3.1.3.1. Descompunerea celulară exactă
Când modulul vitezei lui A nu este limitat iar traiectoriile obstacolelor sunt exprimate sub formă algebrică, algoritmul general de planificare a drumului bazat pe descompunerea Collins se poate aplica cu câteva modificări minore. Diferitele CT– obstacole sunt reprezentate sub forma unor mulțimi semialSgebrice în SCT și planificarea este realizată cu restricția adițională că timpul este ireversibil.
Această restricție poate fi luată în calcul reprezentând o configurație temporală ca o listă (t,C1,…,Cm) Rm+1 (m fiind dimensiunea spațiului configurațiilor temporale ale lui A), unde timpul t este prima coordonată în aplicația în SCT. Astfel, toate celulele rezultate din descompunerea Collins a lui SCT, se vor proiecta pe axa timpului. Cu alte cuvinte, celulele sunt conținute în “cilindri” de deasupra intervalelor sau se proiectează de-a lungul axei timpului. Două celule K și K’ sunt în același cilindru (sau apar în același interval de timp) dacă și numai dacă proiecțiile (K) și (K’) se fac pe aceeași coordonată de timp. Dacă proiecțiile se fac pe coordonate de timp diferite, o celulă apare după cealaltă. Graful de conexiune CG este acum definit ca un graf direct ale cărui noduri sunt celule de dimensiuni (m+1) și m din descompunerea Collins a lui SCT. O celulă K este conectată cu o celula K’ dacă și numai dacă K și K’ sunt adiacente și orice K apare înainte de K’ sau K și K’ apar simultan, ceea ce este echivalent cu: coordonata temporală a lui (K) este mai mică sau egală cu coordonata temporală a lui (K’).
Pentru a construi o mișcare liberă între (Cinițial, 0) și (Cfinal, T), planificatorul de mișcare caută în CG o secvență de celule adiacente K1, …, Kp astfel încât (Cinițial, 0) K1 și (Cfinal, T) Kp. Din această secvență, dacă există vreuna, se generează un SCT–drum de la (Cinițial, 0) până la (Cfinal, T) la fel ca în cazul problemei de bază.
Dacă timpul de sosire T este nespecificat, se aplică aceeași metodă. Configurația finală în SCT este semidreapta {(Cfinal, T) / T 0}. Graful CG trebuie cercetat în căutarea unei secvențe de celule K1, …, Kp astfel încât Kp intersectează această semidreaptă. O cercetare a grafului CG cu timpul ca funcție de cost poate genera SCT–drumul care atinge configurația–scop în timpul cel mai scurt posibil, dacă există bineînțeles un drum liber în SCT.
3.1.3.2. Descompunerea celulară aproximativă
Descompunerea celulară aproximativă se aplică de asemenea la problema planificării dinamice a mișcării fără restricții de viteză. Se cere doar ca definirea grafului de conexitate să fie ușor modificată.
Se presupune că mulțimea configurațiilor temporale posibile în SCT este o zonă dreptunghiulară care a fost descompusă în celule dreptunghiulare mai mici, fiecare clasificată drept GOALĂ (dacă interiorul ei nu se intersectează cu nici un CT -obstacol), PLINĂ (dacă este conținută în întregime în regiunea CT–obstacolelor) sau MIXTĂ. Graful de conexitate CG corespunzător acestei descompuneri este un graf direct ale cărui noduri sunt celulele GOALE (sau și GOALE și MIXTE) ale descompunerii. O celulă K este conectată cu o celulă K’ de un arc orientat, dacă și numai dacă:
oricare din celule este adiacentă cu o fațetă paralelă cu axa timpului;
oricare din celule este adiacentă cu o fațetă care este perpendiculară pe axa timpului și proiecția lui K pe axa timpului este înaintea proiecției lui K’.
În figura 3.2. sunt prezentate:
a) cu șapte celule GOALE
b) ilustrează graful de conexitate corespunzător.
Deși nici un drum între K2 și K4 nu poate fi monoton cu timpul, acest lucru nu este reprezentat în graf, ceea ce înseamnă că graful trebuie limitat în mod corespunzător.
Figura 3.2. Ilustrează un spațiu temporal bi-dimensional al configurațiilor
Planificarea este executată de parcurgerea lui CG după o secvență de celule adiacente formând un canal GOL sau MIXT astfel că prima celula din secvență conține configurația temporală inițială și ultima celulă conține configurația temporală finală.
Această precizare a grafului de conexitate nu este suficientă pentru a garanta că și acest canal construit conține un SCT-drum strict monoton în timp. Este necesar deci să se adauge încă o limitare asupra metodei de căutare în graf, ilustrată în graful din figura 3.2. Deși există un drum strict monoton în timp între K2 și K3 și un drum strict monoton în timp între K3 și K4, nu există un astfel de drum între K2 și K4. Acest lucru nu este reprezentat în graful de conexitate deoarece depinde de celulele care au fost traversate înainte ca celula K4 să fie introdusă, și deci implică mai mult de două celule. Planificatorul poate rezolva această problemă în timpul căutării în graf reținând cel mai mic timp tprim la care poate fi în celula curentă [37]. Fie [tmin(K), tmax(K)] intervalul de timp în care celula K se proiectează pe axa timpului. tprim se calculează după cum urmează :
când planificatorul începe căutarea și se află în celula inițială:
tprim 0,
când planificatorul decide să treacă dintr-o celulă K într-o celulă K’:
tprim max{tprim, tmin(K’)}.
Se presupune că planificatorul a obținut K. Poate alege pe K’ ca și succesorul lui K în căutare dacă și numai dacă există un arc din K la K’ în CG și tprim < tmax(K’). Se consideră figura 3.2 și se presupune că începe căutarea la K1. Cel mai mic timp în K1 este 0. Căutarea poate continua spre K2 cu tprim = tmin(K2), apoi spre K3 cu tprim încă egal cu tmin(K2). K3 are doi succesori, K4 și K5, în CG. Totuși K4 nu poate fi ales ca și succesor al lui K3 deoarece tprim > tmax(K4).
Dacă este construit un canal GOL, poate fi extras cu ușurință din el un SCT–drum liber și strict monoton în timp.
3.1.4. Planificarea mișcării cu limită de viteză
Se consideră cazul în care modulul vitezei robotului este mărginit superior și nu există restricții referitoare la accelerația robotului.
Se va considera la început doar un tip specific de problemă dinamică pentru planificarea mișcării dinamice și se va descrie o metodă completă de planificare. De fapt, metoda generează un graf de vizibilitate extins în spațiul temporar al configurațiilor robotului.
Robotul este un poligon care se poate translata liber în R2. Astfel, SCT = R2x[0, +). Obstacolele Bi, i = 1, …, q, sunt poligoane care translatează cu viteze constante (care pot de varia de un obstacol la altul). Modulul vitezei liniare a robotului A este limitat superior de vmax. În spațiul configurațiilor lui A, problema este echivalentă cu planificarea mișcării unui punct între C–obstacole poligonale, obstacole care translatează cu viteze liniare constante. Se presupune că C– obstacolele nu se intersectează niciodată.
Fiecare CT–obstacol este obținut prin baleierea C–obstacolului corespunzător de-a lungul unei linii a cărei pantă relativă la axa timpului este determinată de viteza liniară constantă a obstacolului.
Se definesc și se utilizează următoarele tipuri de mișcări:
mișcarea directă este o mișcare a lui A cu viteză constantă (posibil nulă), astfel încât A nu intră în contact cu obstacolele, excepție făcând eventual sfârșitul mișcării. În plus, la fiecare punct terminal, unde mișcarea duce la un contact cu un obstacol Bi SCT–drumul reprezentând mișcarea directă în SCT, este suportat de o linie tangentă în punctul de contact corespunzător CT–obstacolului SCTBi.
mișcarea de contact este o mișcare a lui A de-a lungul unei submulțimi convexe (posibil chiar un singur punct) a marginii unui C–obstacol SCTBi, având ca punct de plecare și sosire vârfurile lui SCBi. În SCT, mișcarea este descrisă de un SCT–drum (posibil de lungime 0) care este conținut în frontiera lui SCTBi și începe și se termină într-o linie vârf.
mișcarea fundamentală este o mișcare a lui A care constă într-o mișcare directă, posibil urmată de o mișcare de contact.
mișcarea normală este o mișcare a lui A care constă într-o secvență de mișcări fundamentale, astfel încât oricare două mișcări directe sunt separate de-o mișcare de contact și nu există perechi de două mișcări de contact care să fie făcute în aceeași submulțime maximală a frontierei C–obstacolului. (Deși, dacă C–obstacolul este convex, o mișcare normală îl poate vizita cel mult odată).
3.1.4.3. Descompunerea celulară aproximativă
În paragraful precedent a fost descrisă modificarea făcută metodei descompunerii celulare aproximative ce rezolvă problema planificării dinamice a mișcării fără limitare de viteză. Această abordare poate fi modificată în continuare pentru a rezolva problema cu limitare de viteză.
Principiul folosit este următorul. În același timp cu generarea unui canal GOL (sau MIXT), planificatorul construiește un SCT–drum monoton în timp, conținut în canal și care satisface limitarea vitezei. Un mod de a construi acest drum este de a împărți fiecare celulă dreptunghiulară din canal într-o grilă de configurații temporale și de a căuta grila conținută în canal până acum. Deci, planificatorul caută (1) graful de conexitate al celulelor din canal, și (2) grila conținută în canalul generat pentru SCT–drumul ce satisface limitarea de viteză. Ori de câte ori planificatorul consideră necesară introducerea unei noi celule la sfârșitul canalului, trebuie să verifice că un drum poate fi extins la această celulă fără a depăși limitarea de viteză. Altfel, celula nu poate fi introdusă în canal.
Datorită împărțirii fiecărei celule, metoda de planificare nu garantează găsirea unui SCT–drum care să satisfacă limitarea de viteză dintr-un canal, chiar dacă acesta ar exista. Deci, ar putea să eșueze în încercarea de a rezolva problema dată, chiar dacă o soluție există. Metoda poate fi făcută mai exactă prin folosirea unei discretizări mai fine, dar aceasta ar crește considerabil timpul de calculare necesar.
3.1.4.3. Reglarea vitezei
Reglarea vitezei este o abordare în două faze a problemei dinamice a planificării mișcării. Această abordare constă dintr-o primă planificare a drumului din SCinițial până în SCfinal printre obstacolele staționare din W, și apoi reglarea vitezei lui A de-a lungul drumului astfel încât să se evite ciocnirile cu obstacole mobile. Astfel, problema originală este descompusă în două subprobleme. Prima, este o problemă de bază a planificării mișcării, care poate fi rezolvată cu una din metodele cunoscute. Cea de a doua subproblemă este o problemă de planificare a vitezei. Aceasta poate fi formulată ca o problemă dinamică de planificare a mișcării într-un spațiu temporal al drumurilor similar cu spațiul temporar al configurațiilor bidimensional.
Fie : ℓ [0, L] (ℓ) SC’liber drumul planificat în prima fază. SC’liber desemnează o mulțime de configurații unde A nu se intersectează cu obstacole staționare. Parametrul ℓ măsoară lungimea drumului între (0) și (ℓ). Astfel, L desemnează lungimea totală a drumul. Problema de planificare a vitezei este de a genera o funcție continuă : t [0, T] (ℓ) [0, L] cu (0) = 0 și (T) = L, astfel încât funcția compusă o : t [0, T] ((t)) verifică (((t)), t) SCTliber pentru toate t [0, T]. Aplicația trebuie aleasă astfel încât viteza lui A să fie mărginită de vmax. poate să nu fie bijectivă, astfel încât A poate să traverseze câteva configurații din de mai multe ori.
Fie spațiul ℓt [0, L] x [0, T] notat cu PT. PT se numește spațiul temporal al drumurilor. Pentru un drum dat al lui A în SC, un obstacol mobil B(t) are corespondent în acest spațiu o regiune PTB numită PT–obstacol, definită astfel:
PTB = { (ℓ, t) [0, T] x [0, T] / (ℓ) SCB(t) }.
Fie:
PTliber = [0, L] x [0, T] \ PTBI
unde PTBI sunt PT-obstacole care corespund obstacolelor mobile din W. Problema planificării vitezei este astfel redusă la a găsi un drum continuu, strict monoton în timp în PTliber numit PT–drum liber, între (0, 0) și (L, T). Într-adevăr, acest PT–drum liber determină o funcție unică (t) astfel încât t [0, T], (((t)), t) SCTliber. Panta PT– drumului în raport cu axa timpului trebuie de asemenea să satisfacă restricțiile de viteză, și anume:
dℓ / dt vmax
PT–obstacolele pot avea forme complicate. Un C–obstacol conex SCB poate chiar să aibă ca și corespondent în PT o regiune alcătuită din mai multe componente conexe. În cele ce urmează se va considera că PT–obstacolele sunt poligoane. Această reprezentare este exactă când drumul este o secvență de segmente în SC = R2 sau R3 și C–obstacolele mobile sunt poligoane/poliedre care translatează cu viteza liniară constantă (problema evitării asteroizilor). În alte cazuri, reprezentarea se obține prin aproximarea PT–obstacolelor.
Graficul din figura 3.3. este o rafinare a grafului de vizibilitate redus care incorporează principiile ireversibilității timpului și restricțiile pentru limita superioară a modulului vitezei robotului. Drumul de conectare (0, 0) la (L, T) este afișat cu linie îngroșată.
Figura 3.3. Această figură prezintă un spațiu temporal al drumurilor poligonal simplu cu două PT–obstacole dreptunghiulare și cercetarea corespunzătoare a grafului.
Cu PT–obstacolele poligonale, problema planificării vitezei poate fi ușor rezolvată utilizând o variantă a metodei grafului de vizibilitate. Varianta constă în căutarea unei adaptări a grafului vizibilității redus. Noul graf, notat cu G, este un graf orientat definit astfel: nodurile lui G sunt vârfurile convexe ale PT–obstacolelor și ale celor două puncte (0, 0) și (L, T). Un arc al lui G conectează nodul (ℓ, t) cu (ℓ’, t’) dacă și numai dacă:
t < t’ , vmax
și orice segment de dreaptă care leagă două puncte este muchia unui PT-obstacol sau se află complet în PTliber, excepție făcând la fiecare din cele două capete, unde segmentul este tangent la PT–obstacol.
Se poate arăta că există un PT-drum semiliber ce conectează (0, 0) cu (L, T) în închiderea SPTliber dacă și numai dacă există un drum în G între două noduri corespunzătoare. Figura 3.3 arată un spațiu temporal al drumurilor poligonal și graful G corespunzător. Dacă (0, 0) și (L, T) sunt în aceeași componentă conexă a lui G, cercetarea lui G permite construirea unui PT–drum soluție. Altfel, cercetarea se termină cu eroare. Metoda de mai sus poate fi ușor extinsă pentru cazul în care timpul T de sosire este nespecificat.
Abordarea reglării de viteză este inerent incompletă. Dându-se un drum al lui A care elimină coliziunile cu obstacolele staționare, poate exista un profil al vitezei de-a lungul drumului care permite să se elimine coliziunile cu obstacole mobile. Acest lucru se întâmplă de exemplu când un obstacol vine spre robot pe aproximativ același drum geometric. Este posibil ca alt drum să poată să-l facă să evite coliziunile atât cu obstacolele fixe, cât și cu cele mobile. Ori de câte ori faza de planificare a vitezei eșuează, planificatorul poate încerca să genereze alt drum printre obstacolele staționare. Această abordare, însă, nu dă o cale sistematică pentru a alege acest alt drum.
Cazul când în spațiul de lucru sunt mai mulți roboți
În acest paragraf se va considera o colecție de p roboți, Ai , i = 1,…, p, care se mișcă în același spațiu de lucru W = RN , N = 2 sau 3, printre obstacole staționare Bj, j = 1, …, q. Roboții se mișcă independent unul față de altul, dar nu pot ocupa același spațiu în același timp. Problema constă în planificarea unei mișcări fără ciocniri a roboților din configurația inițială până în cea finală.
3.2.1. Spațiul compus al configurațiilor
Fie SC1, …, SCp spațiile configurațiilor individuale ale celor p roboți A1, …, Ap. Fiecare spațiu SCi, i [1, p] conține două tipuri de C–obstacole:
C–obstacole corespunzătoare coliziunilor lui Ai cu obstacolele staționare B1, …, BC;
C – obstacole corespunzătoare coliziunilor lui Ai cu alți roboți.
C–obstacolele de tipul al doilea depind de mișcarea celorlalți roboți și nu pot fi reprezentate ca regiuni fixe în SCi.
Cea mai directă cale de a extinde mișcarea la roboți multiplii constă în a considera obiectele A1, …, Ai ca și componente ale aceluiași robot compus A = {A1, …, Ap}.
Fie SAi un sistem de referință cartezian atașat lui Ai. O configurație C a lui A este specificată de poziția și orientarea fiecărui sistem SAi (i = 1,…, p) în raport cu sistemul de referință atașat spațiului de lucru SW.
Având în vedere că roboții se mișcă independent unul față de altul, o configurație a lui A este de forma C = ( C1, …, Cp), unde SCi Ci denotă o configurație a lui AI, conduce la A(C) = A1 (C1) … Ap (Cp). Configurația spațială a lui A, C = C1 x…x Cp se numește spațiul compus al configurațiilor lui A1 până la Ap. Acesta este o mulțime netedă de dimensiune , unde mi descrie dimensiunile lui SCi.
Există încă două tipuri de C–obstacole, dar ambele sunt independente funcție de timp:
C–obstacolul datorat interacțiunii lui Ai cu obstacolul Bj, notat cu SCBij și definit:
SCBij = { C = (C1, …, Ci, …, Cp) C / Ai(Ci) Bj 0 }.
C–obstacolul datorat interacțiunii lui Ai și Aj, i < j este notat cu SCAij și definit:
SCAij = {C = (C1, …, Ci, …, Cj, …, Cp) C / Ai(Ci) A(Cj) 0}.
Determinarea frontierelor lui SCAij se poate realiza printr-o ușoară adaptare a metodelor prezentate anterior.
Spațiul liber în SC este definit astfel:
SCliber = SC /
Un drum liber între două configurații Cinițial și Cfinal este definit:
: [0, 1] SCliber, cu (0)= Cinițial și (1)= Cfinal.
Astfel, problema planificării unui drum liber pentru mișcarea mai multor roboți în același spațiu de lucru este formulată ca o problemă de planificare a unui drum liber pentru un singur robot compus. Proiecția lui pe fiecare spațiu SCi, i [1, p] este drumul corespunzător lui Ai. Deși timpul nu apare explicit, execuția lui cere ca roboții individuali să-și urmeze propriul drum într-o manieră coordonată. Schimbând viteza unui robot, este necesar ca și viteza celorlalți roboți să fie schimbată cu același factor.
3.2.2. Planificarea centralizată
Se numește planificare centralizată abordarea ce constă în planificarea de drumuri coordonate ale mai multor roboți ca un drum în spațiul compus al configurațiilor. Această abordare permite utilizarea unei metode generale de planificare a drumului în cadrul problemei de bază.
Ca o ilustrare, figura 3.4 arată câteva configurații de-a lungul unui drum pentru doi roboți modelați prin dreptunghiuri, într-un spațiu de lucru cu trei coridoare drepte. Cei doi roboți nu pot să treacă simultan prin același coridor. În planificarea mișcării este esențială interschimbarea roboților în coridorul central. Drumul a fost generat utilizând metoda bazată pe câmpuri potențiale aleatoare într-un spațiu compus al configurațiilor cu 6 dimensiuni al celor doi roboți.
Au fost dezvoltate mai multe metode specifice pentru a rezolva unele cazuri particulare de probleme de planificare a mișcării pentru cazul când în spațiul de lucru acționează mai mulți roboți.. De exemplu, Schwartz și Sharir (1983c) [37] propun metoda descompunerii celulare exacte pentru planificarea mișcării în plan a două discuri, printre obstacole poligonale. Metoda este bazată pe definiția curbelor critice (în spațiul configurațiilor individual bidimensional al discurilor) unde posibilele contacte între obstacole și discuri se schimbă calitativ.
Barraquand, Langlois și Latombe (1989b) [37] prezintă o metodă de câmp potențial pentru planificarea mișcării mai multor discuri într-un mediu ce conține coridoare înguste și în care două discuri nu pot să treacă simultan. Metoda construiește și în același timp cercetează un graf local minim al funcției potențial, definită în SC = R2p, unde p este numărul de discuri. Unicitatea metodei constă în tehnica folosită pentru a ieși dintr-o zonă de minim local. La fiecare minim local întâlnit, metoda simulează o serie de mișcări limitate. Fiecare mișcare limitată este generată prin forțarea unei coordonate ale configurației, să crească sau să scadă, până când se obține un punct șa al funcției potențial. În timpul mișcării limitate, celelalte m-1 coordonate sunt alese de-a lungul pantei negative a gradientului potențialului. De exemplu, se consideră cazul când o mișcare continuă face ca două discuri să se miște unul spre celălalt în același coridor îngust. La un moment dat, cele două discuri nu mai pot avansa unul spre celălalt fără a se produce o coliziune între ele. Atunci, s-a obținut un minim local al funcției potențial de către mișcarea uniformă continuă. O mișcare limitată este mișcarea înapoi a unuia din cele două discuri, în timp ce celălalt disc înaintează de-a lungul gradientului negativ până când există destul spațiu liber pentru ca cele două discuri să treacă unul pe lângă celălalt (punct șa al potențialului). Această metodă a fost testată cu succes cu până la 10 discuri.
Figura 3.4. Problema de planificare constă în a interschimba doi roboți într-un spațiu de lucru. Cei doi roboți nu pot să treacă simultan prin același coridor. În figură se pot vedea câteva cadre de-a lungul drumului planificat, rezolvarea fiind făcută cu metoda câmpului potențial aleator. Cei doi roboți trebuie să se deplaseze în configurații intermediare înainte de a ajunge în configurația destinație.
Tournassoud Tournassoud (1986) [37] propune o variantă a metodei câmpului potențial în care coordonarea mișcării devine o problemă de optimizare locală. Ideea de bază este de a forța obiectele mobile să alunece de-a lungul unor hiperplane tangente și separate.
3.2.3. Planificarea decuplată
O cale de a reduce complexitatea de calcul a problemei de planificare a drumului pentru mai mulți roboți este de a planifica la început câte un drum pentru fiecare robot, mai mult sau mai puțin independent față de ceilalți roboți și de a lua în considerare interacțiunile dintre drumuri. Acest tip de abordare a problemei se va numi planificare decuplată.
De fapt, cât timp planificarea centralizată este exponențială în m =mi, planificarea decuplată este exponențială în maxi[1,p]{mi}. Oricum, acest câștig se transformă într-o pierdere de complexitate. Abordarea unei planificări decuplate poate eșua în planificarea unui drum, în timp ce abordarea centralizată utilizând același tip de metodă pentru planificarea drumului va avea succes (poate însă cu riscul unui calcul îndelungat).
Se prezintă în continuare două metode pentru planificarea decuplată: planificarea prioritară și coordonarea drumului.
3.2.3.1. Planificarea prioritară
Planificarea prioritară constă în considerarea mișcărilor lui Ai, un robot la un moment dat, cu i = 1, …, p. La fiecare iterație, un drum al lui Ai este generat în spațiul temporal al configurațiilor SCTi al lui Ai eliminând coliziunile atât cu obstacole Bj, j = 1, …, q, cât și cu roboții A1, …, Ai-1. Deci mișcarea lui Ai este planificată astfel încât robotul se deplasează printre q obstacole staționare și i – 1 obstacole mobile. Drumul lui A1 este planificat în SC1, fiind setată o viteză arbitrară pentru a proiecta A1 în spațiul temporal al configurațiilor celorlalți roboți. Această viteză de obicei determină un factor de scală de-a lungul axei timpului a acestor spații. Multiplicarea vitezei lui A1 cu o constantă are ca rezultat multiplicarea vitezelor celorlalți roboți cu același factor. Drumul lui A1 poate fi generat utilizând metodele cunoscute de planificare a drumului.
Comanda roboților face necesară asigurarea unei priorități fiecărui robot. Prioritățile pot fi asignate aleator. Cel mai bun mod de a calcula prioritățile este funcție de restricțiile de mișcare. De exemplu, o regulă simplă poate fi planificarea mișcării celui mai mare dintre roboți, înaintea unuia mai mic. Buckley (1989a) propune asignarea priorităților încercând să se maximizeze numărul de roboți care să se miște în linie dreaptă, din poziția inițială până în cea finală.
Abordarea planificării prioritare creează dificultăți în rezolvarea problemei de planificare din figura 3.4. Într-adevăr, drumul primului robot (se presupune cel mai lung), pare și cel mai direct (de-a lungul drumului, robotul stă în coridorul central). Acest lucru face imposibilă găsirea unui drum pentru cel de al doilea robot, deoarece coridorul este prea îngust și nu permite ca roboții să treacă unul pe lângă altul. Planificatorul poate încerca să găsească alt drum pentru primul robot, dar abordarea planificării prioritare nu oferă vreo cale sistematică pentru a alege alt drum. În plus, prin acceptarea mersului înapoi, complexitatea în timp a abordării planificării prioritare este mărită substanțial. Astfel, când abordarea eșuează, decât să se pornească înapoi, este preferabil să se încerce alt algoritm bazat pe abordarea planificării centralizate sau să se termine procesul.
3.2.3.2. Coordonarea drumului
Coordonarea drumului este o abordare a planificării decuplate propusă de O’Donnel și Lozano-Perez (1989). Ea este bazată pe o tehnică de scheduling pentru lucrul cu resurse limitate, care a fost dezvoltată inițial pentru accesul concurent la o bază de date a mai multor utilizatori. În acest caz, spațiul este o resursă partajată. Abordarea este aplicabilă atunci când problema de planificare include doar doi roboți, A1 și A2. Problema de planificare constă în primul rând din generarea unui drum liber pentru fiecare din cei doi roboți, independent unul de celălalt, și apoi coordonarea celor două drumuri, astfel ca roboții să nu se ciocnească între ei.
Fie : 1 : s1 [0, 1] 1(s1) SC1,liber
2 : s2 [0, 1] 2(s2) SC2,liber
două drumuri libere generate pentru A1 și A2. SC1,liber (respectiv SC2,liber) reprezintă spațiul liber în spațiul configurațiilor lui A1 (respectiv A2) obținut prin ignorarea celuilalt robot. Se consideră s1s2 spațiul [0, 1] x [0, 1]. Orice drum continuu în acest spațiu care conectează (0, 0) cu (1, 1) se numește plan (schedule) și determină o execuție coordonată a celor două drumuri. De exemplu planul ce unește (0, 0) cu (1, 0) printr-un segment de linie dreaptă și apoi (1, 0) cu (1, 1) cu alt segment de linie dreaptă corespunde cazului când A1 se mișcă primul și execută complet drumul 1 înainte ca A2 să se miște de-a lungul lui 2. Dacă s1 (respectiv s2) este proporțional cu lungimea segmentului de drum dintre 1(0) și 1(s1) (respectiv 2(0) și 2(s2)), atunci planul ce conectează (0, 0) cu (1, 1) printr-un singur segment de linie dreaptă, diagonala dreptunghiului [0, 1] x [0, 1] corespunde cazului când cei doi roboți se mișcă simultan, cu un raport constant al modulelor vitezelor proprii.
Se definește regiunea de obstacole în s1s2 ca o mulțime de perechi (s1,s2) astfel ca A1(1(s1)) A2(2(s2)) 0. Faza a doua a abordării de coordonare a drumurilor este de a construi un plan liber (adică un plan care nu traversează această regiune de obstacole). Astfel, abordarea de coordonare a drumurilor, corespunde la restricțiile aplicate drumului lui A = {A1, A2} în spațiul compus al configurațiilor SC = SC1 x SC2 să se afle în intersecția celor două subspații ale căror proiecții în SC1 și SC2 sunt 1 și 2. Spațiul s1s2 este obținut prin aplatizarea acestei intersecții care este bidimensională, pe un plan.
Se observă că toate abordările de coordonare a drumului fixează restricții mai puternice asupra căutării unei soluții decât abordarea planificării prioritare. În același timp, coordonarea drumului poate să eșueze mai des. Când abordarea coordonării drumurilor eșuează, este indicat să se execute un algoritm bazat pe abordarea planificării prioritare. Algoritmul poate utiliza drumul 1 deja generat și planifica un SCT-drum al lui A2 în SCT2 tratând A1 ca un obstacol mobil. Dacă algoritmul eșuează din nou, se poate încerca un algoritm de planificare centralizată.
În general, regiunea obstacolelor din spațiul s1s2 constă din câteva submulțimi conexe ale căror forme sunt complicate arbitrar. Se subîmparte fiecare drum i, i = 1 sau 2 într-o secvență wi de segmente de drum determinate de intervalele 1,ki = [si,ki, si,ki+1] cu ki = 0, …, wi-1, si,0 = 0 și si,wi = 1. Uzual, toate intervalele i,k de-a lungul aceluiași drum i determină segmente de drum de lungime egală. Aceste subdiviziuni transformă spațiul continuu s1s2 într-o matrice de w1 x w2 celule dreptunghiulare închise 1,k1 x 2,k2. În continuare se va nota cu kk1,k2 celula 1,k1 x 2,k2. Fiecare celulă kk1,k2 este GOALĂ dacă regiunile baleiate de A1 și A2 când (s1, s2) baleiază 1,k1 x 2,k2 nu se intersectează, și anume :
{A1(1(s1)) / s1 1,k1 } {A2(2(s2)) / s2 2,k2 } = 0
Celula este PLINĂ în caz contrar. Astfel, algoritmul garantează că cei doi roboți nu se vor ciocni într-o celulă GOALĂ (chiar și pe marginile ei), în timp ce ei pot intra în coliziune într-o celulă PLINĂ. Clasificarea celulelor poate fi mai mult sau mai puțin complicată depinzând de forma roboților, dar de obicei este mai rezonabil să se aproximeze forma ariei baleiate de un robot când configurația lui variază de-a lungul unui segment de drum.
Figura 3.5. Această figură arătă diagrama de coordonare a doi roboți. Fiecare celulă dreptunghiulară determină segmente de configurații a doi roboți de-a lungul a două drumuri 1 și 2. Fiecare celulă este etichetată ca GOALĂ (celule albe) dacă robotul nu intersectează alta în nici una din aceste configurații, altfel, ea este etichetată ca PLINĂ (celule negre). Linia groasă arată un plan liber generat prin căutarea în rețeaua alcătuită din marginile ce delimitează celulele GOALE și diagonalele lor. Un program liber determină o clasă de mișcări coordonate de-a lungul cărora cei doi roboți nu se pot ciocni.
Spațiul discretizat s1s2 cu celule etichetate este numit diagrama de coordonare. Figura 3.5 este un exemplu de astfel de diagramă, cu celule GOALE de culoare albă. Se restricționează drumurile posibile în diagrama de coordonare la rețeaua definită după cum urmează. Nodurile rețelei sunt toate vârfurile pentru celule GOALE. Legăturile sunt toate marginile și diagonalele acestor celule. Se notează fiecare nod prin coordonatele lui discrete (i, j), cu i [0, w1] și j [0, w2]. Un program liber poate fi generat prin căutarea în această rețea a unui drum ce conectează (0, 0) cu (w1, w2). Linia îngroșată din figura 3.5 arată un astfel de program liber. (Se reamintește că frontiera unui celule GOALE este liberă de coliziuni).
Se va descrie o tehnică care permite generarea unui program liber fără căutare. Această tehnică poate genera doar programe care sunt monotone cu
respectarea lui s1 și s2. Aceasta se întâmplă ori de câte ori un astfel de schedule există. Înainte de descriere, se va introduce noțiunea de închidere – SW.
Figura 3.6. Diagrama de coordonate extinsă este obținută prin adăugarea unui segment de drum fictiv la sfârșitul fiecăruia din cele două drumuri 1 și 2. (a).
De-a lungul acestui segment de drum, robotul corespunzător nu se mișcă. Regiunea obstacolului este extinsă ca în figura a (celule hașurate). SW – închidere a regiunii – obstacol extinse este prezentată este prezentată în figura b (celulele negre și hașurate). Dacă există un program liber monoton, traversează numai celulele care nu sunt conținute în aria SW a regiunii – obstacol extinse. Linia groasă din figura b reprezintă programul liber construit cu algoritmul prezentat.
Fie (s’1, s’2) și (s’’1, s’’2) două puncte în planul s1s2. Ele sunt necomparabile dacă și numai dacă (s’1 – s’’1) (s’2 – s’’2) < 0. Se presupune că (s’1, s’2) și (s’’1, s’’2) sunt necomparabile, și (fără a se pierde generalitatea) că s’1 < s’’1 (respectiv s’2 < s’’2 ). Conjugata – SW a (s’1, s’2) și (s’’1, s’’2) este punctul (s’1, s’’2). O regiune conexă R din spațiul s1s2 este SW – închisă dacă și numai dacă conjugata SW a oricare două puncte necompatibile în R este de asemenea în R. SW – închiderea unei regiuni conexe S este cea mai mică regiune R SW –închisă ce conține pe S. SW – închiderea unei regiuni neconexe este definită ca reuniunea dintre închiderile – SW ale tuturor componentelor conexe.
Se consideră diagrama de coordonate. Fie S regiunea de obstacole. Se extinde diagrama adăugând un rând și o coloană celulelor din partea de sus și din dreapta diagramei. Această extindere corespunde adăugării unui segment de drum fictiv la sfârșitul fiecărui drum 1 și 2. De-a lungul acestui segment de drum, robotul nu se mișcă. Regiunea S se extinde astfel:
Dacă pentru orice j [0, w2-1] celula Kw1-1,j este PLINĂ, atunci toate celulele Kw1,k, pentru k = 0, …, j sunt incluse în S;
Dacă pentru orice i [0, w1-1] celula Kj,w2-1 este PLINĂ, atunci toate celulele Kk,w2, pentru k = 0, …, i sunt incluse în S.
Figura 3.6.a arată diagrama extinsă corespunzătoare diagramei de coordonate din figura 3.5.
Fie R aria SW a lui S. Nici unul din programele libere monotone din diagrama de coordonate nu traversează vreo celulă inclusă în R. În plus, un program monoton liber există dacă și numai dacă nici una din cele două celule K0,0 și Kw1-1,w2-1 nu sunt conținute în R. Mai general, un program monoton liber există între (i, j), 0 i w1, 0 j w2 și (w1, w2) dacă și numai dacă nici una din celulele Ki,j și Kw1-1,w2-1 nu sunt conținute în R.
Dacă există un program monoton liber, acesta este construit (fără parcurgerea nici unui graf) de următorul algoritm:
i 0; j 0;
while i < w1 or j < w2 do begin
if ki,j R then
if i < w1 and j < w2 then
i i+1; j j+1; move to (i,j);
else
if i < w1 then i i+1; move to (i,j);
else j j+1; move to (i,j);
else if i < w1 and ki,j-1 R then i i+1; move to (i,j);
else j j-1; move to (i,j);
end;
Un program liber construit cu acest algoritm este prezentat cu linie groasă în figura 3.6.b.
3.3. Roboți articulați
În această parte se va prezenta cazul în care robotul este alcătuit din câteva obiecte rigide mobile conectate prin cuple mecanice cu mișcări limitate. Un braț manipulator este un exemplu tipic de astfel de robot. El constă într-o secvență de obiecte rigide conectate într-un lanț de către cuple.
3.3.1. Spațiul configurațiilor
Se consideră un robot A realizat din elemente rigide A1, …, Ap. Oricare două obiecte Ai și Aj pot fi conectate printr-o cuplă cinematică. Pentru simplificare se presupune că se consideră doar cuple cinematice rotație sau de translație. O cuplă cinematică de rotație este o restricție care permite ca mișcarea relativă a lui Ai și Aj să fie o rotație în jurul unei axe fixe determinată de ambele obiecte. O cuplă cinematică de translație este o restricție care limitează mișcarea relativă la o translație de-a lungul unei axe fixe determinată de ambele obiecte.
Fie SA sistemul de referință atașat elementului Ai, i 1, …, p. Configurația lui A reprezintă o specificare a poziției și orientării fiecărui sistem de referință SAi, i 1, …, p, cu respectarea SW. Dacă obiectele sunt libere în W = RN, spațiul configurațiilor lui A este:
Cuplele cinematice impun restricții asupra configurației din SC’. Aceste restricții selectează un subspațiu SC al lui SC’ de dimensiune mai mică care este actuala configurație spațială a lui A.
Figura 3.7. Brațul manipulator plan A constă din două elemente A1 și A2. A1 este conectat la spațiul de lucru printr-o cuplă de rotație, iar A2 este conectat la A1 printr-o cuplă de translație. Spațiul configurațiilor lui A este un subspațiu bidimensional al lui (R2 x SO(2))2.
Brațul manipulator plan A constă din două elemente A1 și A2. A1 este conectat la spațiul de lucru printr-o cuplă de rotație, iar A2 este conectat la A1 printr-o cuplă de translație.. Spațiul de lucru este W = R2. În acest exemplu, SC’ = (R2 x SO(2))2 este un spațiu 6–dimensional. Prima cuplă impune două restricții prin care punctul pe care A1 se poate roti este fixat în spațiul de lucru. Cupla a doua impune două restricții în plus cu privire la poziția și orientarea lui A2 față de A1. Cele patru restricții sunt independente și determină un subspațiu SC de dimensiune 2 în SC’.
În general se consideră SC independent față de SC’, având în vedere că dimensiunea lui este mult mai mică.
Se va presupune în continuare că A este un robot articulat ce nu conține bucle cinematice, adică nu există nici o secvență A’1, …, A’r, A’r+1, cu A’r+1 = A’1 și A’i+1 fiind conectată cu A’i de o cuplă, pentru orice i [1, r]. Atunci numărul total al cuplelor lui A este exact p.
Având în vedere presupunerea anterioară, se consideră spațiul de lucru ca un obiect fictiv notat A0. Fiecare obiect Aj, (j [1, p]) este conectat la un singur obiect Ai, (i [0, p]), i j.
Întregul robot A poate fi reprezentat printr-o structură arborescentă ale cărei noduri le reprezintă obiectele A0, …, Ap iar arcele le reprezintă cuplele. Rădăcina arborelui este A0. Pentru oricare două obiecte Ai și Aj, unde Aj este succesorul lui Ai în arbore, putem defini configurația lui Aj relativ la Ai ca o specificare a poziției și orientării lui SAj cu respectarea lui SAi. Fie SC(i)j spațiul configurațiilor lui Aj relativ la Ai. Presupunem momentan că nu există nici un opritor mecanic în construcția unei cuple. Dacă două obiecte sunt conectate cu o cuplă de rotație, atunci: SC(i)j = S1. Dacă două obiecte sunt conectate printr-o cuplă de translație, atunci SC(i)j = R. Rezultă că, spațiul configurațiilor SC ale unui obiect articulat A fără bucle, făcut din p obiecte rigide conectate cu p1 cuple de rotație și p2 cuple de translație, unde p = p1 + p2, este [Burdick, 1988]:
Astfel, spațiul configurațiilor unui braț manipulator cu două cuple (figura 3.7), este S1 x R. În acest mod, spațiul configurațiilor unui robot cu 10 cuple (prezentat în figura 3.8) este (S1)7 x R3.
Se presupune că nu există limitatoare mecanice în construcția cuplelor, astfel spațiul configurației robotului este SC = (S1)7 x R3.
Figura 3.8. Această figură redă un robot articulat cu trei cuple de translație (telescopice) și șapte cuple de rotație.
Ca generalizare, spațiul configurației unui robot articulat cu p cuple de rotație și de translație, și fără bucle cinematice este o suprafață curbă p dimensională. O hartă a acestei suprafețe poate fi definită asociind un unghi în intervalul (0, 2) la fiecare cuplă de rotație și un număr real fiecărei cuple de translație. Astfel, o configurație C este reprezentată de o listă de coordonate (q1, …, qp), fiecare descriind poziția relativă și orientarea a două obiecte din A conectate printr-o cuplă. Roboții având cuple de rotație au o configurație spațială multiplu conectată și sunt necesare câteva hărți pentru a forma un atlas. În practică, este de obicei suficient să considerăm o singură hartă, cu fiecare coordonată unghiulară fiind între [0, 2) și se aplică o operație de modulo 2 coordonatei.
(a) (b) (c)
Figura 3.9. Spațiul configurațiilor unui braț manipulator plan cu două cuple de rotație (figura a) este un tor în R3 (figura b). O parametrizare a acestui spațiu este obținută reprezentând fiecare configurație ca (q1, q2) [0, 2) x [0, 2) (figura c), unde q1 și q2 sunt unghiuri asociate cuplelor, ilustrate în figura a. Această parametrizare corespunde la decuparea torului de-a lungul a două generatoare. Marginile opuse ale pătratului din figura c, trebuie să fie identificate procedural prin aritmetica modulo 2 pentru a captura multiple conexiuni ale torului.
Se consideră ca exemplu un braț manipulator cu două cuple de rotație, ca în figura 3.9.a. Spațiul configurațiilor acestui robot este S1 x S1, adică un tor într-un spațiu 3-dimensional Euclidian. (figura 9.b). O hartă a acestei suprafețe poate fi definită prin asocierea unui unghi cuprins în intervalul (0, 2) la fiecare din cele două cuple. Figura 3.9.a. ilustrează două astfel de unghiuri, q1 și q2. Torul este multiplu conectat și sunt cerute câteva hărți pentru a forma un atlas. În cele mai multe cazuri se consideră o hartă și se lasă cele două unghiuri q1 și q2 să își modifice valoarea în [0, 2] cu o operație modulo 2. Această simplificare corespunde reprezentării unui tor cu un pătrat [0, 2] x [0, 2] (figura 3.9.c) ale cărui margini opuse sunt identificate procedural.
Noțiunile de C–obstacol, spațiul liber și drum liber definite pentru obiecte multiple se pot extinde la un robot articulat fără modificări. Sunt, de asemenea, două tipuri de C–obstacole, unul datorită interacțiuni unui obiect Ai și un obstacol Bj și altul datorită interacțiunii a două obiecte Ai și Aj. Figura 3.10 ilustrează construirea C–obstacolelor de acest prim tip pentru un manipulator plan cu două cuple de rotație. Calculul ecuației exacte a frontierei unui C–obstacol pentru un robot articulat a fost recent cercetat de Hwang (1990), Dooley și McCarthy (1990) și Ge și McCarthy (1990).
În general, mișcarea relativă a două obiecte conectate printr-o cuplă, este limitată de o pereche de opritoare mecanice, cu restricționarea intervalelor de valori corespunzătoare configurației de coordonate la un interval conectat. Opritoarele mecanice acționează ca niște “obstacole invizibile”. Mulțimea configurațiilor în care nici o cuplă nu a ajuns la opritor este o submulțime deschisă a lui SC. Complementara acestei mulțimi este regiunea C–obstacolelor, care conține obstacole invizibile datorită mulțimii de opritoare. De obicei, opritoarele mecanice din construcția fiecărei cuple sunt independente de configurația robotului. Atunci submulțimea de configurații lăsate admisibile de opritoare este o intersecție a intervalelor în spațiul cartezian reprezentând SC.
Se consideră o cuplă de rotație conectând Ai cu Aj. Dacă opritoarele mecanice din cuplă opresc Aj să facă o rotație completă de 2 relativ la Ai, limitatorul elimină necesitatea de a aplica operația de modulo 2 la configurația de coordonate corespunzătoare. Dacă, în loc de o singură rotație, mecanismul opritor nu permite lui Ai să realizeze r (r > 1) rotații complete, atunci configurația de coordonate poate lua valori într-un interval de lungime 2r, (unde r nu este necesar a fi întreg). În acest mod, configurația este explicit reprezentată ținând cont de ambele opritoare.
3.3.2. Metode de planificare a drumului
Spațiul configurațiilor SC ale unui robot articulat este doar un alt spațiu topologic. Atâta timp cât limitările impuse de cuple asupra mișcării relative a obiectelor pe care le leagă pot fi exprimate în formă algebrică (cum se întâmplă în cazul cuplelor de translație și de rotație) se pot aplica metodele generale. Aceste metode necesită un timp de calcul simplu și respectiv dublu exponențial față de dimensiunea spațiului configurațiilor SC.
Metoda descompunerii celulare aproximative se poate aplica de asemenea, deși transformarea obstacolului în spațiul configurațiilor este mai dificilă decât pentru problema de bază a planificării mișcării cu obiecte poligonale/poliedrice.
Metoda câmpului potențial poate fi aplicată la obiecte articulate cu adaptări minore. Până acum, cele mai bune rezultate practice asupra roboților cu multe cuple au fost obținute cu această metodă.
Datorită faptului că mișcările părților rigide dintr-un robot articulat sunt independente, metoda “planificării decuplate” nu se poate aplica.
Figura 3.10. Robotul este un manipulator plan cu două cuple de rotație care se mișcă printre trei obstacole circulare B1, B2 și B3 (figura a). Cele două legături ale sale sunt segmente de dreaptă de lungime ℓ1 și ℓ2. Prima cuplă se află în punctul O. Cea de-a doua ce mișcă în cercul de rază ℓ1 cu centrul în O. Spațiul configurațiilor este produsul S1x S1 ca în figura b. Zonele hașurate din figura b reprezintă C–obstacolele.
3.3.3. Descompunerea celulară aproximativă
Principiul descompunerii celulare aproximative este suficient de general pentru a fi aplicabil la un robot articulat. Problema principală este construcția deopotrivă a spațiului liber și a regiunii C–obstacolelor în spațiul cartezian ce reprezintă SC. Se va descrie o metodă care generează o aproximație conservativă a spațiului liber (de fapt o submulțime a actualului spațiu liber), discretizând mișcarea fiecărei cuple în miniintervale. Această reprezentare aproximativă este apoi utilizată la construirea unui graf de conectivitate, care este parcurs în căutarea unui canal conectând configurațiile inițiale și finale. Cu câteva diferențe minore, aceasta este metoda propusă de Gouzenes, (1984b), Laugier și Germain (1985).
Pentru simplificarea acestei reprezentări, se vor face câteva presupuneri care apoi nu vor fi dificil de anulat. La început se va presupune că A este o secvență de p obiecte, A1, …, Ap cu fiecare două obiecte succesive Ai și Ai+1 conectate printr-o cuplă cinematică de translație sau de rotație. A1 este primul obiect din secvență și este conectat la spațiul de lucru printr-o cuplă. Se va reprezenta configurația C a lui A printr-o listă cu p parametri, (C1, …, Cp). Fiecare parametru Ci (i [1, p]), determină poziția și orientarea lui SAi relativ la SAi-1 cu SA0 = SW. Cea de a doua presupunere este că fiecare Ci baleiază un interval mărginit Ii = (C-i, C+i). Dacă Ci corespunde la o cuplă de rotație, fără limitatoare mecanice, intervalul este Ii = [0, 2) și se utilizează operația de modulo 2. A treia presupunere este că oricum ar fi alese două obiecte Ai și Aj, acestea nu se pot ciocni unul cu altul. Singurele ciocniri ce se vor lua în considerare sunt cele între obiectele Ai (i [1, p]) și obstacolele Bj ( j [1, q]). Poziția și orientarea lui SA relativ la SW pentru orice i [1, p] sunt complet determinate de parametrii de la C1 la Ci. Se va nota cu Ai(C1, …, Ci) regiunea din W ocupată de Ai.
Este posibilă construirea unei aproximații ale regiunii C–obstacolelor în I1 x … x Ip Rp după cum urmează: fiecare interval Ii, i = 1, …, p este împărțit în intervale mai mici care nu se suprapun, i,ki, ki = 1,2,… la o rezoluție dinainte specificată. Dacă regiunea baleiată de A în spațiul de lucru, când (C1, …, Cp) baleiază celulele 1,k1 x … x p,kp nu interesează nici un obstacol, atunci 1,k1 x … x p,kp sunt conținute în spațiul liber SCliber; în caz contrar, regiunea baleiată de A în spațiul de lucru este considerată a fi conținută în regiunea C–obstacolelor. Luând în considerare toate celulele, se va construi o aproximare conservativă a spațiului liber ca o colecție de mici celule dreptunghiulare. Graful de conectivitate reprezentând relațiile de adiacență dintre aceste celule poate fi generat și parcurs în căutarea unui canal. Dezavantajul acestei metode constă în faptul că problema planificării complete nu este foarte eficientă în ceea ce privește viteza de calcul și memoria consumată. Totuși, în cele mai multe cazuri, simple modificări aduse metodei permit o reducere considerabilă a numărului celulelor care trebuie efectiv verificate. Unele din aceste modificări vor fi descrise în continuare.
Se consideră un obiect A1 în A. Poziția și orientarea lui în W depind numai de valoarea coordonatei q1. Dacă, pentru o valoare dată a acestei coordonate, obiectul se intersectează cu un obstacol, atunci dispare nevoia de a verifica obiectele A2, …, Ap pentru ciocniri cu obstacole. Într-adevăr, întreaga zonă (p-1) dimensională din SC proiectată la valoarea dată în C1 face parte din regiunea C–obstacolelor. În același mod, dacă pentru valori date C1, …, Ci, Ai se intersectează cu un obstacol, întreaga zonă (p-1) dimensională din SC proiectată la valoarea dată a lui C1, …, Ci face parte din regiunea C–obstacolelor. Aceasta sugerează construirea unei reprezentări a configurației spațiale de forma unui arbore de nivel p, ca în figura 3.11.
Figura 3.11. Spațiul configurațiilor unui braț manipulator este reprezentat în forma unui arbore de nivel p. Nodurile de la adâncimea i – 1 (i [1, p]) reprezintă descompuneri de rangul Ii în intervale PLINE și GOALE. Exceptând adâncimea p – 1, intervalele GOALE sunt descompuse în intervale mai mici i,ki. Considerăm nodul de adâncime 2 notat cu “*”. Intervalele GOALE ale acestui nod sunt formate din toate valorile lui C3 astfel încât A3(C1, C2, C3) nu se intersectează cu nici un obstacol când C1 baleiază peste i,ki și C2 baleiază peste 2,k2.
Fiecare nod la adâncimea i–1 (i [1, p]) în acest arbore reprezintă o descompunere de rangul Ii a valorilor lui Ci în intervale clasificate ca GOALE sau PLINE. Rădăcina acestui arbore (nodul de adâncime 0) reprezintă intervalul Ii. Intervalele goale ale descompunerii sunt formate de toate valorile lui C1 pentru care A1(C1) nu se intersectează cu nici un obstacol. Intervalele PLINE reprezintă complementara intervalelor GOALE în Ii. Intervalele GOALE sunt împărțite în 2 intervale mai mici 1,k1, k1 = 1,2… la rezoluția specificată. Arborele conține un nod la adâncimea 1 pentru fiecare astfel de interval. Se consideră orice interval 1,k1. Succesorul corespunzător reprezintă o descompunere a intervalului I2 în intervale PLINE și GOALE. Intervalele goale sunt formate din toate valorile lui C2 pentru care A2(C1, C2) nu se intersectează cu nici un obstacol când C1 baleiază peste 1,k1. Apoi, aceste intervale sunt descompuse în intervale mai mici 2,k2 și așa mai departe. Având în vedere că întreaga zonă poate fi clasificată ca parte din regiunea C–obstacolelor, la niveluri reduse de calcul, timpul și cantitatea de memorie necesară pentru construcția arborelui sunt de obicei mult mai mici decât la versiunile mai simple ale metodei prezentate anterior.
Când arborele este calculat complet, se va avea o reprezentare aproximativă a spațiului liber și a regiunii C–obstacolelor. În particular, dându-se configurația (C1, …, Cp) se poate ușor verifica dacă aparține spațiului liber sau nu. Într-adevăr, configurația determină un drum unic în arbore. Dacă drumul se termină la un interval PLIN (ceea ce se poate întâmpla la orice adâncime a arborelui), configurația se consideră în regiunea C–obstacolelor. Astfel, dacă drumul se termină într-un interval GOL, (ceea ce se poate întâmpla numai la adâncimea p – 1), configurația este în spațiul liber.
Figura 3.12 ilustrează reprezentarea configurației spațiale a unui braț cu două cuple de revoluție, calculată cu algoritmul anterior. Regiunea de C – obstacole (neagră în figură) este aproximativ ca un set de felii paralele cu axa C2.
Problema calcului pentru construirea arborelui din figura 3.11 este de a determina intervalele de valori ale qi, (i [1, p]) la care Ai(C1, …, Ci-1, Ci) nu intersectează nici un obstacol când C1, …, Ci-1 baleiază peste intervalele 1,k1,…, i-1,ki-1.
Figura 3.12. Figura (a) redă un braț de robot plan cu două cuple de rotație, printre obstacole, la două configurații libere marcate (1) și (2). Se presupune că nu există limitatoare mecanice în construcția cuplelor. Figura b redă reprezentarea configurației spațiale a robotului construit cu algoritmul descris în text. Regiunea C–obstacolelor (cu culoare întunecată) este aproximată de un set de zone paralele cu axa q2. Punctele desemnate cu 1 și 2 reprezintă configurațiile marcate cu (1) și (2) în figura a.
O tehnică simplă propusă de Lozano – Perez (1987) constă în fixarea valorilor C1,…,Ci-1 de exemplu la mijlocul C1,k1,…,Ci-1,ki-1 al intervalelor 1,k1,…, i-1,ki-1. În acest caz, procesul de calcul se reduce la determinarea intervalelor de valori ale lui Ci pentru care Ai(C1,k1, …, Ci-1,ki-1, Ci) nu intersectează nici un obstacol când se rotește în jurul unei axei fixe (cazul cuplei de rotație) sau translatează de-a lungul unei axe fixe (cazul cuplei de translație). Dacă Ai și obstacolele sunt modelate de poligoane sau poliedre, procesul de calcul este mai simplu.
Fixarea valorilor C1, …, Ci-1 constituie compromisul generării unei aproximări a spațiului liber care nu garantează conservativitatea. O cale de a înlătura acest compromis este de a calcula dispunerea Euclidiană maximă i a oricărui punct din Ai pentru orice Ci Ii când C1, …, Ci-1 baleiază 1,k1, …, i-1,ki-1. Obiectul Ai crește izotropic cu i și obiectul rezultat (altul decât Ai) este utilizat la descompunerea intervalului Ii în intervale PLINE și GOALE. Construirea arborelui reprezentând spațiul configurațiilor poate fi îmbunătățită astfel: fie Si (C1, …, Ci), i [1, p] regiunea baleiată de obiectele Ai+1, …, Ap unde Ci+1, …, Cp baleiază Ii+1, …, Ip și precedentele i obiecte A1, …, Ai sunt la configurația (C1, …, Ci). Trebuie subliniat faptul că doar poziția și orientarea lui Si (C1, …, Ci) depind de valorile C1, …, CI, nu și forma lui. Când intervalul Ii etichetează un nod de adâncime i-1 în arbore, intervalele generate sunt etichetate PLIN, S/GOL (pentru “sigur gol”) și P/GOL (pentru “posibil gol”):
intervalele de tipul PLIN sunt aceleași de înainte: ele sunt formate de toate valorile lui Ci astfel ca Ai(C1,k1, …, Ci-1,ki-1, Ci) se intersectează cu un obstacol când C1, …, Ci-1 baleiază 1,k1,…, i-1,ki-1.
intervalele de tipul S/GOL sunt formate de toate valorile lui Ci astfel încât Ai(C1, …, Ci-1, Ci) Si (C1, …, Ci-1, Ci) nu intersectează nici un obstacol când C1, …, Ci-1 baleiază 1,k1,…, i-1,ki-1.
intervalele de tipul P/GOL sunt complementarele intervalelor PLIN și S/GOL în Ii.
Doar intervalele de tip P/GOL din Ii sunt împărțite in intervale mai mici i,ki. Fiecare interval P/GOL dintr-un nod al arborelui poate fi asociat listei obstacolelor cu care Si intră în coliziune. Când succesorii acestui nod (corespunzători acestui interval) sunt luați în considerare, vor fi luate în considerare pentru testarea posibilelor ciocniri ale lui Ai+1 numai obstacolele din această listă. Astfel, în fiecare interval P/GOL al lui Ii+1, dacă lista este "curățată" mai departe prin eliminarea obstacolelor care nu se ciocnesc cu Si+1 (Faverjon și Tournassoud, 1989).
Odată ce reprezentarea arborescentă a configurației spațiale a robotului a fost construită, există încă problema construirii unui drum liber între configurația inițială și cea finală. Arborele redă o reprezentare directă a spațiului liber sub forma unei colecții de celule dreptunghiulare. Graful de conectivitate ce reprezintă relațiile de adiacență dintre aceste celule poate fi construit și parcurs în căutarea unui canal. Oricum, celulele derivate din reprezentarea arborescentă sunt foarte subțiri de-a lungul câtorva dimensiuni și de obicei sunt multe, rezultând un graf de conectivitate complicat. Poate fi preferabilă gruparea acestor celule în dreptunghiuri mai mari. Un mod de rezolvare a acestei probleme este de a considera reprezentarea arborescentă și reprezentarea exactă a configurației spațiale și apoi aplicarea metodei de descompunere celulară aproximativă a acestei reprezentări. Utilizând informațiile conținute în arbore, etichetarea unor noi celule generate cu această metodă ca GOALĂ, PLINĂ și MIXTĂ este simplă în particular.
3.3.4. Câmpuri potențial
Abordarea bazată pe câmpuri potențial se aplică roboților articulați. La fel ca în cazul unui singur obiect rigid, există mai multe metode posibile bazate pe această abordare.
De obicei, se consideră o colecție de puncte de control aj A, j = 1, …, q care pot fi distribuite peste diferite obiecte Ai. Fiecare punct aj este supus unui câmp de potențial Vj(x) definit în spațiul de lucru. Acest potențial poate fi atractiv, care depinde de destinația lui Aj în W, un potențial repulsiv, care depinde de obstacolele din spațiul de lucru sau un potențial mixt depinzând și de destinația lui aj și de obstacole.
Funcția potențial U(C) în spațiul configurațiilor robotului este obținută prin însumarea acestor potențiale:
Funcția induce forța atractivă definită de:
Se consideră o aplicație în spațiul configurațiilor SC ale robotului. Astfel, configurația C este parametrizată de (C1, …, Cp) cu fiecare Ci definind poziția relativă a două obiecte conectate printr-o cuplă. Componentele lui R(C) în baza lui TC(C) (tangentă la C în spațiul SC) induse de această aplicație sunt forțele care acționează în fiecare cuplă cinematică a robotului. Se presupune în continuare că W=R3, cu x, y, z coordonatele unui punct x W în SW. Fie Xj(C1, …, Cp), Yi(C1, …, Cp) coordonatele lui aj(C) în R(C) este:
Astfel, relația devine:
unde JjT este transpusa matricei Jacobiene Jj a spațiului:
(C1,…,Cp) Rp Xj(C1,…,Cp), Yi(C1,…,Cp), Zj(C1,…,Cp) R3
Același rezultat se memorează cu W = R2.
Dacă mișcarea unei cuple este limitată de opritoare mecanice, aceste opritoare pot fi luate în calcul în funcția potențial. Un mod de a rezolva aceasta problemă este prezentat de Khatib [37]. Fie o configurație de coordonate C1 limitată într-un interval (Ci-, Ci+) de opritoare mecanice din cupla corespunzătoare. Ambele capete ale intervalului pot fi tratate ca obstacole generatoare de câmpuri de potențial repulsiv W-(Ci) și W+(Ci). Utilizând aceeași formă generală ca pentru funcția potențial repulsiv definită anterior, se vor defini W-(Ci) și W+(Ci) după cum urmează:
W- (Ci) = pentru Ci- Ci- 0
W- (Ci) = 0 Pentru Ci- Ci- > 0
și:
W+ (Ci) = pentru Ci+- Ci 0
W+ (Ci) = 0 pentru Ci+- Ci > 0
unde este un factor scalar pozitiv și 0 este “distanța de influență” a opritoarelor mecanice.
La funcția U(C1, …, Cp) sunt adăugate diferitele funcții W- (Ci) și W+ (Ci) pentru a obține funcția potențial ce ia în calcul și opritoarele din cuple. Toate componentele forței induse de W- (Ci) și W+ (Ci), excepție făcând componenta i, sunt 0.
Componenta i a acestei forțe are valoarea:
pentru Ci- Ci- 0
pentru Ci- Ci- > 0
și:
pentru Ci+- Ci 0
pentru Ci+- Ci > 0
Diferitele metode bazate pe câmpul potențial pot fi utilizate la planificarea drumurilor libere pentru brațe manipulatoare. Ca o ilustrare a calității acestei abordări, figurile 3.13 și 3.14 redau instantanee de-a lungul a două drumuri generate de un planificator aleator. Figura 3.13 ilustrează un drum pentru un robot echipat cu 8 cuple de rotație. Figura 3.14 ilustrează un drum pentru un robot echipat cu 10 cuple de rotație (cel din figura 3.8). Exemplul din figura 3.13 a fost executat utilizând un singur punct de control aflat la capătul brațului.
Exemplul din figura 3.14 a fost executat utilizând două puncte de control aflate la capetele celor două lanțuri cinematice. În ambele exemple, ciocnirile diferitelor legături între ele, vor fi studiate explicit în același mod ca și ciocnirile între robot și obstacole.
Opritoarele mecanice vor fi impuse fiecărei cuple și ciocnirile cu fiecare opritor vor fi de asemenea studiate.
Figura 3.13. Această figură redă instantanee de-a lungul unui drum generat pentru un robot cu opt cuple de rotație prin implementarea metodei bazate pe câmpuri potențial aleatoare.
Figura 3.14. Această figură redă instantanee de-a lungul unui drum generat pentru un robot cu 10 cuple (cel din figura 3.8) generate de o implementare a metodei bazate pe câmpuri potențial aleatoare.
C A P I T O L U L 4
IMPLEMENTAREA ALGORITMULUI DE PLANIFICARE
A MISCARII ROBOTILOR INDUSTRIALI
Introducere
Prin definiție, un robot este un dispozitiv mecanic sau o combinație de dispozitive echipate cu servomotoare și senzori și aflate sub controlul unui sistem de calcul.El opereaza intr-un spațiu real populat cu obiecte fizice și trebuie sâ fie capabil sâ-și planifice propriile mișcâri pentru a realiza o sarcina in funcție de aranjamentul inițial și final al obiectelor din spațiul de lucru.Robotul va trebui sâ realizeze mișcarea doritâ și sâ-și activeze diferitele organe in acord cu obiectivul pe care il are.Totul depinde de cunostințele pe care robotul le are asupra configurației inițiale a spațiului de lucru (statice) cât și de cele obținute pe parcursul evoluției sale (dinamice).
Asigurarea indeplinirii sarcinii unui robot se bazeaza pe trei acțiuni majore:
-stabilirea unei strategii de navigare;
-modelarea spațiului de lucru;
-planificarea mișcârii in spațiul de lucru respectiv;
Stabilirea unei strategii de navigare se referâ la determinarea metodelor de plasare a robotului in acord cu tipul sarcinii de executat.Pot exista trei tipuri distincte de navigare:
a) Deplasarea dintr-un punct al spațiului intr-un alt punct,ambele având poziții bine precizate;strategia constâ in a genera o astfel de functiede comandâ încât sâ se atingâ poziția dorită.
b) Baleierea intregii zone,navigare ce se impune pentru roboții a câror sarcinâ este de a atinge intreaga suprafațâ de lucru în scopul efectuârii unei anumite acțiuni.Navigarea se poate realiza prin douâ strategii distincte:
-deplasarea în spiralâ prin porțiuni de traiectorii paralele cu traiectorii deja utilizate, pornind de la perimetrul exterior al spațiului și mergând din aproape în aproape spre centru.
-deplasarea în zig-zag, ce constâ din parcurgerea zonei utile de la stânga la dreapta și de sus în jos, sau invers.
In cazul unui spațiu de lucru complex prevâzut cu multe obstacole,metoda de navigare constâ în a-l împârți în zone în care se sâ poatâ aplica una din strategiile menționate.Problema constă în a minimiza numârul zonelor pe care robotul ar trebui sâ le traversezede mai multe ori.
c) Urmârirea unui alt mobil care se deplaseazâ sau a contururilor unui obstacol din spațiul de lucru.
Programul realizat in cadrul acestui proiect urmârește cel de-al doilea obiectiv,modelarea spațiului de lucru.Din metodele dezvoltate pentru aceastâ acțiune, din care enumerâm metoda grilei, metoda arborelui, metoda poligoanelor convexe, metoda punctelor de trecere, etc, am ales pentru implementare metoda grilei omogene și neomogene, respectiv metoda arborelui.
4.1. Metoda Grilei Omogene
Este o metoda simplă de modelare, care, referindu-ne la un spațiu bidimensional, constă în împărțirea sa în celule dreptunghiulare de dimensiuni identice, a căror apartenență la o zonă permisă sau interzisă e booleană.
Precizia modelului depinde de dimensiunile celulelor.Capacitatea de memorie necesară pentru a înregistra ansamblul coordonatelor celulelor este mare.
Utilizarea unor celule paralelipipedice permite modelarea unui spațiu tridimensional.
O strategie pentru găsirea drumului unui robot constă în folosirea inițialăa unor celule de dimensiuni mari, ce solicită mai puțină memorie.Dacă folosind aceste celule nu este găsită o cale pentru deplasarea robotului,atunci se vor reduce dimensiunile celulelor.Algoritmul se repetă până cândse obține o soluție.
Metoda Arborelui
Această metodă provine din cea precedentă, considerând dreptunghiurile ca fiind de dimensiuni neegale.
Un arbore este o reprezentare particularâ în care fiecare nod are douâ forme diferite:
– nodul de tip frunzâ ce reprezintâ o celulâ care nu va mai fi descompusâ și căreia îi este asociată o funcție booleană definind posibilitățile de acces;
– nodul de tip creangă căreia îi succed alte patru noduri rezultate prin descompunerea celulei corespunzătoare în patru celule egale.
Numărul de celule în care se împarte fiecare celulă inițial considerată este de obicei patru;în spațiul tridimensional, fiecare celulă paralelipipedicâ se împarte în căte opt celule.
Metoda Grilei Neomogene
Metoda grilei neomogene este folosită pentru descompunerea unui spațiu de lucru complex în zone dreptunghiulare în care robotul să se poatâ mișca fără restricții.Algoritmul folosit de această metodă asigură împărțirea spațiului într-un număr minim de dreptunghiuri ce acoperă întrgul spațiu liber și au o arie maximă.Astfel vor exista dreptunghiuri incluse în altele.
Metoda presupune toate obstacolele de formă dreptunghiulară.Dacă ele nu au această formă, atunci se vor aproxima printr-un dreptunghi acoperitor.Existând un număr de n obstacole în spațiul de lucru, acesta se împarte printr-o grilă rezultată prin prelungirea laturilor obstacolelor, obținându-se (2n+1)y dreptunghiuri.
Fiecare regiune este reprezentată prin două lanțuri binarede 2n+1 biți, dintre care unul reprezintă poziția relativă x, iar celălalt poziția relativă y.
Exemplificare:
-lanțul 0 1 0 0 0 caracterizează situația în care obstacolul este pe poziția a doua, pornind de la stânga;
-lanțul 0 0 1 0 0 caracterizează situația în care obstacolul este al treilea, pornind de sus.
De asemenea, pentru a reprezenta mai multe regiuni:
1 1 0 0 0 0 0 1 1 0
se realizează tablourile echivalente:
1 0 0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0 1 0
Modelarea se realizează în șase etape.
Etapa 1: Reprezentarea fiecărei benzi orizontale prin 2n+1 biți.Un bit are valoarea “1” dacă celula este liberă și “0” în caz contrar.Un al doilea lanț conține un singur “1” care corespunde la poziția verticală a benzii.
1 1 1 1 1 1 0 0 0 0
1 0 1 1 1 0 1 0 0 0
1 1 1 1 1 0 0 1 0 0
1 1 1 0 1 0 0 0 1 0
1 1 1 1 1 0 0 0 0 1
Etapa 2: Determinarea tuturor benzilor orizontale continue rezultate din separarea primului lanț în mai multe, fiecare având o suită continuă de “1”.De exemplu:
1 1 1 1 1 0 0 1 0 0 devine:
1 0 0 0 0 0 1 0 0 0
0 0 1 1 1 0 1 0 0 0
Etapa 3: Se face o listă cu toate lanțurile generate în etapa a doua, astfel ca:
– lanțurile să fie regrupate în raport cu benzile care le-au generat;
– grupele să fie ordonate în raport cu poziția verticală a benzilor generatoare.
Linia 1
1 1 1 1 1 1 0 0 0 0
1 0 0 0 0 0 1 0 0 0
0 0 1 1 1 0 1 0 0 0
1 1 1 1 1 0 0 1 0 0
1 1 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1 0
1 1 1 1 1 0 0 0 0 1
Etapa 4: Generarea unei noi liste pornind de la cea precedentă confor următoarelor reguli:
-noua grupă i de lanțuri este generată prin combinarea fiecărui lanț din vechea grupă i+1 (i=1,2,..);
-două lanțuri sunt combinate printr-un SI logic pentru lanțurile din stânga și SAU logic pentru lanțurile din dreapta; dacă toți bițiisunt nuli, lanțul respectiv se elimină,dacă nu, se include pe listă.
-de fiecare dată când un lanț este adăugat la noua listă se elimină lanțurile de pe lista precedentă care sunt acoperite de această nouă adăugare;un lanț S1 este acoperit de către S2 dacă un SAU logic intre ele conduce la S2.
Etapa 5: Se repetă etapa 4 dacă noua listă are două sau mai multe grupe.
Linia 2:
1 0 0 0 0 1 1 0 0 0
0 0 1 1 1 1 1 0 0 0
1 0 0 0 0 0 1 1 0 0
0 0 1 1 1 0 1 1 0 0
1 1 1 0 0 0 0 1 1 0
0 0 0 0 1 0 0 1 1 0
1 1 1 0 0 0 0 0 1 1
0 0 0 0 1 0 0 0 1 1
Linia 3:
1 0 0 0 0 1 1 1 0 0
0 0 1 1 1 1 1 1 0 0
1 0 0 0 0 0 1 1 1 0
0 0 1 0 0 0 1 1 1 0
0 0 0 0 1 0 1 1 1 0
1 1 1 0 0 0 0 1 1 1
0 0 0 0 1 0 0 1 1 1
Linia 4:
1 0 0 0 0 1 1 1 1 0
0 0 1 0 0 1 1 1 1 0
0 0 0 0 1 1 1 1 1 0
1 0 0 0 0 0 1 1 1 1
0 0 1 0 0 0 1 1 1 1
0 0 0 0 1 0 1 1 1 1
Linia 5:
1 0 0 0 0 1 1 1 1 1
0 0 1 0 0 1 1 1 1 1
0 0 0 0 1 1 1 1 1 1
Etapa 6: Se stabilesc lanțurile neeliminate de pe liste care reprezintă o zonă fără obstacole.
4.4. Prezentarea programului
Programul prezentat in cadrul proiectului este conceput în mediul de programere C++. Pentru funcționarea sa sunt necesare un PC din familia Intel 80×486 cu placa grafică VGA și mouse.
La lansarea în execuție,este prezentată o fereastră cu numele programului si al candidatei. După apăsarea butonului de confirmare,apare meniul principal. Deasupra meniului este o fereastră cu numele configurației curente.
Comenzile sunt selectate cu ajutorul mouse-ului după cum urmează:
1.New: La apelul acestei comenzi sunt șterse toate obiectele din spațiul de lucru. Menționăm că la lansarea în execuție a programului există o configurație “default” a acestui spațiu,din motive de exmplificare rapidă.
2.Open: Cu ajutorul acestei comenzi se poate încărca o configurație a spațiului de lucru salvată pe disc sub forma de fișier.Fișierele au o terminația “mec”.Numai fișierele aflate în directorul curent pot fi încărcate.Ele sunt afișate într-o listă de unde pot fi selectate cu ajutorul mouse-ului.Dacărul de fișiere existente este mai mare decăt numărul fișierelor ce pot fi afișate la un moment dat, se vor folosi butoanele de scroll,prezentate la extremitățile ferestrei.În momentul în care este selectat un fișier,numele lui apare într-o fereastră aflată deaspra listei, iar prin apăsarea butonului “DA” configurația este încărcată în memorie. De asemenea,se poate renunța la încărcare prin selectarea butonului “NU”.
3.Save: Prin această comandă se salvează configurația curentă din memorie pe disc,într-un fișier de tipul “.mec”.Dacă configurația nu are nume (munele se poate vizualiza în paretea de sus a meniului),sunteți invitați să introduceți un nume.Acest nume este format din maxim 8 caractere alfanumerice. Nu sunt permise semne de punctuație și nu este necesară introducerea terminației.
OBS. Fișierele “.mec” sunt fișiere de tip text,putând fi posibilă modificarea lor cu un editor obișnuit,deși este recomandată editarea lor cu comanda “Paint” ce va fi descrisă mai jos.
Formatul fișierului este următorul:
n
nrvârfuri 1
cx11 cy11
cx12 cy12
:
cd l nrvârfuri1 cd nrvârfuri1
nrvârfuri2
cx21 cy21
:
:
unde:
n-numarul de obiecte din figură.Obiectele sunt de două tipuri: dreptunghiuri și poligoane.
nrvârfurix x=1..n;
-numărul de vârfuri ale obiectului x. Dacă nrvârfurix este
pentru 2, atunci obiectul x este un dreptunghi.Numărul minim de vârfuri un poligon este 4 (primul vârf coincide cu ultimul).
cxij cyij
-coordonatele vârfului j din obiectul i.Coordonatele sunt numere întregi din domeniu 0<=x<=639 și 0<=y<=439.
4.Paint: Cu acesta se editează spațiul de lucru.Se pot adăuga diferite obiecte (maxim 30).Inițial obiectul care se va adăuga este dreptunghi.Prin apăsarea butonului dreapta al mouse-ului,apare un mini meniu cu care se selsctează desenarea dreptunghiurilor,a poligoanelor sau se notifică terminarea editării.
Pentru dreptunghiuri,se apasă butonul stânga al mouse-ului în punctul inițial al dreptunghiului,se mișcă mouse-ul ținând apăsat butonul până în punctul final,când se eliberează butonul.În cursul mișcării se vizualizează instantaneu poziționarea dreptunghiului.
Pentru poligoane,se desnează cu ajutorul mouse-ului liniile ce constituie perimetrul.Se aplică aceeași regulă cu apăsarea butonului stânga.
În momentul in care este adăugat și ultimul vârf,se apsă butonul dreapta,și poligonul este închis automat (primul vârf va coincide cu ultimul).
5.Run: Cu ajutorul acestei comenzi este cativată procedura pentru analizarea spațiului de lucru.Sunteți solicitați să introduceți metoda de analiză: I. Metoda Grilei Omogene
II. Metoda Arborelui
Metoda Grilei Neomogene
6.Exit: Se iese din program.
În cursul creării programului,o grijă deosebită a fost acordată optimizării algoritmilor pentru efectuarea descompunerii spațiului de lucru.
4.5. Exemplificarea programului
Metoda Grilei Omogene:
Este afișat spațiul de lucru.La apăsarea butonului stânga al mouse-ului, este suprapusă descompunerea în celule dreptunghiulare a spațiului respectiv.Celule au dimensiunea 16X15, astfel încât există o matrice de 40X32 de celule, o dimensiune rezonabilă pentru salvarea spațiului de memorie.Celulele goale sunt negre, cele pline albe iar celulele mixte au culoarea gri.
În implementarea acestei metode,s-a ales o dimensiune a celulei de 16X15 puncte,în special pentru creșterea vitezei de analiză.
pentru i=0,39
pentru j=0,31
dacă celula [I,j] este mixtă
atunci desenează;
Se parcurge întreaga matrice de celule,iar dacă este mixtă se desenează un dreptunghi de culoare gri.
Deoarece imaginea spațiului de lucru este binară (1-punct ocupat,0-punct liber) șirurile de 16 puncte sunt echivalente cu un număr.Astfel obținem 15 numere întregi pentru o celulă de 16X15.
Dacă tote numerele sunt 6535(echivalentul zecimal al șirului binar 1111111111111111) atunci celula e plină.
În acelaș mod,dacă toate numerele sunt nule,celula este goală,dacă celula nu e nici plină,nici goală,atunci avem de-a face cu o celulă mixtă.
Metoda Arborelui:
Este abordată o împărțire de 2×2,cu adâncimea maximă a arborelui de 5.
Celulele minime rezultate au dimensiunea de 20×15. Acestă metodă necesită un timp de așteptare ceva mai lung (3 sec. pe un calculator 486/133MHz) datorat amalizei arborelui.Mențiunile referitoare la culoarea celulelor raman valabile și aici.
Deși în mod normal analizarea începe cu o dimensiune mare a celulelor, urmând ca ea să fie înjumătățită în cazul unei celule mixte, programul prezentat efectuează descompunerea în celule de dimensiune minimă (în cazul nostru 20X15).
Dacă s-ar fi urmat varianta clasică,atunci,în cazul unor celule mixte,
s-ar fi analizat de maxim 5 ori un fragment din spațiul de lucru,ceea ce ar fi dus la niște timpi de execuție mari.
Se folosește un algoritm asemănător cu cel descris la metoda grilei omogene.Rezultatele sunt înscrise într-o matrice 32X32.Dacă o celulă e mixtă,atunci ea este desenată.
Cu ajutorul acestei matrici se construiește una cu rezoluție mai mică(16X16).Astfel,dacă toate cele 4 celule din matricea 32X32 incluse într-o celulă 16X16 sunt pline,atunci și celula mare e plină.Analog,în cazul celulelor goale.Dacă nici una din condițiile de mai sus nu este îndeplinită,celula rezultată este goală.
Repetând algoritmul de 4 ori,se ajunge la o matrice de 2X2.
Metoda Grilei Neomogene:
Aceasta metodă a fost dezvoltată mai mult decât celelalte,aici fiind posibilă și găsirea unui drum între 2 puncte ale spațiului de lucru.
Inițial, sunt afișate obiectele și grila rezultată prin prelungirea laturilor dreptunghiurilor.De menționat că poligoanele sunt aproximate prin dreptunghiul acoperitor.Prin apăsarea repetată a butonului stânga al
mouse-ului sunt afișate zonele dreptunghiulare găsite prin aplicarea variantei optimizate a algoritmului de descompunere.Zonele respectă condițiile stabilite la partea teoretica,fiecare zonă fiind etichetată cu o literă mare,începând cu ‘A’ și terminând cu ‘Z’.După prezentarea tuturor zonelor,este afișat graful de adiacență.Pentru facilitarea vizualizării grafului,acesta este suprapus peste imaginea spațiului de lucru,fiecare nod al grafului fiind așezat în mjlocul zonei pe care o etichetează.
Sunteți invitați să introduceți punctele inițial și final ale mișcării robotului.Ele sunt notificate prin apăsarea butonului stânga al mouse-lui.
Nu sunt luate în considerare pozițiile aflate în interiorul dreptunghiurilor de încadrare.Drumul găsit este afișat instantaneu.
În partea teoretică a lucrării,am inclus și algoritmul pentru analiza spațiului de lucru cu ajutorul metodei grilei neomogene.În implementarea programului,în locul șirurilor binare vom folosi dreptunghiuri.Pentru reprezentarea acestora sunt necesare 4 numere,vărfurile stânga-sus și dreapta-jos.Coordonatele vârfurilor reprezintă poziția dreptonghiurilor în matricea obținută după trasarea grilei.
Drumul robotului. Exemplificare
C O N C L U Z I I
Planificarea mișcării unui robot prezintă o varietate de aspectedificile de calcul. Astfel, pe parcursul primului capitol s-au prezentat aspectele planificării mișcării unui robot, specificând problema de bază a planificării unei traiectorii. Cea mai simplă problemă de planificare presupune că robotul este singurul obiect în mișcare în spațiul de lucru, care nu posedă proprietăți dinamice evitând astfel problemele temporale.
Se consideră de asemenea că robotul nu intră în contact cu obiectele înconjurătoare,evitând astfel problemele legate de interacțiunea mecanică dintr obiecte fizice. Aceste considerații transformă problema planificării ”fizice” a mișcării într-o problemă pur geometrică. Deși problema de bazăa planificării traiectoriilor este simplificată, ea este totușio problemă dificilă cu mai multe soluții și cu extensiidirecte spre probleme mai complicate.
Problema de bază a planificării traiectoriei presupune că robotul parcurge cu exactitate traiectoria generată de planificator, și că atăt geometria robotului, căt și pozițiile obstacolelor sunt cunoscute cu exactitate, însăîn realitate nici o problemă de planificare nu satisface aceste ipoteze.
Un robot este conceput să realizeze trei categorii de sarcini:
– deplasări pure;
eforturi pure;
sarcini compliante care combină deplasările cu eforturi.
Mișcarea ce trebuie executată de robot este specificată de planul de mișcare, iar o traiectorie precizează o secvență continuă a configurațiilor pe care robotul trebuie să le traverseze spre configurația finală.
De asemenea s-a presupus că robotul deține informații complete și exacte despre mediul său înconjurător.În majoritatea situațiilorînsă, geometria spațiului de lucru poate fi doar parțial cunoscută în momentul planificării.Rezolvarea problemei de planificare a mișcării necesită cunoașterea modelului mediului înconjurător. Dacă robotul nu deține suficiente informații despre mediul său, acesta trebuie să se bazeze pe înregistrarea informațiilor prin intermediul sistemului senzorial și să reacționeze la informațiile preluate de senzori.
Asigurarea îndeplinirii sarcinii unui robot se bazează pe trei acțiuni majore:
– stabilirea unei strategii de navigare;
modelarea spațiuarelui de lucru;
planificarea mișcării în spațiul de lucru respectiv.
Stabilirea unei strategii de navigare se referă la determinarea metodelor de deplasare ale robotului în acord cu tipul sarcinii de executat. Se disting trei tipuri de strategii de navigare.
Stabilirea unei hărți de navigare în spațiul considerat se poate face fie independent de orice acțiune a robotului prin memorarea unei cofigurații date, care de regulă, reprezintă starea inițială a spațiului de lucru, fie în cursul executării sarcinii pe măsură ce robotul își descoperă propriul spațiu de lucru.
Prin intermediul cunoștințelor astfel acumulate se poate împărți spațiul de lucru în celule independente care să reprezinte zone accesibile respectiv interzise pentru robot. Această operație se numește modelarea spațiului de lucru al robotului.
Metodele de modelare prezentate în cadrul acestui proiect sunt:
– metoda grilei omogene;
– metoda arborelui;
– metoda grilei neomogene.
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Planificarea Miscarii Robotilor Industriali (ID: 161283)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.